MySQL InnoDB存储索引详解

InnoDB存储引擎支持以下几种常见的索引，如B+树索引、哈希索引、全文索引。哈希索引是自适应的，InnoDB会根据表的使用情况自动为表生成哈希索引。

B+树索引是目前关系型数据库中最常用、最有效的索引之一，其索引结构是一种多路平衡树结构（与二叉树类似，B代表的不是Binary，而是Balance）。通过B+树索引能够快速的定位要要查找的数据所在的数据页，然后将页读入内存，在通过页字典槽快速寻找到数据行。

InnoDB引擎中实现了B+树结构的索引，其高度一般在2~3层，换句话说，查询记录的IO操作次数最多3次。InnoDB索引可以分为聚簇索引和非聚簇索引，这两种分类的索引都是B+树结构的。

<

聚簇索引（Clustered Index）

聚簇索引，又称聚集索引，其是一种数据存储的方式。在InnoDB存储引擎中B+树索引与数据是存储在一起的，换句话说InnoDB存储引擎的数据是由B+树索引组织的。

<

建表

在进行索引讲解前，我们先建立如下表：

-- ----------------------------
-- Table structure for index_test
-- ----------------------------
DROP TABLE IF EXISTS `index_test`;
CREATE TABLE `index_test` (
  `id` int NOT NULL AUTO_INCREMENT,
  `name` varchar(50) NOT NULL,
  `age` int NOT NULL,
  `profession` varchar(100) NOT NULL,
  `sex` char(1) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `index_name_profession` (`name`,`profession`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of index_test
-- ----------------------------
BEGIN;
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (1, 'Tom', 33, 'teacher', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (2, 'Ryan', 25, 'programmer', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (3, 'Li', 18, 'student', 'w');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (4, 'Bob', 40, 'doctor', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (5, 'Jim', 60, 'doctor', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (6, 'Ben', 34, 'teacher', 'm');
INSERT INTO `index_test` (`id`, `name`, `age`, `profession`, `sex`) VALUES (7, 'Joy', 28, 'programmer', 'w');
COMMIT;

<

聚簇索引结构

数据行实际存储在数据页中，通过B+树索引结构的叶子节点将数据页组织起来。如下图所示（若对B+树结构不了解可以看我另外一篇文章《数据结构-B树族》）：

聚簇索引结构

B+树的每一个叶子节点都是一个数据页。B+树的内部节点都是索引节点，键的左右指针指向的都是数据页。叶子节点间（数据页）是通过指针（页指针）相连的，是一个双向链表结构。叶子节点（数据页）内部是数据行，数据行之间也是通过指针相连。叶子节点（数据页）与叶子节点内的数据行，都是按照主键顺序排列的（注意：叶子节点之间与行之间都不是物理连续的，而都是链表结构）。<

主键选择原则

使用B+树作为数据存储的结构我们需要让主键（键值）满足以下特性：

键值长度尽量小：键值是会占用空间的，我们希望的是其越小越好。

键值尽量单调递增：B+树的插入可能会引起节点的分裂，如果不是单调递增，我们可能会插入到页中间位置，这就可能导致数据的分裂以及数据的挪动，严重的影响插入性能。

<

非聚簇索引（Secondary Index）

非聚簇索引，也称非聚集索引、二级索引、辅助索引等。在InnoDB中，非聚簇索引的页节点除了包含键之外，还包含一个bookmark，也就是一个可以找到该键对应的数据行所在位置。结合我们上面讲到的，这里的书签值就对应的是聚簇索引的键。

辅助索引与聚簇索引关系

<

单列索引

单列索引，即一个索引树中只包含一个列的值，一张表可以建立多个单列索引，如果一个查询语句中包含了单列索引列，优化器可能只会选择一个最优的单列索引，具体遵循如下原则：

如果查询条件是AND连接，且用到的所有（或部分）列都建立了索引，则优化器会按照最优策略，可能会命中一个或多个索引。如果查询条件是OR连接，且用到的所有列都建立了索引，则所有索引都会命中。如果查询条件是OR连接，且用到的只有部分列建立了索引，则执行全表扫表。

1、2两条原则涉及到了一个index_merge策略，这是一个多索引合并优化策略，这个概念我们下面会讲。

单列索引

<

索引合并

合并索引是在mysql 5.7的InnoDB引擎引入的一个策略，我们称之为index_merge，如果使用到了这种策略，执行计划会返回type：index_merge，它具有有以下的特性：

它会将几个索引的范围扫描结果合并成（AND取交集、OR取并集）一个。该策略只适用于单表操作，多表查询失效。如果存在某个OR条件没有建立单列索引，则失效。如果所有条件对应的列都是索引，则AND和OR组合使用也会命中该类型索引。执行如下语句我们可以看到type为index_merge，Extra为sort_union。

EXPLAIN SELECT * FROM index_test WHERE name='Tom' OR professinotallow='teacher';

执行结果

<

组合索引

在没有建立组合索引的情况下，可通过多个单列索引UNION操作快速得到结果。接下来我们介绍一下组合索引，先见下图：

组合索引

对于组合索引来说，所有参与索引的列都会出现在索引树上。如上图，是一个index_profession_name组合索引，存储引擎首先会根据profession列值顺序建立第一个索引列，紧接在第一个列的基础上建立第二个索引列。

组合索引有以下特性：

查询遵循最左原则，查询条件必须包含第一个索引列，即profession、profession&name、profession&sex等组合；如果查询条件包含了第一个索引列，则查询条件的书写顺序没有要求，即name&profession、age&profession等写法都可以，优化器会处理顺序;OR查询会让组合索引失效；<

回表查询

组合索引的查询可能涉及到回表查询操作，什么是回表查询呢？

当SELECT的列中包含了非索引列时，我们需要通过聚簇索引来补齐数据，这个就叫回表查询。

我们来举个例子：

SELECT profession,name,age,sex FROM index_test WHERE profession = 'xxx';

此时的age、sex列不在索引index_profession_name中，则需要通过查询index_test的聚簇索引补齐age、sex列信息。

如果我们SELECT的列都是索引列呢？是否就不需要回表查询了，这个有涉及另一个概念即索引覆盖。

<

索引覆盖

从上面的一个例子我们很容易得出，索引覆盖就是：

当SELECT的列中包含都是索引列时，我们通过该非聚簇索引就能拿到所有数据，这就叫做索引覆盖。

如下图是索引覆盖时的执行计划的内容，我们可以看到Extra为Usering index。

索引覆盖

<

索引下推

关于索引下推从字面上不太好理解（这个词很唬人，但是我们了解了其逻辑后，你会发现极其简单，论起名的重要性），我们先看下面这张图：

SELECT * FROM index_test WHERE name like 'J%' AND profession = 'programmer' AND sex = 'm';

索引下推

在MySQL5.6以前，只要第一个索引列满足查询条件，就会回表查询，如上图有3次回表查询。

在MySQL5.6之后，通过索引下推，会依次匹配多个索引列，过滤掉不符合的，从而减少回表次数，如上图不等于programmer直接跳过了，减少了1次回表操作。

索引下推可以有效减少回表次数，从而提升查询效率（也就是多个if判断，搞个名词唬人）。

<

索引的选择性

索引的选择性，就是指该索引的建立是否有必要性，因为并不是所有查询条件中出现的列都需要添加索引。比如性别（男、女），整张表除了男就是女，浪费索引存储空间且起不到任何提升查询速度的作用。

索引的选择性有一个非常重要的指标，即Cardinality（基数），即该索引所统计的不重复记录数，如果其越接近于聚簇索引，那么其利用率及效率越高，如下图所示：

索引的选择性

索引的选择性公式为：索引的选择性=不重复的索引值数/数据表的记录总数。

聚簇索引选择性为1，也就是说如果一个索引的选择性约接近1，其查询效率越高，但是索引所占用的空间越大。

<

索引失效

OR 前后查询条件不都是索引字段。未遵循最左N个字段。模糊查询 LIKE 以 % 开头。需要类型转换。WHERE 中索引列有计算。WHERE 中索引列用到了函数。索引字段上使用 NOT、<> 、!= 。当全表扫描速度比索引速度快时。<

前缀索引

我们先来看如下两个索引：

ALTER TABLE index_test ADD INDEX index_name(name);

ALTER TABLE index_test ADD INDEX index_name_pre(name(1));

上面两个索引的唯一不同点就是，index_name_pre索引是一个name的前缀索引，前缀的长度为1，也就是说index_name_pre只包含name字段的第一个字符。

我们分别执行下面的语句，看一下两个索引的使用情况：

EXPLAIN SELECT * FROM index_test WHERE name like 'Ben';

index_name_pre索引

index_name_pre索引

index_name索引

index_name索引

从两条执行计划可以看出，若在index_name_pre索引下查询会扫描2行记录，而index_name索引下只需要扫描1行记录。那是不是前缀索引就没有存在的意义了呢？然而并不是，我们接着看。

<

前缀索引的选择原则

列值很长且需要建立索引：如果我们为表index_test表建立了一个新列：address varchar(500)，该列是一个存储用户的地址列，其实际长度可能有几百个字符。如果我们为其建立一个完整索引，其所占用的索引空间将是巨大的，这时我们可以为其建立一个前缀索引。前缀索引需要列的一部分前缀作为索引，这个“一部分”的计算依据是根据索引的选择性来决定的。

我们希望的是：前缀n的选择性无限趋近于全列的选择性，但n的值需要尽量小（节省空间），计算步骤如下：

column_name的全列选择性计算方式：

SELECT COUNT(DISTINCT column_name) / COUNT(*) FROM table_name;

column_name的前缀n的选择性计算方式：

SELECT COUNT(DISTINCT LEFT(column_name, n)) / COUNT(*) FROM table_name;

通过调整n的大小，得到一个接近全列选择性的n值，同时又能保证前缀足够小。

<

Hash索引

MySQL的Memory引擎支持Hash索引，但我们今天讲的不是该引擎，而是InnoDB的存储引擎的哈希索引。我这里说的哈希索引，严格意义上说应该叫自适应哈希索引（Adaptive Hash Index，AHI）。

自适应哈希索引是不能用户手动创建的，它是由引擎根据当前视图的数据访问频次在缓冲池建立一个哈希索引。通过访问频次建立，换句话说就是为高频热点数据建立索引。

<

结构

哈希索引是通过哈希表来实现的，Key是利用查询条件中的键通过哈希函数计（CRC32算）算得到，Value则是直接指向数据页中的值。

自适应哈希索引结构

如上图通过Hash索引可以做到O(1)的时间复杂度查询，而利用辅助索引则需要N次（与树的高度有关）。

<

自适应的触发条件

使用相同的条件访问了同一个索引17次；

例如表index_test表有index_profession_name组合索引，如果我们使用以下任意语句访问（不能是交替访问）可创建自适应索引：

SELECT * FROM index_test WHERE profession = 'programmer';

SELECT * FROM index_test WHERE profession = 'programmer' AND name = 'Tom';

如果以同一查询条件进行了100次以上的访问；

数据页被相同查询语句访问了N次（N = 页记录数 * 1/16）;

<

缺点

自适应哈希索引的维护势必会用到锁来控制并发，那么该锁可能导致性能损耗。自适应哈希索引在DML操作下引发的数据变化时处理效率成本高。自适应哈希索引的条件很苛刻，需要相同的查询条件连续访问，且只适用于等值搜索条件，order by、模糊查询等都不行。其本身会可能会占用大量的内存池空间，从而加重引擎的负担，需要做好参数调节。<

总结

InnoDB存储引擎的索引共有以下几种：B+树索引、哈希索引、全文索引，本文主要介绍了前两种。InnoDB存储引擎的数据是由B+树索引组织的，换句话说：聚簇索引即使索引又存储完整记录数据。可以利用多个单列索引的索引合并来实现组合索引的效果，但是不推荐这么做。在设计组合索引时需要注意索引的选择性，约趋近于1的索引会越高效，但是索引存储空间也会变大。可以利用覆盖索引来快速的查询，覆盖索引不用回表查询，非常高效。当遇到非常大的列需要建立索引时可以考虑使用前缀索引，但要注意前缀的长度选择，可通过索引的选择性公式计算。索引下推可以有效减少组合索引的回表次数，提示查询效率。自适应哈希索引的条件非常的苛刻，因此要设法利用它来提升查询效率。