B-树与哈希表的比较

Question

B-树与哈希表的比较

mysqldata-structurescomputer-sciencecomplexity-theoryb-tree

165

在MySQL中，索引类型是B-tree，访问B-tree中的元素是以对数摊销时间O(log(n))完成。

另一方面，在哈希表中访问元素是以O(1)完成的。

为什么在数据库中访问数据时不使用哈希表而使用B-tree呢？

- JohnJohnGa

14

哈希表不支持范围查询，在操作过程中也不能平滑地增长或缩小。 - hmakholm left over Monica

4

为什么不对不需要范围查询的列使用哈希？ - Pacerier

8个回答

168

实际上，MySQL似乎会根据以下链接使用哈希表或B-tree索引。

使用B-tree和哈希表的区别在于前者允许您在使用=、>、>=、<、<=或BETWEEN运算符的表达式中使用列比较，而后者仅用于使用=或<=>运算符的相等性比较。

- lmiguelvargasf

15

不公平，最佳答案得分最低。 - Андрей Беньковский

7

这正是我在寻找的。我关心的是它对我的查询产生了什么影响，而不是技术分析。 - Ben Dehghan

没错！这个答案对我帮助最大。 - Ron Ross

非常感谢，虽然已经很久了，但这个答案对我也帮助很大。 - Reham Fahmy

唯一有意义的答案是，在哈希表键中始终可以实现列表，开销与B-树没有区别，只是B-树没有选择。此外，永远无需在运行时重建哈希表，您可以制作更多的哈希表（逐步添加总寻找时间）并离线重建。这里的主要考虑因素是，哈希表需要更多的提前规划，但在我的看法中，如果足够考虑它们，就可以实现更优异的结果。 - user81993

延续“这对我有什么影响？”的趋势：引用链接包括B树和哈希表索引之间的一个重要区别：“只能使用整个键来搜索行。（使用B树索引可以使用任何最左前缀来查找行。）” - rinogo

17

哈希表的时间复杂度仅在具有足够大小的情况下才能保持常数级别（必须有足够的桶来容纳数据）。由于数据库表的大小事先未知，因此必须不时地重新散列表格以获得哈希表的最佳性能。重新散列也是昂贵的。

- Emil Vikström

2

在数据库在线的情况下，是否可以进行重新哈希操作？还是我们必须锁定表格来重新哈希所有内容？ - Pacerier

1

Pacerier，MySQL 不支持哈希索引。在数据库仍在线的情况下，理论上可以重新生成索引（继续使用旧索引、创建新索引，并在完成后切换到新索引），但我不知道如果 MySQL 实现了哈希索引会发生什么。 - Emil Vikström

3

MySQL支持哈希索引，对吗？：http://dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html - Pacerier

1

你说得对。我的答案实际上是错误的。如果我今天回答这个问题，我会像在MongoDB的这个答案中那样，解释为什么B树在实践中具有有效的O(1)查找。 - Emil Vikström

1

@EmilVikström - MongoDB 的论点也适用于 MySQL，但使用的是约为 log_100 的值。（InnoDB 的扇出规则是 100；十亿行需要 5 层。） - Rick James

显示剩余2条评论

8

我认为哈希映射在扩展性方面存在问题，当整个映射需要重新哈希时可能会很昂贵。

- Jonathan Weatherhead

8

MySQL只在少数情况下支持HASH： ENGINE=MEMORY（很少使用）和内部用于“hash-join”。
即使您要求InnoDB表具有HASH索引，它也会悄悄地将其转换为BTree。
Hash接近O(1)，但在最坏情况下技术上更像是O(N^2)。这是因为需要处理“碰撞”。
MySQL选择BTree，因为它比Hash更灵活（因为它可以处理范围），而且不比Hash慢多少。
BTree由于块的缓存而较O(1)慢。非叶节点倾向于被缓存并保留在RAM中，即使叶节点来去不定（对于大型表）。
MySQL动态地维护BTree；虽然您可以要求重建索引（参见OPTIMIZE），但这很少值得努力。
InnoDB中，数据按PRIMARY KEY排序存储在BTree中。二级索引也存储在单独的BTrees中，但按二级键列排序。叶节点中仅包含PRIMARY KEY值。因此，二级键查找需要两个BTree查找（除非所有必要的列都在二级+主列中 - 这称为“覆盖”）。

我得出的结论是，Big-O可能很有趣，但实现的细节增加了复杂性。并且对于任意大的表性能也很重要。

- Rick James

MariaDB正在为TEXT/BLOB上的UNIQUE功能开发HASH，但实际上这是使用哈希键的BTree。 - Rick James

