MySQL InnoDB索引原理和算法

也许你经常用 MySQL ，也会经常用索引，但是对索引的原理和高级功能却并不知道，我们在这里一起学习下。

InnoDB 存储索引

在数据库中，如果索引太多，应用程序的性能可能会受到影响；如果索引太少，又会对查询性能产生影响。所以，我们要追求两者的一个平衡点，足够多的索引带来查询性能提高，又不因为索引过多导致修改数据等操作时负载过高。

InnoDB 支持 3 种常见索引：

B+ 

我们接下来要详细讲解的就是 B+ 树索引和全文索引。

哈希索引

InnoDB 存储引擎支持的哈希索引是自适应的，会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。这块内容我们先不展开说，后续补充。

B+ 树索引

B+ 树索引是目前关系型数据库系统中查找最为常用和有效的索引，其构造类似于二叉树，根据键值对快速找到数据。 B+ 树 （balance+ tree） 由 B 树 （banlance tree 平衡二叉树） 和索引顺序访问方法 （ISAM: Index Sequence Access Method） 演化而来，这几个都是经典的数据结构。而 MyISAM 引擎最初也是参考 ISAM 数据结构设计的。

基础数据结构

想要了解 B+ 树数据结构，我们先了解一些基础的知识。

二分查找法

又称为折半查找法，指的是将数据顺序排列，通过每次和中间值比较，跳跃式查找，每次缩减一半的范围，快速找到目标的算法。其算法复杂度为 log2(n) ，比顺序查找要快上一些。

如图所示，从有序列表中查找 48 ，只需要 3 步：

详细的算法可以参考 二分查找算法 。

二叉查找树

二叉查找树的定义是在一个二叉树中，左子树的值总是小于根键值，根键值总是小于右子树的值。在我们查找时，每次都从根开始查找，根据比较的结果来判断继续查找左子树还是右子树。其查找的方法非常类似于二分查找法。

平衡二叉树

二叉查找树的定义非常宽泛，可以任意构造，但是在极端情况下查询的效率和顺序查找一样，如只有左子树的二叉查找树。

若想构造一个性能最大的二叉查找树，就需要该树是平衡的，即平衡二叉树（由于其发明者为 G. M. Adelson-Velsky 和 Evgenii Landis ，又被称为 AVL 树）。其定义为必须满足任何节点的两个子树的高度最大差为 1 的二叉查找树。平衡二叉树相对结构较优，而最好的性能需要建立一个最优二叉树，但由于维护该树代价高，因此一般平衡二叉树即可。

平衡二叉树查询速度很快，但在树发生变更时，需要通过一次或多次左旋和右旋来达到树新的平衡。这里不发散讲。

B+ 树

了解了基础的数据结构后，我们来看下 B+ 树的实现，其定义十分复杂，目标是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在该树中，所有的记录都按键值的大小放在同一层的叶子节点上，各叶子节点之间有指针进行连接（非连续存储），形成一个双向链表。索引节点按照平衡树的方式构造，并存在指针指向具体的叶子节点，进行快速查找。

下面的 B+ 树为数据较少时，此时高度为 2 ，每页固定存放 4 条记录，扇出固定为 5 （图上灰色部分）。叶子节点存放多条数据，是为了降低树的高度，进行快速查找。

当我们插入 28、70、95 3 条数据后， B+ 树由于数据满了，需要进行页的拆分。此时高度变为 3 ，每页依然是 4 条记录，双向链表未画出但是依然是存在的，现在可以看出来是一个平衡二叉树的雏形了。

InnoDB 的 B+ 树索引

InnoDB 的 B+ 树索引的特点是高扇出性，因此一般树的高度为 2~4 层，这样我们在查找一条记录时只用 I/O 2~4 次。当前机械硬盘每秒至少 100 次 I/O/s ，因此查询时间只需 0.02~0.04s 。

数据库中的 B+ 树索引分为聚集索引 （clustered index） 和辅助索引 （secondary index） 。它们的区别是叶子节点存放的是否为一整行的完整数据。

聚集索引

聚集索引就是按照每张表的主键（唯一）构造一棵 B+ 树，同时叶子节点存放整行的完整数据，因此将叶子节点称为数据页。由于定义了数据的逻辑顺序，聚集索引也能快速的进行范围类型的查询。

聚集索引的叶子节点按照逻辑顺序连续存储，叶子节点内部物理上连续存储，作为最小单元，叶子节点间通过双向指针连接，物理存储上不连续，逻辑存储上连续。

聚集索引能够针对主键进行快速的 排序 查找和范围查找，由于是双向链表，因此在逆序查找时也非常快。

