为什么程序和数据库之间的“默认”选择会产生不同呢？
作者
EvanJones
译者
弯月，责编
屠敏
以下为译文：
我可以肯定地说，哈希表远比有序数据结构更常见，Go中的map、Python中的dict、Java中的HashMap等都是哈希表，而树结构只在保存有序数据结构时才使用。有一次，在谈到Google优化C++的哈希表时，有人指出在整个Google的服务器中，有1%的CPU和4%的内存都被哈希表使用了。然而，数据库默认总是会使用有序索引，通常是B树。为什么程序和数据库之间的“默认”选择会产生不同呢？说到底两者都是为了同一个目标：访问数据。一年前，我曾就这个问题在Twitter上发表了推文，并得到了许多有趣的答案。下面就来总结一下我得到的答案。
常见的答案是，当在内存中存储数据时，哈希表的效率很高，而B树的设计旨在以块的形式访问较慢的存储。然而，这不是决定性的属性。我们也有为访问磁盘而设计的哈希表，例如MySQL的哈希索引；也有许多在内存中使用的树，例如Java的TreeMap、C++的映射；甚至连B树都有内存中使用的版本。
我认为最重要的答案是，B树更适合于“一般用途”，它们能够以较低的总成本访问大规模的持久数据。换句话说，即使在访问大部分工作负载都是单个值的数据时，B树的速度较慢，但考虑到罕见的操作和多个索引的成本，B树的表现还是更为突出。在本文中，我将简要解释哈希表和B树之间的差异，然后讨论持久性数据与内存数据在需求上有何不同。最后，尽管我认为“内存应该使用有序的数据结构而数据库应该使用哈希表”这种默认的做法可能是正确的，但我仍然会提出一些自己的看法。
哈希表与树
首先，让我们回顾一下这些数据结构之间的根本区别。在访问单个值时，哈希表的访问时间是常数O(1)，而树的访问时间是对数O(logn)。对于单值查找，这意味着无论数据存储在内存中还是磁盘中，哈希表的速度都比较快。但是，尽管树有额外开销，但树中的值都是有序的。因此，我们可以高效地访问范围值，这意味着它们可以有效地支持多种操作。例如，我们可以查找所有以某个前缀开头的值，或者“前k个”值，换作哈希表的话，则我们需要扫描整个表。关于数据库中B树的使用，我强烈建议你阅读《ModernB-TreeTechniques》（