2020-12-16

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)
1
2
3
4
5
6
7

数组元素也可以是数组，这样的表示称为多维数组，如图 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

数组优缺点如下，

优点：

数组最大的优点是可以根据下标来快速读取到对应的值，通俗的说法就是时间复杂度为 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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 的技术内容，你们还有什么想知道的吗？赶紧留言告诉小编吧！