MySQL的默认索引结构是B+树，也可以指定索引结构为HASH或者R树等其他结构来适应不同的检索需求。这里我们来介绍MySQL哈希索引。
MySQL哈希索引又基于哈希表（散列表）来实现，所以了解什么是哈希表对MySQL哈希索引的理解至关重要。接下来，我们来一步一部介绍哈希表。
1.数组
数组是最常用的数据结构，是一种线性表的顺序存储方式，由下标（也叫索引）和对应的值构成。数组在各个开发语言以及数据库中都有类似的结构，类似下图1：
图1展示了一个一维整数数组，数组的长度为10，下标从0-9，每个下标对应不同的值。每种编程语言基本上都有数组，大部分数据库也提供了数组或者是类似数组的结构，MySQL也有数组，以下为MySQL的一维数组：
mysqlselect
aasarray,json_length(a)asarray_size;+-------------------------------------------+------------+
array
array_size
[10,20,30,40,50,60,70,80,90,]
10
1rowinset(0.00sec)
数组元素也可以是数组，这样的表示称为多维数组，如图2，一个二维字符串数组：
以下为MySQL里的多维数组：
mysqlselectjson_pretty(
a)\G***************************1.row***************************
json_pretty(
a):[[
mysql,
db2
],
oracle,
mongodb,
sqlserver,
redis
memcached,
dble,
postgresql,
mariadb
]
]
1rowinset(0.01sec)
数组优缺点如下，
优点：
数组最大的优点是可以根据下标来快速读取到对应的值，通俗的说法就是时间复杂度为O(1)。
缺点：
1）对数组的写入（插入或者删除）要涉及到原下标对应值的迁移以及新下标的生成；
2）数组存储需要一块连续的存储区域，后期数组扩容需要申请新的连续存储区域，造成空间浪费。
2.字典
字典和数组结构类似，不同的是，下标并非是从0开始的数字，而是任意的字符串。有的程序语言里把字典也叫数组，由Key映射为对应的value，字典的结构类似于图2：
MySQL也同样提供了这样的字典，比如下面定义了一个字典，存入变量
a，把图2里前4个元素拿出来，对应的value分别为“mysql,db2,oracle,mongodb.mysqlset
a={10:mysql,20:db2,30:oracle,40:mongodb};QueryOK,0rowsaffected(0.00sec)
mysqlselectjson_keys(
a);+--------------------------+
json_keys(
a)[10,20,30,40]
mysqlset
x1=json_extract(a,$.10);QueryOK,0rowsaffected(0.01sec)
mysqlset
x2=json_extract(a,$.20);mysqlset
x3=json_extract(a,$.30);mysqlset
x4=json_extract(a,$.40);mysqlselect
x1dict[10],x2dict[20],x3dict[30],x4dict[40];+------------+------------+------------+------------+
dict[10]
dict[20]
dict[30]
dict[40]
mysql
db2
oracle
mongodb
3.链表
链表也是一种线性表的存储结构，但是和数组不一样，存储线性表数据的单元并非顺序的。每个元素（也叫节点）包含了自己的值以及指向下一个元素地址的指针。
比如图3，一个单线链表，MySQL的B+树索引叶子节点就是一个链表结构。
链表的优缺点如下，
1）链表不需要连续的存储区域，任何空余的存储区域都可以保存链表元素，只要指针指向正确的地址即可。
2）对链表的更改（插入或者删除）操作非常快，时间复杂度为O(1)，只需要更改节点对应的指针即可，不需要挪动任何数据。比如上图，往“MySQL”和“DB2”中间插入一个新的元素“maxdb”，只需要把“MySQL的指针指向“maxdb，同时把maxdb的指针指向db2即可。
无法快速定位到指定的元素，必须从链表开头的第一个元素顺序查找，假设要查找的元素是链表的最后一个，那需要把每个元素都扫描一遍，时间复杂度为O(N)。
4.哈希表（散列表）
哈希表（散列表），表现为根据{key，value}（类似字典）直接访问的一种数据结构。哈希表一般用数组来保存，其中下标是根据一个固定的函数func1（散列函数）带入参数key计算的结果，value为对应的数据。对于数组a来说，a[func1(key)]=value。比如图4，func1这里为取模函数mod(key,9)：
从上图可以发现以下几个问题：
1）数组的值直接保存了对应的VALUE，比如相同下标对应多个VALUE，每个VALUE本身又占用很大空间，那查询这样的VALUE时，就得在内存中申请一块连续的存储区域。
2）数组的写入效率很差，VALUE存在数据的值里是否合适？
3)数组的下标生成有重复，也就是说散列函数的结果不唯一，也叫散列值发生碰撞。
那如何规避掉以上问题？答案是肯定的！
针对前两个问题，可以把数组和链表结合起来，这样既可以使用数组的高性能随机读，又能使用链表的高性能随机写，这种一般叫做拉链法，见图5：
图5所示的散列表依然用数组保存，下标为散列函数根据KEY计算的结果，值变为指向一个链表的指针，链表里保存了对应的VALUE，这样的优点是数组本身占用空间不大，后期需要扩容效率也高。
比如查找key为20对应的VALUE，通过函数func1计算得到结果为2，就可以很快找到下标为2的值。
那接下来看图4里发现的最后一个问题，散列函数的选择。理论上来讲，对任何键值都有可能存在一个完美的散列函数并且不会发生任何碰撞，但是现实场景中找一个散列碰撞极少的散列函数就已经很优化了。
大致有两个层面要考虑，
1）数据分布
比如上面的取模函数，针对整数类型集合，如果除数足够大，其生成结果产生的碰撞几率就足够小。举个简单例子，
以下Key集合{1,2,...,0000}，有W个元素，每个元素类型都为无符号整数，那这样，可以用最大值0000来做基数取模，每个值的散列结果都唯一。但是这个得提前获知集合的大小以及类型。
2）散列函数的效率
散列表能快速查找，归功于散列函数的快速计算，如果一个散列函数计算耗时很久，那对应的散列表查找也就不可能很快。一般来说，散列函数的复杂度都假设为趋近于O（1），一个好的散列函数理论上应该是稳定、快速。比如MySQL的哈希分区就用的函数password。下图6是基于一个非常差的散列函数生成的散列表。可以看到结果多次碰撞，应该避免这种场景发生。
对上图中的散列表来说，不可能快速检索。不过可以考虑当链表到达一定的长度后，把链表变为一棵AVL树来加快检索效率。散列表的实现除了一般的拉链法还有比如开放地址法等，感兴趣的可以深入研究。
哈希表（散列表）的优缺点总结如下，
哈希表的目的是让写入和查找时间复杂度都接近常量O（1），所以小表做哈希性能非常好。
要提前预判用来生成哈希表的基础表数据量，防止数据量过大，哈希表被撑大。
要找到合适的哈希函数，以防哈希表碰撞太频繁。
总结
哈希索引的实现就是建立在散列表的基础上，把索引字段当成KEY，通过散列函数计算结果后，指向对应的行记录。认识哈希表对后期的INNODB自适应哈希索引以及对HASHJOIN的理解就会更加深刻。