一、為什么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值的自然順序進行排序；