一、為什么Rust標(biāo)準(zhǔn)庫的TreeMap采用B樹實(shí)現(xiàn)

簡單來說，BST確實(shí)是理論上內(nèi)存數(shù)據(jù)結(jié)構(gòu)的優(yōu)異解，但是有個(gè)前提：內(nèi)存是真的均質(zhì)隨機(jī)訪問內(nèi)存。這里給出一個(gè)定義，均質(zhì)隨機(jī)訪問內(nèi)存即主存擁有在任意上下文場景下，訪問任意地址，都有著非常相似的性能。但是很不幸，現(xiàn)在的內(nèi)存并不是這樣子的。

在計(jì)算機(jī)當(dāng)中，由于cache的存在，訪問臨近位置的內(nèi)存在平均意義下會產(chǎn)生非常巨大的性能提升，而BST的特性導(dǎo)致臨近的元素并不是在內(nèi)存中存放在一起的，從而在實(shí)踐當(dāng)中性能非常糟糕。而B-Tree在大部分場景下，可以讓一些臨近元素在內(nèi)存中存放在一起，從而在大部分情況下，實(shí)踐中得到比BST更好的性能。

B-Tree相對于B+Tree的優(yōu)劣勢：

優(yōu)勢：省內(nèi)存，不需要多做一層索引。

劣勢：Iter略慢，next() 最差會出現(xiàn)log n的復(fù)雜度，B+Tree可以穩(wěn)定O(1)。

可以區(qū)分index和數(shù)據(jù)，把index做的很小，放進(jìn)更快但是更小的存儲中。

首先Rust的BTreeMap是全放在內(nèi)存里的，第三條基本上就沒啥用，第二條的性能提升微乎其微，但是名列前茅條的省內(nèi)存可是實(shí)實(shí)在在的，所以B+Tree在這個(gè)使用場景下GG。

再給大家添加一個(gè)B+Tree很適合的使用場景來進(jìn)一步學(xué)習(xí)下B+Tree，一個(gè)典型應(yīng)用是硬盤KV數(shù)據(jù)庫，開啟數(shù)據(jù)庫的時(shí)候根據(jù)硬盤中保存的葉子結(jié)點(diǎn)們在內(nèi)存中構(gòu)造出來B+Tree的index部分，這樣子的硬盤KV的讀寫一個(gè)key一般只需要hit一次硬盤就可以完成，當(dāng)然觸發(fā)平衡時(shí)候會是多次，但是相比于純硬盤BTree的log n次硬盤操作（index大 內(nèi)存塞不下）而言，優(yōu)勢非常明顯的。

延伸閱讀：

二、TreeMap概述

TreeMap存儲K-V鍵值對，通過紅黑樹（R-B tree）實(shí)現(xiàn)；

TreeMap繼承了NavigableMap接口，NavigableMap接口繼承了SortedMap接口，可支持一系列的導(dǎo)航定位以及導(dǎo)航操作的方法，當(dāng)然只是提供了接口，需要TreeMap自己去實(shí)現(xiàn)；

TreeMap實(shí)現(xiàn)了Cloneable接口，可被克隆，實(shí)現(xiàn)了Serializable接口，可序列化；

TreeMap因?yàn)槭峭ㄟ^紅黑樹實(shí)現(xiàn)，紅黑樹結(jié)構(gòu)天然支持排序，默認(rèn)情況下通過Key值的自然順序進(jìn)行排序；