什么是索引

索引是一种排好序数据结构，用于帮助我们在大量的数据中快速定位到我们想要查询的数据。就像一本书的目录，能够快速定位我们想要找的内容。

InnoDB 中的索引

MySQL 中索引是由存储引擎实现的。下面主要分析 InnoDB 存储引擎下的索引算法及实现。

InnoDB 存储引擎下常见的几种索引：

• B+ 树索引
• 哈希索引
• 全文索引

B+ 树索引

B+ 树索引是 MySQL 数据库中最为主要和最常见的索引。

为什么使用 B+ 树作为索引结构？

Hash

Hash 结构增删改查效率都比较高，Hash 索引适合精确查找，但是对于范围查询不合适。

对每一行数据进行 hash 运算，得到的 hash 码之间没有顺序性，所以对范围查询只能全表扫描。

二叉查找树

二叉树的特点是：

1. 非叶子节点最多拥有两个子节点。
2. 左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。

这颗二叉树的确可以提高我们的查询效率，但是同样是这几个数据，也可以构造出如下二叉树：

显然这颗二叉树就蜕变成链表了，查询效率明显降低了。

由于二叉树这个特性，在实践中很少使用二叉树，一般只是作为理论讲解。

平衡二叉树

在满足二叉查找树的前提下，还要满足任何节点的两个子树的高度差为 1。如下图所示：

平衡二叉树的查询速度很快，但是维护一颗平衡二叉树的代价非常大，通常来说，需要1次或者多次的左旋和右旋来得到插入或更新后树的平衡性。

随着数据量的增加，平衡二叉树的高度也会不断增加，查询速度也很变的越来越慢。树高也决定了 I/O 次数过多。

如果是范围查询，会出现回旋查找问题，导致查询速度变慢。比如查询 id > 3 的数据，需要先找到 3 节点，然后再回旋找到 5，6，7，8 节点。

平衡二叉树一般用于内存结构对象中。

B 树

是一种多路平衡搜索树，一个m阶的B树具有如下特点：

1. 根结点至少有两个子女。
2. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m。
3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
4. 所有的叶子结点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

如下图所示：

相对 AVL 树，存放的数据更多，树的高度更矮，磁盘 I/O 次数减少。

范围查找还是要回旋查找，范围查找效率太低。

B+ 树

和 B 树相似，但是和 B 树不同的是：

1. B+ 树所有数据节点都是按键值的大小顺序存放在同一层的叶子节点上，各叶子节点指针连接，形成链表。
2. B+ 树叶子节点才会保存数据，其他节点只会存储索引本身。

B+ 树中的B是平衡（Balance），而不是二叉（Binary）。B+ 树是由 B 树演化来的。B+ 树是为磁盘或者其他直接存取辅助设备设计的一种平衡查找树。

总结，MySQL索引使用 B+ 树优点：

1. B+ 树磁盘 I/O 次数少，相对于 B 树来说，B+ 树没有中间数据，相同的磁盘页可以容纳更多的索引元素，所以 B+ 树比 B 树更加低矮，因此查询时磁盘 I/O 次数也更少。
2. B+ 树范围查询效率高，B+ 树做范围查询只需要找到链表上的索引元素，然后遍历链表即可，简单高效。
3. B+ 树查询更加稳定，B+ 所有查询都要查询到叶子节点。

在数据库中，B+ 树的高度一般都在24层，也就是说查询某一个键值记录最多需要24次的磁盘 I/O，当前一般机械磁盘一次 I/O 大约需要花费0.01秒。

B+ 树索引分类

InnoDB 中的 B+ 树索引可以分为 聚集索引（clustered index） 和 辅助索引（secondary index） ，他们的内部都是 B+ 树结构，聚集索引和普通索引的不同是，叶子节点存放的是否是一整行的信息。

聚集索引

聚集索引是按照表中的主键顺序构造一棵 B+ 树，非叶子节点称为索引页，叶子节点称为数据页，索引页存放的是键值及指向数据页的偏移量，数据页存放的是完整的每行记录。每个数据页都通过一个双向链表进行链接，页中的数据通过单向链表链接。每张表只有一个聚集索引。

