mysql - B树与哈希表

Question

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

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

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

Answer 1

您只能通过哈希表中的主键访问元素。这比使用树算法(O(1) 而不是 log(n))要快，但您不能选择范围( x 和 y 之间的所有内容)。树算法在 Log(n) 中支持这一点，而哈希索引可以导致全表扫描 O(n)。此外，哈希索引的恒定开销通常更大(这不是 theta 表示法的因素，但它仍然存在)。此外，树算法通常更易于维护、随着数据、规模等增长。

哈希索引与预定义的哈希大小一起使用，因此您最终会得到一些存储对象的“桶”。这些对象会再次循环以在此分区内真正找到正确的对象。

因此，如果您的尺寸较小，则小元素的开销会很大，大尺寸会导致进一步扫描。

如今的哈希表算法通常可以扩展，但扩展可能效率低下。

There are indeed scalable hashing algorithms. Don't ask me how that works - its a mystery to me too. AFAIK they evolved from scalable replication where re-hashing is not easy.

Its called RUSH - Replication Under Scalable Hashing, and those algorithms are thus called RUSH algorithms.

但是，与您的哈希大小相比，您的索引可能会超过一个可容忍的大小，并且您的整个索引需要重新构建。通常这不是问题，但对于庞大的数据库，这可能需要几天时间。

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

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