B树与哈希表

在MySQL中,索引types是b树,访问b树中的元素是处于对数分摊时间O(log(n))

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

为什么不使用散列表而不是b-tree来访问数据库中的数据?

您只能通过散列表中的主键访问元素。 这比使用树algorithm( O(1)而不是log(n) )快,但是不能select范围( xy之间的所有东西 )。 树algorithm在Log(n)中支持这一点,其中作为散列索引可以导致全表扫描O(n) 。 散列索引的常量开销通常也是较大的( 这在θ表示中是没有影响的,但它仍然存在 )。 另外树algorithm通常更容易维护,与数据,规模等成长。

哈希索引以预定义的哈希大小工作,所以最终会得到一些存储对象的“桶”。这些对象再次循环,以便在该分区内find正确的哈希。

所以如果你有小尺寸的话,对于小的元素来说就会有很多的开销,大的尺寸会导致进一步的扫描。

今天的哈希表algorithm通常会缩放,但缩放可能是低效的。

确实有可扩展的哈希algorithm。 不要问我怎么做 – 对我来说也是一种莫名其妙的感觉。 AFAIK他们从可扩展的复制发展而来,其中重新哈希是不容易的。

它被称为RUSHR表示U nder S可用Hashing,这些algorithm因此被称为RUSHalgorithm。

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

树algorithm的权衡很小,几乎适用于所有用例,因此是默认的。

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

实际上,MySQL似乎根据下面的链接使用了这两种索引,哈希表或b-tree。

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

因为一个btree可以很容易地分页到磁盘。 另外,哈希表的时间复杂度只有在足够大的哈希表(需要足够的桶来存放数据)时才是常量。 数据库表的大小并不是事先知道的,所以表必须不时地重新映射,然后才能从散列表中获得最佳性能。 重新调整也是昂贵的。

我认为,HashMap不能很好地扩展,当整个地图需要重新整理时,可能会很昂贵。