共计 3825 个字符，预计需要花费 10 分钟才能阅读完成。
MySQL 的默认索引构造是 B+ 树，也能够指定索引构造为 HASH 或者 R 树等其余构造来适应不同的检索需要。这里咱们来介绍 MySQL 哈希索引。
MySQL 哈希索引又基于哈希表（散列表）来实现，所以理解什么是哈希表对 MySQL 哈希索引的了解至关重要。接下来，咱们来一步一部介绍哈希表。
1. 数组
数组是最罕用的数据结构，是一种线性表的顺序存储形式，由下标（也叫索引）和对应的值形成。数组在各个开发语言以及数据库中都有相似的构造，相似下图 1：
图 1 展现了一个一维整数数组，数组的长度为 10，下标从 0-9，每个下标对应不同的值。每种编程语言基本上都有数组，大部分数据库也提供了数组或者是相似数组的构造，MySQL 也有数组，以下为 MySQL 的一维数组：
mysql> select @a as "array",json_length(@a) as "array_size";
+-------------------------------------------+------------+
| array | array_size |
+-------------------------------------------+------------+
| [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] | 10 |
+-------------------------------------------+------------+
1 row in set (0.00 sec)数组元素也能够是数组，这样的示意称为多维数组，如图 2，一个二维字符串数组：
以下为 MySQL 里的多维数组：
mysql> select json_pretty(@a)\G
*************************** 1. row ***************************
json_pretty(@a): [
[
"mysql",
"db2"
],
[
"oracle",
"mongodb",
"sql server",
"redis"
],
[
"memcached",
"dble",
"postgresql",
"mariadb"
]
]
1 row in set (0.01 sec)数组优缺点如下，
长处：
数组最大的长处是能够依据下标来疾速读取到对应的值，艰深的说法就是工夫复杂度为 O(1)。
毛病：
1）对数组的写入（插入或者删除）要波及到原下标对应值的迁徙以及新下标的生成；
2）数组存储须要一块间断的存储区域，前期数组扩容须要申请新的间断存储区域，造成空间节约。
2. 字典
字典和数组构造相似，不同的是，下标并非是从 0 开始的数字，而是任意的字符串。有的程序语言里把字典也叫数组，由 Key 映射为对应的 value，字典的构造相似于图 2：
MySQL 也同样提供了这样的字典，比方上面定义了一个字典，存入变量 @a，把图 2 里前 4 个元素拿进去，对应的 value 别离为“mysql”,”db2″,”oracle”,”mongodb”.
mysql> set @a='{"10":"mysql","20":"db2","30":"oracle","40":"mongodb"}';
Query OK, 0 rows affected (0.00 sec)
mysql> select json_keys(@a);
+--------------------------+
| json_keys(@a) |
+--------------------------+
| ["10", "20", "30", "40"] |
+--------------------------+
1 row in set (0.00 sec)
mysql> set @x1=json_extract(@a,'$."10"');
Query OK, 0 rows affected (0.01 sec)
mysql> set @x2=json_extract(@a,'$."20"');
Query OK, 0 rows affected (0.00 sec)
mysql> set @x3=json_extract(@a,'$."30"');
Query OK, 0 rows affected (0.00 sec)
mysql> set @x4=json_extract(@a,'$."40"');
Query OK, 0 rows affected (0.00 sec)
mysql> select @x1 "dict['10']", @x2 "dict['20']", @x3 "dict['30']", @x4 "dict['40']";
+------------+------------+------------+------------+
| dict['10'] | dict['20'] | dict['30'] | dict['40'] |
+------------+------------+------------+------------+
| "mysql" | "db2" | "oracle" | "mongodb" |
+------------+------------+------------+------------+
1 row in set (0.00 sec)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,…,1000000}，有 100W 个元素，每个元素类型都为无符号整数，那这样，能够用最大值 1000000 来做基数取模，每个值的散列后果都惟一。然而这个得提前获知汇合的大小以及类型。
2）散列函数的效率
散列表能疾速查找，归功于散列函数的疾速计算，如果一个散列函数计算耗时很久，那对应的散列表查找也就不可能很快。一般来说，散列函数的复杂度都假如为趋近于 O（1），一个好的散列函数实践上应该是稳固、疾速。比方 MySQL 的哈希分区就用的函数 password。下图 6 是基于一个十分差的散列函数生成的散列表。能够看到后果屡次碰撞，应该防止这种场景产生。
对上图中的散列表来说，不可能疾速检索。不过能够思考当链表达到肯定的长度后，把链表变为一棵 AVL 树来放慢检索效率。散列表的实现除了个别的拉链法还有比方凋谢地址法等，感兴趣的能够深入研究。
哈希表（散列表）的优缺点总结如下，
长处：
哈希表的目标是让写入和查找时间复杂度都靠近常量 O（1），所以小表做哈希性能十分好。
毛病：
要提前预判用来生成哈希表的根底表数据量，避免数据量过大，哈希表被撑大。
要找到适合的哈希函数，以防哈希表碰撞太频繁。
总结
哈希索引的实现就是建设在散列表的根底上，把索引字段当成 KEY，通过散列函数计算结果后，指向对应的行记录。意识哈希表对前期的 INNODB 自适应哈希索引以及对 HASH JOIN 的了解就会更加粗浅。
对于 MySQL 的技术内容，你们还有什么想晓得的吗？连忙留言通知小编吧！