我们可以通过 explain 命令来分析 MySQL 数据库的执行计划：

# 查看表的定义，可以看到id为主键，name为普通列
mysql> show create table dimensionsConf;
| Table          | Create Table     
| dimensionsConf | CREATE TABLE `dimensionsConf` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(20) DEFAULT NULL,
  `remark` varchar(1024) NOT NULL,
  PRIMARY KEY (`id`),
  FULLTEXT KEY `fullindex_remark` (`remark`)
) ENGINE=InnoDB AUTO_INCREMENT=178 DEFAULT CHARSET=utf8 |
1 row in set (0.00 sec)

# 先测试一个非主键的name属性排序并查找，可以看到没有使用到任何索引，且需要filesort（文件排序），这里的rows为输出行数的预估值
mysql> explain select * from dimensionsConf order by name limit 10\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: dimensionsConf
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 57
        Extra: Using filesort
1 row in set (0.00 sec)

# 再测试主键id的排序并查找，此时使用主键索引，在执行计划中没有了filesort操作，这就是聚集索引带来的优化
mysql> explain select * from dimensionsConf order by id limit 10\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: dimensionsConf
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 10
        Extra: NULL
1 row in set (0.00 sec)

# 再查找根据主键id的范围查找，此时直接根据叶子节点的上层节点就可以快速得到范围，然后读取数据
mysql> explain select * from dimensionsConf where id>10 and id<10000\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: dimensionsConf
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 56
        Extra: Using where
1 row in set (0.00 sec)

辅助索引

辅助索引又称非聚集索引，其叶子节点不包含行记录的全部数据，而是包含一个书签 （bookmark） ，该书签指向对应行数据的聚集索引，告诉 InnoDB 存储引擎去哪里查找具体的行数据。辅助索引与聚集索引的关系就是结构相似、独立存在，但辅助索引查找非索引数据需要依赖于聚集索引来查找。

全文索引

我们通过 B+ 树索引可以进行前缀查找，如：

select * from blog where content like 'xxx%';

只要为 content 列添加了 B+ 树索引（聚集索引或辅助索引），就可快速查询。但在更多情况下，我们在博客或搜索引擎中需要查询的是某个单词，而不是某个单词开头，如：

select * from blog where content like '%xxx%';

此时如果使用 B+ 树索引依然是全表扫描，而全文检索 （Full-Text Search） 就是将整本书或文章内任意内容检索出来的技术。

倒排索引

全文索引通常使用倒排索引 （inverted index） 来实现，倒排索引和 B+ 树索引都是一种索引结构，它需要将分词 （word） 存储在一个辅助表 （Auxiliary Table） 中，为了提高全文检索的并行性能，共有 6 张辅助表。辅助表中存储了单词和单词在各行记录中位置的映射关系。它分为两种：

• inverted file index （倒排文件索引），表现为{单词，单词所在文档 ID }
• full inverted index （详细倒排索引），表现为{单词，(单词所在文档 ID , 文档中的位置)}

对于这样的一个数据表：

倒排文件索引类型的辅助表存储为：

详细倒排索引类型的辅助表存储为，占用更多空间，也更好的定位数据，比提供更多的搜索特性：

全文检索索引缓存

辅助表是存在与磁盘上的持久化的表，由于磁盘 I/O 比较慢，因此提供 FTS Index Cache （全文检索索引缓存）来提高性能。 FTS Index Cache 是一个红黑树结构，根据 （word, list） 排序，在有数据插入时，索引先更新到缓存中，而后 InnoDB 存储引擎会批量进行更新到辅助表中。

当数据库宕机时，尚未落盘的索引缓存数据会自动读取并存储，配置参数 innodb_ft_cache_size 控制缓存的大小，默认为 32M ，提高该值，可以提高全文检索的性能，但在故障时，需要更久的时间恢复。

在删除数据时， InnoDB 不会删除索引数据，而是保存在 DELETED 辅助表中，因此一段时间后，索引会变得非常大，可以通过 optimize table 命令手动删除无效索引记录。如果需要删除的内容非常多，会影响应用程序的可用性，参数 innodb_ft_num_word_optimize 控制每次删除的分词数量，默认为 2000 ，用户可以调整该参数来控制删除幅度。

全文检索限制

全文检索存在一个黑名单列表 （stopword list） ，该列表中的词不需要进行索引分词，默认共有 36 个，如 the 单词。你可以自行调整：

