其实这个答案在rust的docs网站上已经有个清晰的阐述，我接下来只是把这些阐述以自己的语言搬运过来，链接在最尾。 简单来说，BST确实是理论上内存数据结构的最优解，但是有个前提：内存是真的均质随机访问内存。这里给出一个定义，均质随机访问内存即主存拥有在任意上下文场景下，访问任意地址，都有着非常相似的性能。但是很不幸，现在的内存并不是这样子的。 在计算机当中，由于cache的存在，访问临近位置的内存在平均意义下会…