B树与哈希表

在MySQL中，索引类型是b树，访问b树中的元素处于对数分期时间O(log(n))。B树与哈希表

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

为了访问数据库内的数据，为什么不使用散列表代替b-树？

2011-09-05 JohnJohnGa

哈希表不支持范围查询，并且在操作期间无法平稳地增长或收缩。 –

@HenningMakholm为什么不为需要范围查询的列散列？ – Pacerier

您只能通过散列表中的主键访问元素。这比一树算法（O(1)而不是log(n)）更快，但你不能选择的范围（一切x和y之间）。树算法在Log(n)中支持该算法，其中作为散列索引可导致全表扫描O(n)。散列索引的常量开销通常更大（，这在θ表示中没有影响，但仍然存在）。另外，树算法通常更容易维护，与数据，比例等一起增长。

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

所以，如果你有小尺寸的小元件会有很多开销，大尺寸会导致进一步的扫描。

今天的哈希表算法通常会缩放，但缩放可能是低效的。

确实存在可扩展的散列算法。不要问我怎么做 - 对我来说也是一种神秘感。 AFAIK他们从可扩展复制发展而来，其中重新哈希不容易。

其所谓RUSH - ř eplication ù的nDer 小号 calable ħ灰化，因此这些算法被称为算法RUSH。

然而，与您的散列大小相比，您的索引可能会超出容许的大小，并且您的整个索引需要重新构建。通常这不是问题，但对于巨大而庞大的数据库，这可能需要几天时间。

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

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

来源

2011-09-05 09:58:30

你能解释一下索引重建的更多内容吗？这是否意味着在索引重建的x天内，该表在此期间完全无法使用？ – Pacerier

依赖于正在使用的数据库系统。这个问题只涉及理论上的参照。我真的不知道常用数据库系统的实现细节。但通常情况并非如此，因为第二个索引可以在第一个索引仍在使用时生成 –

散列表的时间复杂度只有足够大的散列表（需要足够的存储桶来存放数据）才是常量。数据库表的大小事先是未知的，所以必须立即重新映射表，然后才能从散列表中获得最佳性能。重新粉碎也很昂贵。

来源

2011-09-05 09:48:12

数据库联机时可以执行重新转换吗？或者我们必须锁定表格来重新扫描一切吗？ – Pacerier

Pacerier，MySQL不支持散列索引。理论上可以在数据库仍然在线时重新编制索引（继续使用旧索引，创建新索引，完成后切换到新索引），但是我不知道MySQL如果实现散列标记。 –

MySQL支持散列索引吧？：http://dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html – Pacerier

我认为散列图不能很好地扩展，并且在整个地图需要重新整理时可能会很昂贵。

来源

2011-09-05 09:48:53

实际上，根据以下link，MySQL似乎使用了这两种索引或者哈希表或b-tree。

使用B树和哈希表之间的差异在于，前者允许您使用列的比较在使用表达式=，>，> =，<，< =之间，或运营商，而后者仅用于，用于使用=或< =>运算符的相等性比较。

来源

2016-05-19 21:23:03 lmiguelvargasf

这是不公平的。最好的答案是最低的分数。 –

这正是我正在寻找的。我关心它如何影响我的查询，而不是技术分析。 –

回答

相关问题