mysql> select * from information_schema.INNODB_FT_DEFAULT_STOPWORD;
+-------+
| value |
+-------+
| a     |
| about |
| an    |
| are   |
| as    |
| at    |
| be    |
| by    |
| com   |
| de    |
| en    |
| for   |
| from  |
| how   |
| i     |
| in    |
| is    |
| it    |
| la    |
| of    |
| on    |
| or    |
| that  |
| the   |
| this  |
| to    |
| was   |
| what  |
| when  |
| where |
| who   |
| will  |
| with  |
| und   |
| the   |
| www   |
+-------+
36 rows in set (0.00 sec)

其他限制还有：

• 每张表只能有一个全文检索索引
• 多列组合的全文检索索引必须使用相同的字符集和字符序，不了解的可以参考 MySQL乱码的原因和设置UTF8数据格式
• 不支持没有单词界定符 （delimiter） 的语言，如中文、日语、韩语等

全文检索

我们创建一个全文索引：

mysql> create fulltext index fullindex_remark on dimensionsConf(remark);
Query OK, 0 rows affected, 1 warning (0.39 sec)
Records: 0  Duplicates: 0  Warnings: 1

mysql> show warnings;
+---------+------+--------------------------------------------------+
| Level   | Code | Message                                          |
+---------+------+--------------------------------------------------+
| Warning |  124 | InnoDB rebuilding table to add column FTS_DOC_ID |
+---------+------+--------------------------------------------------+
1 row in set (0.00 sec)

全文检索有两种方法：

• 自然语言 （Natural Language） ，默认方法，可省略： （IN NATURAL LANGUAE MODE）
• 布尔模式 （Boolean Mode） ： （IN BOOLEAN MODE）

自然语言还支持一种扩展模式，后面加上： （WITH QUERY EXPANSION） 。

其语法为 MATCH()...AGAINST() ， MATCH 指定被查询的列， AGAINST 指定何种方法查询。

自然语言检索

mysql> select remark from dimensionsConf where remark like '%baby%';
+-------------------+
| remark            |
+-------------------+
| a baby like panda |
| a baby like panda |
+-------------------+
2 rows in set (0.00 sec)

mysql> select remark from dimensionsConf where match(remark) against('baby' IN NATURAL LANGUAGE MODE);
+-------------------+
| remark            |
+-------------------+
| a baby like panda |
| a baby like panda |
+-------------------+
2 rows in set (0.00 sec)

# 查看下执行计划，使用了全文索引排序
mysql> explain select * from dimensionsConf where match(remark) against('baby');
+----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+
| id | select_type | table          | type     | possible_keys    | key              | key_len | ref  | rows | Extra       |
+----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+
|  1 | SIMPLE      | dimensionsConf | fulltext | fullindex_remark | fullindex_remark | 0       | NULL |    1 | Using where |
+----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+
1 row in set (0.00 sec)

我们也可以查看各行数据的相关性，是一个非负的浮点数， 0 代表没有相关性：

mysql> select id,remark,match(remark) against('baby') as relevance from dimensionsConf;
+-----+-----------------------+--------------------+
| id  | remark                | relevance          |
+-----+-----------------------+--------------------+
| 106 | c                     |                  0 |
| 111 | 运营商             |                  0 |
| 115 | a baby like panda     | 2.1165735721588135 |
| 116 | a baby like panda     | 2.1165735721588135 |
+-----+-----------------------+--------------------+
4 rows in set (0.01 sec)

布尔模式检索

MySQL 也允许用修饰符来进行全文检索，其中特殊字符会有特殊含义：

• +: 该 word 必须存在
• -: 该 word 必须排除
• （no operator）: 该 word 可选，如果出现，相关性更高
• @distance: 查询的多个单词必须在指定范围之内
• >: 出现该单词时增加相关性
• <: 出现该单词时降低相关性
• ~: 出现该单词时相关性为负
• *: 以该单词开头的单词
• ": 表示短语

# 代表必须有a baby短语，不能有man，可以有lik开头的单词，可以有panda，
select remark from dimensionsConf where match(remark) against('+"a baby" -man lik* panda' IN BOOLEAN MODE);

扩展查询

当查询的关键字太短或不够清晰时，需要用隐含知识来进行检索，如 database 关联的 MySQL/DB2 等。但这个我并没太明白怎么使用，后续补充吧。

类似的使用是：

select * from articles where match(title,body) against('database' with query expansion);

参考资料

1. 二分查找算法： https://juejin.im/post/5c90ed...
2. MySQL乱码的原因和设置UTF8数据格式: https://segmentfault.com/a/11...
3. 《MySQL技术内幕 InnoDB存储引擎 第2版》第5章：索引与算法