03 MySQL 的索引是如何执行的？

好了，可以作为所索引内存模型的数据结构都分析了一遍。最终 MySQL 还是选择了 B+ 树作为索引内存模型。那 B+ 树在具体的引擎中是怎么发挥作用的呢？一起来看看

3.1 InnDB 索引

首先是 InnDB 索引，篇幅原因，我就聊聊主键索引和普通索引。

3.1.1 主键索引

主键索引又叫聚簇索引，它使用 B+ 树构建，叶子节点存储的是数据表的某一行数据。当表没有创建主键索引是，InnDB 会自动创建一个 ROWID 字段用于构建聚簇索引。规则如下：

1. 在表上定义主键 PRIMARY KEY，InnoDB 将主键索引用作聚簇索引。
2. 如果表没有定义主键，InnoDB 会选择第一个不为 NULL 的唯一索引列用作聚簇索引。
3. 如果以上两个都没有，InnoDB 会使用一个 6 字节长整型的隐式字段 ROWID 字段构建聚簇索引。该 ROWID 字段会在插入新行时自动递增。

多说无益，以下面的 Student 表为例，它的 id 是主键，age 列为普通索引。

CREATE TABLE `student`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `age` int(11) NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  INDEX `index_age`(`age`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 66 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;

表数据如下：

• 主键索引等值查询 sql：

select * from student where id = 38;

过程如下：

• 第一次磁盘 IO：从根节点检索，将数据块 1 加载到内存，比较 38 < 44，走左边。
• 第二次磁盘 IO：将左边数据块 2 加载到内存，比较 8<37<38，走右边。
• 第三次磁盘 IO：将右边数据块 6 加载到内存，比较 37<38，38=38。查询完毕，将数据返回客户端。

流程图：3 次磁盘 IO

• 主键索引范围查询 sql

select * from student where id between 38 and 44;

前面也介绍说了，B+ 树因为叶子节点有双向指针，范围查询可以直接利用双向有序链表。

过程如下：

• 第一次磁盘 IO：从根节点检索，将数据块 1 加载到内存，比较 38 < 44，走左边。
• 第二次磁盘 IO：将左边数据块 2 加载到内存，比较 8<37<38，走右边。
• 第三次磁盘 IO：将右边数据块 6 加载到内存，比较 37<38，38=38。走右边。
• 第四次磁盘 IO：将右边数据块 7 加载到内存，比较 38<44=44。查询完毕，将数据返回客户端。

流程图：一共四次磁盘 IO

3.1.2 普通索引

• 普通索引等值查询 sql

在 InnDB 中，B+ 树普通索引不存储数据，只存储数据的主键值。比如本表中的 age，它的索引结构就是这样的：

执行以下查询语句，它的流程又是怎样的呢？

select * from student where age = 48;

使用普通索引需要检索两次索引。第一次检索普通索引找出 age = 48 得到主键值，再使用主键到主键索引中检索获得数据。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一遍索引树。因此，我们应该尽量使用主键查询。

过程如下：

• 第一次磁盘 IO：从根节点检索，将数据块 1 加载到内存，比较 48 < 54，走左边。
• 第二次磁盘 IO：将左边数据块 2 加载到内存，比较 28<47<48，走右边。
• 第三次磁盘 IO：将右边数据块 6 加载到内存，比较 47<48，48=48。得到主键 38。
• 第四次磁盘 IO：从根节点检索，将根节点加载到内存，比较 38 < 44，走左边。
• 第五次磁盘 IO：将左边数据块 2 加载到内存，比较 8<37<38，走右边。
• 第六次磁盘 IO：将右边数据块 6 加载到内存，比较 37<38，38=38。查询完毕，将数据返回客户端。

流程图：一共 6 次磁盘 IO。

3.1.3 组合索引

如果为每一种查询都设计一个索引，索引是不是太多了？如果我现在要根据学生的姓名去查它的年龄。假设这个需求出现的概览很低，但我们也不能让它走全表扫描吧？

但是为一个不频繁的需求创建一个（姓名）索引是不是有点浪费了？那该咋做呢？我们可以建个（name，age）的联合索引来解决呀。组合索引的结构如下图所示：

执行以下查询语句，它的流程又是怎样的呢？

select * from student where name = '二狗5' and age = 48;

过程如下：

• 第一次磁盘 IO：从根节点检索，将数据块 1 加载到内存，比较 二狗 5 < 二狗 6，走左边。
• 第二次磁盘 IO：将左边数据块 2 加载到内存，比较 二狗 2 < 二狗 4 < 二狗 5，走右边。
• 第三次磁盘 IO：将右边数据块 6 加载到内存，比较 二狗 4 < 二狗 5，二狗 5 = 二狗 5。得到主键 38。
• 第四次磁盘 IO：从根节点检索，将根节点加载到内存，比较 38 < 44，走左边。
• 第五次磁盘 IO：将左边数据块 2 加载到内存，比较 8<37<38，走右边。
• 第六次磁盘 IO：将右边数据块 6 加载到内存，比较 37<38，38=38。查询完毕，将数据返回客户端。

流程图：一共六次磁盘 IO

3.1.4 最左匹配原则

最左前缀匹配原则和联合索引的索引存储结构和检索方式是有关系的。

在组合索引树中，最底层的叶子节点按照第一列 name  列从左到右递增排列，但是 age 列是无序的，age 列只有在 name 列值相等的情况下小范围内递增有序。

就像上面的查询，B+ 树会先比较 name 列来确定下一步应该搜索的方向，往左还是往右。如果 name 列相同再比较 age 列。但是如果查询条件没有 name 列，B + 树就不知道第一步应该从哪个节点查起，这就是所谓的最左匹配原则。

可以说创建的 idx_name_age (name,age) 索引，相当于创建了 (name)、（name,age）两个索引。

组合索引的最左前缀匹配原则：使用组合索引查询时，mysql 会一直向右匹配直至遇到范围查询 (>、<、between、like) 就停止匹配。

3.1.5 覆盖索引

覆盖索引是一种很常用的优化手段。因为在上面普通索引的例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表。那么有没有可能经过索引优化，避免回表呢？比如改成这样子：

select age from student where age = 48;

在上面普通索引例子中，如果我只需要 age 字段，那是不是意味着我们查询到普通索引的叶子节点就可以直接返回了，而不需要回表。这种情况就是覆盖索引。

看下执行计划：

覆盖索引的情况：

未覆盖索引的情况：

3.2 myisam 索引

还是上面那张 student 表，建表语句：

CREATE TABLE `student`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `age` int(11) NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  INDEX `index_age`(`age`) USING BTREE
) ENGINE = MyISAM AUTO_INCREMENT = 66 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;

