一、为什么Rust标准库的TreeMap采用B树实现

简单来说，BST确实是理论上内存数据结构的优异解，但是有个前提：内存是真的均质随机访问内存。这里给出一个定义，均质随机访问内存即主存拥有在任意上下文场景下，访问任意地址，都有着非常相似的性能。但是很不幸，现在的内存并不是这样子的。

在计算机当中，由于cache的存在，访问临近位置的内存在平均意义下会产生非常巨大的性能提升，而BST的特性导致临近的元素并不是在内存中存放在一起的，从而在实践当中性能非常糟糕。而B-Tree在大部分场景下，可以让一些临近元素在内存中存放在一起，从而在大部分情况下，实践中得到比BST更好的性能。

B-Tree相对于B+Tree的优劣势：

优势：省内存，不需要多做一层索引。

劣势：Iter略慢，next() 最差会出现log n的复杂度，B+Tree可以稳定O(1)。

可以区分index和数据，把index做的很小，放进更快但是更小的存储中。

首先Rust的BTreeMap是全放在内存里的，第三条基本上就没啥用，第二条的性能提升微乎其微，但是名列前茅条的省内存可是实实在在的，所以B+Tree在这个使用场景下GG。

再给大家添加一个B+Tree很适合的使用场景来进一步学习下B+Tree，一个典型应用是硬盘KV数据库，开启数据库的时候根据硬盘中保存的叶子结点们在内存中构造出来B+Tree的index部分，这样子的硬盘KV的读写一个key一般只需要hit一次硬盘就可以完成，当然触发平衡时候会是多次，但是相比于纯硬盘BTree的log n次硬盘操作（index大 内存塞不下）而言，优势非常明显的。

延伸阅读：

二、TreeMap概述

TreeMap存储K-V键值对，通过红黑树（R-B tree）实现；

TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要TreeMap自己去实现；

TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；

TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；

上一篇

数据结构构造有哪些?

下一篇

为什么要引入红黑树，它比普通的平衡二叉树究竟好在哪?