6

除了这里的好答案外，在思考如何构建数据库时，以下是一些观点。

首先，强大的哈希表通常使用桶系统完成，例如在Quadratic Probing中使用，该方法用于实现JavaScript“对象”（即哈希表）。您可以在here中查看JavaScript中的桶哈希表实现。

在这个实现中，你会发现比 O(1) 表示法更多的处理过程。首先，你需要运行它通过哈希函数，这个函数会迭代输入字符串的长度，并且每次迭代都有五个或以上的计算步骤。需要注意的是，这些步骤很快，因为它们都在寄存器中完成，而不是在RAM中。接下来，你使用哈希值来获取一个桶(bucket)。我不确定有多少个桶(bucket)，或者每个桶(bucket)的长度是多少，但是桶(bucket)是一个数组或链表。然后，你需要遍历桶(bucket)中的项目，并将每个项目与要获取值的输入键进行比较。这又是一个字符串比较。所以，即使是简单的字符串从哈希表中获取值，至少也需要100个计算步骤。所有这些字符串比较加起来就会很多。

此外，桶(bucket)可能只填充了一半，这占用了很多无用的空间。最后，当哈希表达到一定的占用大小时，它必须扩大两倍！它必须重新处理和重新计算所有内容。这可能会导致UI应用程序出现明显的故障。

B+树是一种更紧凑的数据结构。您仍然在进行字符串比较，但是只需在树中跳转MAX（我会说20个）链接（按深度计算），然后扫描最后一个树节点中的子项以查找精确匹配项。

从这个意义上讲，我认为实际上B+树或B树将与哈希表表现相当，特别是天真的实现。两个系统都可以进行优化和微调，我仍然认为它们将接近相等。只有测试才能说明问题。但是，树具有更紧凑的内存优势。因此，在长时间思考并权衡方程式的每个方面后，我将选择B+树作为快速“按键查找项目”的理想解决方案。

- Lance

0

另一个可能影响选择的因素是：哈希表适用于将一个键映射到一个单一值。然而，在一个键映射到大量元素的情况下（对于表的单个列非常常见），根据它的处理方式，您很容易失去O(1)的行为。B树没有这个问题，并且能够出色地处理大量重复条目。

- saolof

几乎不可能制作一个总是映射到完全不同值的哈希函数。用于索引目的的哈希不必担心这一点。也就是说，在任何哈希实现中都可能发生一些冲突。因此，“通常情况下是O(1)”。 - Rick James

InnoDB的PRIMARY KEY BTree必然没有重复项（PK是唯一的）。次要索引隐式包含PK，因此它们也没有重复项。 - Rick James

0

Pick DB/OS基于哈希，运行良好。如今有更多的内存来支持高效的稀疏哈希表，并且冗余哈希以支持适度范围查询，我认为哈希可能仍然有其用武之地（有些人可能更喜欢其他形式的非范围相似匹配，例如通配符和正则表达式）。我们还建议进行复制，以使碰撞链在内存层次结构具有大的速度差异时保持连续。

- RONALD LOUI

非常好的答案，为我们提供了一个不同的角度来思考哈希表。 - Hasnat Safder

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- The Surrican · Accepted Answer

在散列表中，只能通过主键来访问元素。相比于树状算法（O(1)而不是log(n)），这种方式更快，但无法选择范围（介于x和y之间的所有元素）。树状算法支持Log(n)的范围查询，而哈希索引可能导致全表扫描O(n)。此外，哈希索引的定值开销通常更大（在theta符号中没有因素，但它仍然存在）。另外，树状算法通常更易于维护、随数据增长、扩展等。哈希索引使用预定义的哈希大小，因此您最终会得到一些“桶”，对象存储在其中。这些对象再次循环以真正找到该分区内正确的对象。因此，如果尺寸较小，则小元素将有很大的开销，而较大的尺寸则会导致进一步扫描。现今的哈希表算法通常是可扩展的，但扩展可能效率低下。

确实有可扩展的哈希算法。别问我它是如何工作的——对我来说也是一个谜。据我所知，它们起源于可扩展的复制，在这种情况下，重新哈希不容易。

它被称为 RUSH - Replication Under Scalable Hashing，而这些算法因此被称为 RUSH 算法。

然而，如果索引超过了与哈希大小相比可以容忍的尺寸，那么您的整个索引需要重建。通常这不是问题，但对于非常大的数据库，这可能需要花费数天时间。树状算法的折衷方案很小，适用于几乎所有的用例，并且因此是默认的。但是，如果您有一个非常精确的用例，并且您确切地知道将需要什么，那么您可以利用哈希索引。