对于聚集索引来说，索引即数据，数据即索引。

聚集索引查询流程

select * from emp where id = 3

以上的 sql 语句执行流程：

1. 首先从根索引页查询（根索引页一般常驻内存），因为 id=3，二分查找法定位到数据页8。
2. 将数据页8 加载到内存。
3. 在数据页8 中继续查找，利用二分查找法定位到具体数据行，返回行全部数据。

辅助索引

辅助索引又称非聚集索引，叶子节点并不包含行记录的全部数据，除了包含键值以外，还包含了聚集索引键（表中主键）。每张表中可以有多个辅助索引。

辅助索引查询流程：

select * from emp where name='jack'

以上 sql 语句执行流程：

1. 在根索引页查询，定位到数据页8。
2. 将数据页8 加载到内存。
3. 二分法查找到 name='jack' 数据对应的主键3。 和上面 sql 执行步骤1，2，3一致。
4. 然后在根据 id=3 去聚集索引上查询（过程和上面 sql 一致）。这个操作也称为回表。

根据辅助索引查询，并没有查询到所需的字段值，此时就需要再次通过主键从聚集索引中查找，这个过程称为回表。

InnoDB 和 MyISAM 存储结构

在 MyISAM 中只存在辅助索引，B+ 树的叶子节点存放的是索引键值和数据对应的地址，索引和数据的存储是分开的。

MyISAM 主键索引结构:

MyISAM 辅助索引结构：

InnoDB 和 MyISAM 磁盘存储结构：

表 seed_innodb 存储引擎为 InnoDB，表 seed_myisam 存储引擎为 MyISAM。

• InnoDB 类型的表包含两个文件

  • *.frm ：描述表的定义
  • *.ibd ：表的索引和数据（大小始终都是16384（16k）的整数倍）

• MyISAM 类型的表包含三个文件

  • *.frm ：描述表的定义
  • *.MYD ：表的数据文件
  • *.MYI ：表的索引文件

联合索引

联合索引是指对表中的多列建立索引，如下图，对表中name, age, mobile 字段建立联合索引：

InnoDB 在维护该联合索引时，首先会先根据 name 字段排序，name 字段值相同的话会根据 age 字段值排序，如果 age 也相同，则会按照手机号排序，如果手机号也相同，就会按照主键来排序。

联合索引优点：

1. 建立一个索引，相当于多个索引使用，比如上图联合索引相当于3个索引，分别是：（name），（name，age），（name，age，mobile）。
2. 联合索引已经对第二个值之后进行了排序处理，如果需要对后面的字段进行排序，这时使用联合索引可以避免多一次的排序操作（Using filesort）。
3. 可以使用到索引覆盖，避免了回表查询。

最左前缀

使用联合索引必须遵守最左前缀原则，如上图，联合索引都是排好序的，如果不能确定联合索引的第一个元素，就无法向后查找。

索引覆盖

从辅助索引中就可以查询到所需字段，不需要回表查询聚集索引。

select age, mobile from emp where name='jack'

以上 sql 语句执行流程：

1. 在根索引页查询，定位到数据页8。
2. 将数据页8 加载到内存。
3. 二分法查找到 name='jack' 数据对应的 age，mobile 字段返回。

索引覆盖优点：

辅助索引不包含整行记录的信息，所以大小远远小于聚集索引，因此可以减少大量的 I/O 操作。

索引优化

MRR(Multi-Range Read) 多范围查找 优化

MySQL 5.6 开始支持的 MRR 优化，可适用于 range，ref，eq_ref 类型的查询。

MRR 优化的目的就是为了减少磁盘的随机访问，将随机访问转化为较为顺序的数据访问，这对 IO-bound 类型的 SQL 查询语句带来性能极大的提升。

对于 InnotDB 和 MyISAM 存储引擎的范围查询和 JOIN 查询操作，MRR 的工作方式：

1. 将查询得到的辅助索引键值存放到一个缓存中。
2. 将缓存中的键值根据 RowID 进行排序。
3. 根据 RowID 的排序顺序来访问实际的数据文件。

