为什么数据库常使用有序数据结构而编程语言使用哈希表结构

编译自https://www.evanjones.ca/ordered-vs-unordered-indexes.html

在编程语言里哈希表结构（例如 Go 中的 Map，Python 中的 Dict，Java 中的 HashMap 等）要比有序索引的数据结构（例如Tree）更常见。作者提到了，Google 对 C++ 哈希表结构的优化总体上减少了1％ CPU 使用率和4％ 内存的使用。然而在数据库中，最常见的是默认使用像B树一样的有序索引。

为什么编程语言和数据库之间“默认”的选择不同呢？传统的答案是：数据存储在内存中时使用哈希表的读取效率很高；而 B 树的设计理念是充分利用磁盘中块（ Block ）的作用，所以对于编程语言而言，读取效率比较低。事实上，不仅有用于磁盘的哈希表（例如 MySQL 的哈希索引）以及在内存中的树结构（例如 Java 的 TreeMap ），因此传统的答案不够完善。

在本文中，作者认为更好的答案是 B 树的“通用性”更好。比如对于数据库而言，它经常会遇到需要持久化的大量数据，此时 B 树所消耗的“总成本”较低。换句话说，虽然对于单值查找而言，B 树等有序数据结构的数据读取速度较慢，但在考虑到范围查询操作和构建联合索引的成本时，B 树会是更好选择。

哈希表和树结构的比较

在给出答案之前，先来看看哈希表和树结构的差别。

计算复杂度

从计算复杂度来说，哈希表对于单个值的读取时间恒定为 O(1)，而树结构的读取时间为 O(log n) 。这意味着无论数据存储在何处，对于单值查找而言，哈希表都会更快。但是树结构因为索引内的值是有序的，所以无论是单值查找还是范围查找，效果都差不多。简单来说，当需要找到所有以给定前缀开头的值或“前 k 个”值，树结构的读取时间永远是 O(log n)；使用哈希表结构的话，则需要扫描整个表。

读取速度的稳定性

哈希表虽然对于单值查找而言，读取的时间是恒定的，但是可能会存在哈希冲突，以至于需要重新哈希。并且随着数据库里表数据量的增长，哈希冲突的可能性会更大，每一次的重新哈希则需要 O(n) 的时间，对性能造成极大的影响，而树结构的最坏情况也就是 O(log n)。

持久化数据和内存数据

数据库需要存储的数据通常都需要持久化，编程语言仅仅只是临时存储数据，因此数据库会存储更多的数据。基于这种事实和下面的原因，数据库的默认项选择了使用 B 树结构。

1. 当数据量很少时，选择哪种数据结构都没关系。

编程语言中大多数使用的哈希表存储的数据量都很小，只有数千个元素，甚至更少。因此，O(1)，O(log n)和O(n)之间的复杂度差异无关紧要。因此，所以在编程语言中，常常会遇到单值查找，使用哈希表读取速度会更快，而很难遇到全表扫描。但是随着数据量的变大，遇上全表扫描时花 O(n) 来查找值会慢的难以接受。

这是经典的 O(n) 与 O(log n) 比较图。从图中看，意味着对于大数据集而言，有序数据结构有着更“平衡”的性能。

2. 存储不是免费的

注意，建立索引是需要额外空间的。当数据量较少时，无论怎么构建索引、构建多少索引，存储的成本都比较低；当数据量变大时，添加新的索引至少会花费 O(n) 的存储空间和 O(n) 的构建时间。比如在数据库上的一张超级大表上添加新的二级索引可能要花费数小时或数天。因此，索引要尽可能的可重复利用，以适应各种不同的查询条件，这种好处会随数据量的增大而增大。这个时候，使用有序索引就体现出优势来了，因为数据库有很多种不同的方式来尽可能地使用树结构的有序属性。数据库可以创建多于一列的联合索引，以（位置，商店名称）构建索引，然后这个索引可以访问一个特定的（位置，商店名称），还可以记录单个（位置）甚至位置键的前缀。而对于哈希表，则需要针对每一列构建单独的索引。

3. 持久化的存储更复杂

将数据存储在磁盘上，即使遇上机器崩溃也不会损坏和丢失数据是一件非常困难的事。开发者对数据的写入进行排序，使用预写日志，并且还要解决细粒度的并发问题。因为与将数据写入内存相比，将数据写入磁盘开发者需要写更多的代码。这导致了许多数据库仅支持一种类型的索引。在这种情况下，要保证这种索引尽可能的适用于各种类型的查询和写入方式。

也因为引入了这种额外的复杂度（比如通过网络发送请求，对数据进行解码等等），O(1)和O(log n)的读取速度就没有那么大差别了。

4. 存储的位置很重要

在计算机中，数据存储的位置总是很重要的。在计算机分层结构中，使用 数据命中 L1 缓存时间约为1 ns，内存大约需要100 ns，SSD随机读取大约为15 us，磁盘随机读取大约为2ms。在哈希表中，大部分都是随机访问，所以存储在哪里就不是很重要了，很难进行缓存；但是使用树等有序数据结构，根据局部性原理，数据库在可以按磁盘中的块（Block）缓存数据到内存中，提升后续查询数据的效率。当然这种优化有好有坏，取决于开发者遇到的情况。

结论

综上所述，在编程语言中使用哈希表，在数据库中使用有序数据结构是一种正确的默认选项。