B树与哈希表

Question

在MySQL中,索引类型是b树,并且访问b树中的元素是以对数分摊的时间O(log(n)).

另一方面,访问哈希表中的元素O(1).

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

Answer 1

您只能通过哈希表中的主键访问元素.这比用树算法(更快O(1)的替代log(n)),但你不能选择的范围(之间的一切x和y).树算法支持这一点,Log(n)而哈希索引可以导致全表扫描O(n).哈希索引的常量开销通常也更大(这不是theta表示法的因素,但它仍然存在).树算法通常更容易维护,随数据,规模等增长.

散列索引使用预定义的散列大小,因此您最终会得到一些存储对象的"存储桶".这些对象再次循环,以便在此分区中找到正确的对象.

因此,如果您的尺寸较小,则对于小尺寸元件会产生大量开销,因此大尺寸会导致进一步扫描.

今天的哈希表算法通常可以缩放,但缩放可能效率低下.

确实存在可扩展的散列算法.不要问我这是怎么回事 - 这对我来说也是一个谜.AFAIK是从可扩展复制发展而来的,其中重新散列并不容易.

它被称为RUSH - R eplication U nder S calable H ashing,因此这些算法被称为RUSH算法.

但是,与您的散列大小相比,您的索引可能超出了可容忍的大小,并且需要重新构建整个索引.通常这不是问题,但对于巨大的巨大数据库,这可能需要数天时间.

树算法的权衡很小,它们几乎适用于所有用例,因此是默认的.

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

Answer 2

实际上,似乎MySQL根据以下链接使用散列表或b树这两种索引.

使用b-tree和哈希表之间的区别在于前者允许你在使用=,>,> =,<,<=或BETWEEN运算符的表达式中使用列比较,而后者仅用于使用=或<=>运算符的等式比较.

Answer 3

哈希表的时间复杂度仅对于足够大小的哈希表是恒定的(需要有足够的桶来保存数据).事先不知道数据库表的大小,因此必须立即对表进行重新分析,以便从哈希表中获得最佳性能.重组也很昂贵.

Answer 4

• MySQL 仅在几种情况下支持 HASH：（ ENGINE=MEMORY很少使用）和内部“散列连接”。
• 即使当你要求 InnoDB 表有一个 HASH 索引时，它也会默默地把它变成 BTree。
• 哈希值接近O(1)，但从技术上讲，在最坏的情况下它更像是 O(N^2)。这是因为需要处理“碰撞”。
• MySQL 选择 BTree 是因为它比 Hash 更灵活（因为它可以处理范围），同时并不比 Hash 慢很多。
• 可以说，由于块的缓存，BTree 的速度比 O(1) 慢。非叶节点往往会被缓存并保留在 RAM 中，即使叶节点来来往往（对于大型表）。
• MySQL动态维护BTree；虽然您可以要求重建索引（cf OPTIMIZE），但这很少值得付出努力。
• 在InnoDB中。数据存储在按 排序的 BTree 中PRIMARY KEY。辅助键也存储在单独的 BTree 中，但按辅助键列排序。叶节点中唯一的其他信息是PRIMARY KEY值。因此，辅助键查找需要两次 BTree 查找（除非所有必要的列都在辅助列+主列中——这称为“覆盖”）。

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

Answer 5

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

首先，健壮的哈希表通常使用分桶系统来完成，例如用于实现 JavaScript“对象”（即哈希表）的二次探测。您可以在此处查看 JavaScript 中的分桶哈希表实现。

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

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

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

从这个意义上说，我认为实际上 B+ 树或 B 树将与哈希表执行相同的操作，尤其是简单的实现。这两个系统都可以优化和微调，而且我仍然认为它们将接近平等。只有测试才能证明。但树的优点是内存更紧凑。因此，在思考了很长一段时间并权衡了等式的各个方面之后，我将选择 B+ 树作为通过键快速查找项目的理想解决方案。

Answer 6

我认为Hashmaps也不会扩展,并且当需要重新整理整个地图时可能会很昂贵.