下图是未启用 MRR 查询方式，首先查询辅助索引，然后回表继续查询，在回表查询时可能发生大量的随机I/O。

启用 MRR 查询方式：

执行器对查询数据缓存并根据 rowid 进行排序，再回表查询，这样就将随机 I/O 转化为了 顺序 I/O。

查询是否启用 MRR:

SHOW VARIABLES LIKE '%optimizer_switch%';

当 mrr=on 时，表示启用 MRR 优化，mrr_cost_based 表示告诉优化器基于使用 MRR 的成本来选择是否启用 MRR 优化。若 mrr=on, mrr_cost_based=off，表示总是启用 MRR 优化。

总是开启 MRR 优化：

SET optimizer_switch='mrr=on,mrr_cost_based=off';

基于优化器判断是否开启 MRR 优化（默认）：

SET optimizer_switch='mrr=on,mrr_cost_based=on';

关闭 MRR 优化：

SET optimizer_switch='mrr=off,mrr_cost_based=on';

参数 read_rnd_buffer_size 用来控制缓冲区大小，如果缓冲区满了就会先把 rowid 排好序去磁盘查询，然后清空缓冲区，接下来继续往缓冲区里存放数据、排序、查询，如此循环

查询 read_rnd_buffer_size ：

SHOW VARIABLES LIKE '%read_rnd_buffer_size%';

默认大小 256K。

一条语句如果使用 MRR 优化，会在执行计划的 Extra 字段显示 Using MRR

ICP(Index Condition Pushdown) 索引下推 优化

在联合索引中，如果不符合最左前缀原则，比如使用了范围查询，这时就会走索引下推。

MySQL 5.6 开始支持索引下推，支持 range、ref 、eq_ref、ref_or_null 类型的查询，InnoDB 和 MyISAM 都支持索引下推。

索引下推是在存储引擎层使用索引过滤数据的一种优化方式，仅支持辅助索引。

非索引下推：当进行索引查询时，首先根据索引来查找记录，返回 Server 层后，再根据 WHERE 条件过滤记录。

索引下推：根据辅助索引查询数据的同时，判断是否可以进行 WHERE 条件的过滤（这个 WHERE 条件的过滤是放在了存储引擎层的），然后将符合 WHERE 条件数据返回 Server 层。

索引下推优点：

• 减少回表次数，只有在完全符合条件的时候才会回表查询，
• 减少返回给 Server 层的数据，减少 I/O 操作。

举个例子：

select * from user where name like '张%' and age < 18;

未启用索引下推的流程：

1. MySQL Server 层调用存储引擎层，
2. 存储引擎层通过联合索引（idx_name_age）找到以张开头的数据，
3. 回表查询，
4. 重复 2，3 步骤，直到将符合条件（以张开头）的数据全部取出，
5. 将查询到的数据返回给 Server 层，Server 层根据age条件对结果进行过滤。

启用索引下推流程：

1. MySQL Server 层调用存储引擎层，
2. 存储引擎层通过联合索引（idx_name_age）找到以张开头的数据，再根据联合索引中的age进行过滤，
3. 找到符合条件（以张开头并且age小于18）的数据，回表查询，
4. 重复 2，3 步骤，直到将符合条件的数据全部取出，
5. 将查询到的数据返回给 Server 层。

如果执行计划的 Extra 字段显示 Using index condition，则说明使用了 ICP 优化：

查看索引下推状态：

SHOW VARIABLES LIKE '%optimizer_switch%';

默认开启。

注意：

• 只有联合索引下，才能使用索引下推。
• explain Extra 字段显示 Useing indx condition 不一定走了索引下推，前提使用的索引必须是联合索引。

HASH 索引

InnoDB 存储引擎使用哈希索引是自适应的，仅是数据库自身创建并使用，不能人为进行干预。自适应哈希索引经过哈希函数映射到一个哈希表中，所以对于字典类型的查找非常快速，如： select * from table where index_col='xxx'。但是对于范围查询就无能为力了。

全文索引

InnoDB 1.2 之后才使用的全文索引。使用的较少。