为什么DB索引使用平衡树,而不是哈希表？

Question

就磁盘访问而言,Hashtables似乎更受欢迎.索引通常用树实现的真正原因是什么？对不起,如果它是婴儿,但我没有找到关于SO的直接答案.

Answer 1

尺寸,btree开始小而且完美成型,并且很好地适应了巨大的尺寸.哈希具有固定的大小,对于您拥有的数据量,它可能太大(10,000个条目为1000个条目)或太小(10,000个桶用于1,000,000,000个条目).

Answer 2

数据的常见操作之一是对其进行排序或搜索范围内的数据 - 树将按顺序包含数据,而哈希表仅用于查找行并且不知道下一行是什么.

因此,由于这个答案,哈希表对于这种常见情况并不好

SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000

要么

SELECT * FROM MyTable ORDER BY x

显然有些情况下哈希表更好,但最好先处理主要情况.

Answer 3

哈希表对此案例没有任何好处:

SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000

Answer 4

只需查看与存储引擎相关的MySQL 哈希索引实现，MEMORY即可了解其缺点：

1. 它们可以与等式运算符一起使用，例如=但不能与比较运算符一起使用，例如<
2. 优化器不能使用哈希索引来加速 ORDER BY 操作。
3. 只能使用整个键来搜索一行。（对于 B 树索引，键的任何最左边的前缀都可用于查找行。）
4. 优化器无法确定两个值之间大约有多少行（范围优化器使用它来决定使用哪个索引）。

请注意，上述内容适用于在内存中实现的哈希索引，而没有额外考虑与在磁盘上实现的索引相关的磁盘访问问题。@silentbicycle 指出的磁盘访问因素会使它更倾向于平衡树索引。