3.2.1 主键索引

与 InnDB 不同的是 myisam 的数据文件和索引文件是分开存储的。它的叶子节点存的是健值，数据是索引所在行的磁盘地址。它的结构如下：表 student 的索引文件存放在 student.MYI 中，数据文件存储在 student.MYD 中。

• 主键索引等值查询

select * from student where id = 38;

它的具体执行流程如下：

• 第一次磁盘 IO：从根节点检索，将数据块 1 加载到内存，比较 38 < 44，走左边。
• 第二次磁盘 IO：将左边数据块 2 加载到内存，比较 8<37<38，走右边。
• 第三次磁盘 IO：将右边数据块 6 加载到内存，比较 37<38，38=38。得到索引所在行的内存地址。
• 第四次磁盘 IO：根据地址到数据文件 student.MYD 中获取对应的行记录。

流程图：一共 4 次磁盘 IO。

• 主键索引范围查询

select * from student where id between 38 and 44;

过程如下：

• 第一次磁盘 IO：从根节点检索，将数据块 1 加载到内存，比较 38 < 44，走左边。
• 第二次磁盘 IO：将左边数据块 2 加载到内存，比较 8<37<38，走右边。
• 第三次磁盘 IO：将右边数据块 6 加载到内存，比较 37<38，38=38。得到索引所在行的内存地址。
• 第四次磁盘 IO：根据地址到数据文件 student.MYD 中获取主键 38 对应的行记录。
• 第五次磁盘 IO：将右边数据块 7 加载到内存，比较 38<44=44。得到索引所在行的内存地址。
• 第六次磁盘 IO：根据地址到数据文件 student.MYD 中获取主键 44 对应的行记录。

