B- 树 VS 哈希表

在 MySQL 中，索引类型是 b-tree，访问 b-tree 中的元素的对数分摊时间为 O(log(n))。

另一方面，在 O(1)中访问散列表中的元素。

为什么不使用哈希表来代替 b 树来访问数据库中的数据？

100374 次浏览
小开

哈希表的时间复杂度仅对于大小足够的哈希表是常数(需要有足够的存储桶来存储数据)。数据库表的大小事先并不知道，因此必须不时地对表进行重新散列以获得散列表的最佳性能。换汤不换药也很昂贵。

小开

我认为散列映射不能很好地扩展，而且当整个映射需要重新散列时会很昂贵。

小开
最佳答案

只能通过哈希表中的主键访问元素。 这比树算法(ABC0而不是 log(n))快，但是不能选择范围(在 ABC2和 y之间的所有东西)。 树算法在 Log(n)中支持这一点，而散列索引可以导致完整的表扫描 O(n)。 此外，哈希索引的常数开销通常更大(它不是 θ 符号中的因子，但它仍然存在)。 此外，树算法通常更容易维护，增长与数据，规模等。

散列索引与预定义的散列大小一起工作，因此您最终会得到一些存储对象的“桶”。这些对象被重新循环以在这个分区中找到正确的对象。

因此，如果你有小尺寸，你有很多开销为小元素，大尺寸的结果进一步扫描。

如今，哈希表算法通常是可伸缩的，但是可伸缩性可能是低效的。

确实存在可伸缩的哈希算法。不要问我这是怎么回事——对我来说也是个谜。AFAIK 是从可扩展复制演变而来的，在那里重新散列并不容易。

它被称为 RUSH-R复制 美国nder 是的可调 Hash，因此这些算法被称为 RUSH 算法。

然而，可能有一个点，您的索引超过了一个可容忍的大小相比，您的散列大小和您的整个索引需要重新生成。通常这不是一个问题，但是对于巨大巨大的数据库来说，这可能需要几天的时间。

树算法的折衷是很小的，它们适合几乎所有的用例，因此是默认的。

但是，如果您有一个非常精确的用例，并且您确切地知道需要什么，并且只知道需要什么，那么您可以利用散列索引。

小开

实际上，根据下面的 链接，MySQL 似乎使用了两种索引: 哈希表或 b 树。

使用 b-tree 和散列表的区别在于，前者允许在使用 = 、 > 、 > = 、 < 、 < = 或 BETWEEN 运算符的表达式中使用 列比较，而后者使用使用 = 或 < = > 运算符的 只是为了进行等式比较。

小开

PickDB/OS 基于散列，运行良好。现在有了更多的内存来支持高效的稀疏哈希表，以及冗余哈希来支持适度的范围查询，我想说哈希可能还有它的位置(有些人宁愿使用其他形式的非范围相似性匹配，比如通配符和 regexp)。我们还建议在内存层次结构速度差异很大时进行复制，以保持冲突链连续。

小开

除了这里的好答案之外，这里还有一些关于如何构建数据库的观点。

首先，强壮散列表通常使用桶式系统完成，例如，在用于实现 JavaScript“对象”(即散列表)的 二次探测中。您可以在 JavaScript给你中看到一个桶式散列表实现。

您会注意到，在这个实现中，进行的处理要比使用 O(1)符号所看到的多得多。首先，通过哈希函数运行它，这个函数是 迭代输入字符串的长度，每次迭代有5 + 个计算步骤。但是请注意，这些都是快速的计算步骤，因为它们都是在寄存器中完成的，而不是在 RAM 中。接下来，使用该散列值获取 水桶。我不确定存在多少个 bucket，或者一个 bucket 有多长，但是 bucket 是一个数组或链表。因此，您可以遍历 bucket 项，并将每个项与要获取值的输入键进行比较。这也是一个字符串比较。因此，我估计，即使是一个简单的字符串从散列表中获取它，也至少需要100个计算步骤。所有这些字符串比较加起来。

此外，桶可能是半空的，这占用了大量无用的空间。最后，当哈希表在占用中达到一定大小时，它的大小必须加倍！它必须重新处理和重新计算一切。这可能会在 UI 应用程序中引起明显的小故障。

另一方面，B + 树是一种更紧凑的数据结构。你仍然在做字符串比较，但你只是跳转 MAX 我会说20个链接在树(就深度而言) ，然后扫描子节点在最后一个树找到精确的匹配。

从这个意义上说，我认为在现实中，B + 树或 B-树的性能将与哈希表相当，特别是幼稚的实现。这两个系统都可以进行优化和微调，我仍然认为它们将接近相同。只有测试才能知道。但是树的优势在于更紧凑的内存。经过长时间的思考，权衡了方程的各个方面之后，我打算选择 B + 树作为 按键查找项目的理想解。

小开
  • MySQL 只在几种情况下支持 HASH: ENGINE=MEMORY(很少使用)和 在内部用于“ HASH-join”。
  • 即使当您要求 InnoDB 表具有 HASH 索引时，它也会悄悄地将其转换为 BTree。
  • 散列表示 差不多到 O (1) ，但从技术上讲，在最坏的情况下它更像 O (N ^ 2)。这是因为需要处理“冲突”。
  • MySQL 选择 BTree 是因为它比 Hash 更灵活(因为它可以处理范围) ，而不是比 Hash 慢很多。
  • 可以说，由于块的缓存，BTree 比 O (1)慢。非叶节点倾向于缓存并保留在 RAM 中，即使叶节点来来去去(对于大型表)也是如此。
  • MySQL维持是一个动态的 BTree; 当 可以请求重新构建索引(cfOPTIMIZE)时，很少值得这样做。
  • 在 InnoDB。数据存储在按 PRIMARY KEY排序的 BTree 中。辅助键也存储在单独的 Btree 中，但是按照辅助键列排序。叶节点中唯一的其他信息是 PRIMARY KEY值。因此，辅助键查找需要两个 BTree 查找(除非所有必要的列都在辅助 + 主列中——这称为“覆盖”)。

最后，我想说 Big-O 可能很有趣，但是实现的细节增加了复杂性。以及任意大型表的性能。

小开

另一个可能影响选择的因素是: 散列表可以很好地将键映射到单个值。但是，在一个键映射到大量元素(对于表的单列来说非常常见)的情况下，您可能很容易丢失 O (1)行为，具体取决于它如何处理它。Btree 没有这个问题，并且能够很好地处理大量的重复条目。


提交答案