B树与哈希表
在MySQL中，索引types是b树，访问b树中的元素是处于对数分摊时间O(log(n)) 。
另一方面，访问哈希表中的元素在O(1) 。
为什么不使用散列表而不是b-tree来访问数据库中的数据？
您只能通过散列表中的主键访问元素。 这比使用树algorithm（ O(1)而不是log(n) ）快，但是不能select范围（ x和y之间的所有东西 ）。 树algorithm在Log(n)中支持这一点，其中作为散列索引可以导致全表扫描O(n) 。 散列索引的常量开销通常也是较大的（ 这在θ表示中是没有影响的，但它仍然存在 ）。 另外树algorithm通常更容易维护，与数据，规模等成长。
哈希索引以预定义的哈希大小工作，所以最终会得到一些存储对象的“桶”。这些对象再次循环，以便在该分区内find正确的哈希。
所以如果你有小尺寸的话，对于小的元素来说就会有很多的开销，大的尺寸会导致进一步的扫描。
今天的哈希表algorithm通常会缩放，但缩放可能是低效的。
确实有可扩展的哈希algorithm。 不要问我怎么做 – 对我来说也是一种莫名其妙的感觉。 AFAIK他们从可扩展的复制发展而来，其中重新哈希是不容易的。
它被称为RUSH – R表示U nder S可用Hashing，这些algorithm因此被称为RUSHalgorithm。
但是，与您的散列大小相比，您的索引可能会超出容许的大小，并且您的整个索引需要重新构build。 通常这不是一个问题，但是对于巨大而庞大的数据库来说，这可能需要几天的时间。
树algorithm的权衡很小，几乎适用于所有用例，因此是默认的。
但是，如果你有一个非常精确的用例，而且你确切地知道什么是需要的，你可以利用散列索引。
实际上，MySQL似乎根据下面的链接使用了这两种索引，哈希表或b-tree。
使用b-tree和哈希表的区别在于，前者允许您在使用=，>，> =，<，<=或BETWEEN运算符的expression式中使用列比较 ，而后者仅用于使用=或<=>运算符的等式比较 。
因为一个btree可以很容易地分页到磁盘。 另外，哈希表的时间复杂度只有在足够大的哈希表（需要足够的桶来存放数据）时才是常量。 数据库表的大小并不是事先知道的，所以表必须不时地重新映射，然后才能从散列表中获得最佳性能。 重新调整也是昂贵的。
我认为，HashMap不能很好地扩展，当整个地图需要重新整理时，可能会很昂贵。
