一、為什么Rust標準庫的TreeMap采用B樹實現(xiàn)
簡單來說,BST確實是理論上內(nèi)存數(shù)據(jù)結(jié)構的優(yōu)異解,但是有個前提:內(nèi)存是真的均質(zhì)隨機訪問內(nèi)存。這里給出一個定義,均質(zhì)隨機訪問內(nèi)存即主存擁有在任意上下文場景下,訪問任意地址,都有著非常相似的性能。但是很不幸,現(xiàn)在的內(nèi)存并不是這樣子的。
在計算機當中,由于cache的存在,訪問臨近位置的內(nèi)存在平均意義下會產(chǎn)生非常巨大的性能提升,而BST的特性導致臨近的元素并不是在內(nèi)存中存放在一起的,從而在實踐當中性能非常糟糕。而B-Tree在大部分場景下,可以讓一些臨近元素在內(nèi)存中存放在一起,從而在大部分情況下,實踐中得到比BST更好的性能。
B-Tree相對于B+Tree的優(yōu)劣勢:
優(yōu)勢:省內(nèi)存,不需要多做一層索引。
劣勢:Iter略慢,next() 最差會出現(xiàn)log n的復雜度,B+Tree可以穩(wěn)定O(1)。
可以區(qū)分index和數(shù)據(jù),把index做的很小,放進更快但是更小的存儲中。
首先Rust的BTreeMap是全放在內(nèi)存里的,第三條基本上就沒啥用,第二條的性能提升微乎其微,但是名列前茅條的省內(nèi)存可是實實在在的,所以B+Tree在這個使用場景下GG。
再給大家添加一個B+Tree很適合的使用場景來進一步學習下B+Tree,一個典型應用是硬盤KV數(shù)據(jù)庫,開啟數(shù)據(jù)庫的時候根據(jù)硬盤中保存的葉子結(jié)點們在內(nèi)存中構造出來B+Tree的index部分,這樣子的硬盤KV的讀寫一個key一般只需要hit一次硬盤就可以完成,當然觸發(fā)平衡時候會是多次,但是相比于純硬盤BTree的log n次硬盤操作(index大 內(nèi)存塞不下)而言,優(yōu)勢非常明顯的。
延伸閱讀:
二、TreeMap概述
TreeMap存儲K-V鍵值對,通過紅黑樹(R-B tree)實現(xiàn);
TreeMap繼承了NavigableMap接口,NavigableMap接口繼承了SortedMap接口,可支持一系列的導航定位以及導航操作的方法,當然只是提供了接口,需要TreeMap自己去實現(xiàn);
TreeMap實現(xiàn)了Cloneable接口,可被克隆,實現(xiàn)了Serializable接口,可序列化;
TreeMap因為是通過紅黑樹實現(xiàn),紅黑樹結(jié)構天然支持排序,默認情況下通過Key值的自然順序進行排序;