3.2.2 普通索引

在 MyISAM 中，辅助索引和主键索引的结构是一样的，没有任何区别，叶子节点的数据存储的都是行记录的磁盘地址。只是主键索引的键值是唯一的，而辅助索引的键值可以重复。

查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树中检索数据。

3.3 索引的使用技巧

3.3.1 避免回表

上面说了，回表的原因是因为查询结果所需要的数据只在主键索引上有，所以不得不回表。回表必然会影响性能。那怎么避免呢？

使用覆盖索引，举个栗子：还是上面的 student ，它的一条 sql 在业务上很常用：

select id, name, age from student where name = '二狗2';

而 student 表的其他字段使用频率远低于它，在这种情况下，如果我们在建立 name 字段的索引的时候，并不是使用单一索引，而是使用联合索引（name，age）这样的话再执行这个查询语句就可以根据辅助索引查询到的结果获取当前语句的完整数据。

这样就有效避免了通过回表再获取 age 的数据。喏，这就是一个典型的用覆盖索引的优化策略减少回表的情况。

3.3.2 联合索引的使用

联合索引，在建立索引的时候，尽量在多个单列索引上判断下是否可以使用联合索引。联合索引的使用不仅可以节省空间，还可以更容易的使用到索引覆盖。比如上面的 student 表，我就建了 (name,age) 和 age 索引。

联合索引的创建原则，在创建联合索引的时候因该把频繁使用的列、区分度高的列放在前面，频繁使用代表索引利用率高，区分度高代表筛选粒度大。

也可以在常需要作为查询返回的字段上增加到联合索引中，如果在联合索引上增加一个字段而使用到了覆盖索引，这种情况下应该使用联合索引。

联合索引的使用

• 考虑当前是否已经存在多个可以合并的单列索引，如果有，那么将当前多个单列索引创建为一个联合索引。
• 当前索引存在频繁使用作为返回字段的列，这个时候就可以考虑当前列是否可以加入到当前已经存在索引上，使其查询语句可以使用到覆盖索引。

3.3.3 索引下推

现在我的表数据是这样的：加了一个 sex 列。

说到满足最左前缀原则的时候，最左前缀可以用于在索引中定位记录。这时，你可能要问，那些不符合最左前缀的部分，会怎么样呢？

我们还是以学生表的联合索引（name，age）为例。如果现在有一个需求：检索出表中 “名字第一个字是二，而且年龄是 38 岁的所有男生”。那么，SQL 语句是这么写的：

select * from student where name like '张%' and age=38 and sex='男';

根据前缀索引规则，所以这个语句在搜索索引树的时候，只能用 "张"，找到三个满足条件的记录（图中红框数据）。当然，这还不错，总比全表扫描要好。

然后呢？当然是判断其他条件是否满足。

在 MySQL5.6 之前，只能从满足条件的记录 id=18 开始一个个回表。到主键索引上找出数据行，再对比字段

而 MySQL 5.6 引入的索引下推优化（index condition pushdown），可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

它的整个执行的流程图是这样的：

InnoDB 在（name，age）索引内部就判断了 age 是否等于 38，对于不等于 38 的记录，直接判断并跳过。在我们的这个例子中，只需要对 id=18 和 id=65 这两条记录回表取数据判断，就只需要回表 2 次，这就是所谓的索引下推。