MySQL中的hash index

• • 一、散列表（哈希表）
  • 二、Hash 索引
  • 三、InnoDB 中的自适应哈希索引
  • 四、总结

题外话

前几天有人问到MongoDB的hash分片是怎么实现的，当时记忆有些模糊，联想到了mysql的hash索引，故简单整理了此文。MongoDB的hash分片介绍可参考我另一文章：https://blog.csdn.net/tah_001/article/details/108690215

一、散列表（哈希表）

散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列表,它是基于高速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构能够理解为一个线性表，可是当中的元素不是紧密排列的，而是可能存在空隙。

散列方法的主要思想是根据结点的关键码值来确定其存储地址：以关键码值K为自变量，通过一定的函数关系h(K)(称为散列函数)，计算出对应的函数值来，把这个值解释为结点的存储地址，将结点存入到此存储单元中。检索时，用同样的方法计算地址，然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列（hash，也称“哈希”）是一种重要的存储方式，也是一种常见的检索方法。

二、Hash 索引

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希码索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有他的限制：

1）哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行，不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。

2）哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序

3）哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。

4）哈希索引只支持等值比较查询，包括=、IN()、<=>、也不支持任何范围查询。

5）访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。

6）如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。 

因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。举个例子，在数据仓库应用中有一种经典的“星型” schema，需要关联很多查找表，哈希索引就非常适合查找表的需求。

除了Memory引擎外，NDB集群引擎也支持唯一哈希索引，且在NDB集群引擎中作用非常特殊。

三、InnoDB 中的自适应哈希索引

InnoDB 引擎有一个特殊额功能叫做“自适应哈希索引”，当 InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引页具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过若果有必要，完全可以关闭该功能。

四、总结

上文可以知道hash index的效率非常高，但在mysql中限制也很多，所以我们应按实际情况合理使用；最后借鉴一匿名网友生动的描述，理解一下hash算法：（借鉴地址：https://zhidao.baidu.com/question/548095906.html）

假如我们有很多的小猪，每个4102的体重都不一样，假设体重分布比较平均(我们考虑到公斤级别)，我们按照体重来分,划分成100个小猪圈。
然后把每个小猪，按照体重赶进各自的猪圈里，记录档案。 好了，如果我们要找某个小猪怎么办呢？我们需要每个猪圈，每个小猪的比对吗？
当然不需要了。 我们先看看要找的这个小猪的体重，然后就找到了对应的猪圈了。
在这个猪圈里的小猪的数量就相对很少了。
我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。 对应于hash算法。
就是按照hashcode分配不同的猪圈，将hashcode相同的猪放到一个猪圈里。
查找的时候，先找到hashcode对应的猪圈，然后在逐个比较里面的小猪。 所以问题的关键就是建造多少个猪圈比较合适。 如果每个小猪的体重全部不同（考虑到毫克级别)，每个都建一个猪圈，那么我们可以最快速度的找到这头猪。缺点就是，建造那么多猪圈的费用有点太高了。 如果我们按照10公斤级别进行划分，那么建造的猪圈只有几个吧，那么每个圈里的小猪就很多了。我1653们虽然可以很快的找到猪圈，但从这个猪圈里逐个确定那头小猪也是很累的。 所以，好的hashcode，可以根据实际情况，根据具体的需求，在时间成本(更多的猪圈，更快的速度)和空间本(更少的猪圈，更低的空间需求)之间平衡。

哎哟，不错噢！ - - - - - - 欢迎指出有误的地方以及补充更好的方法