MySQL|索引

如何理解索引

索引的目的

我们可以将索引类比为字典、目录

在海量数据的查询时，我们可以借助原先生成并维护的索引，将每一次不同的复杂查询都以一种相同的查询顺序（模式）来进行

在使用索引时，本质上是通过不断地缩小想要获得的数据的范围来筛选出最终的结果，将随机的复杂查询目的数据，变成顺序的查询流程

磁盘 IO 与预读原理

在开始讨论索引设计之前，我们需要对计算机（操作系统）针对磁盘 IO 操作读取数据的优化有所了解

对于磁盘 IO 操作，实际上相比于直接访存获取数据而言是很慢的。大概一次 IO 的耗时，是访存的 10w 倍左右

因此计算机的操作系统会在一次 IO 操作读取数据时，不光光是读取指定地址的磁盘数据，而是读取这一地址附近的所有数据。（因为一般来说当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到）

这一地址附近的所有数据我们称之为页(page)，具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO

B+树索引

数据结构

在B+树中，叶子节点和非叶子节点有着明显的存储行为区别

• 非叶子节点不会存储真实数据，只会存储区间的左右端点数据（指引搜索方向的数据项），以及指针
• 只有叶子节点会存储实际的数据

例如上图中，磁盘上并未存储17和35这两个数据，实际存储的数据只有最下面一排叶子节点的数据，例如3、5、9等

索引的查找过程

例如查找29号数据，那么首先会在第一次IO，将磁盘块1加载到内存

然后发现29介于17与35之间，于是通过P2指针，得到磁盘块3的地址，将磁盘块3加载到内存，这是第二次IO

之后基于磁盘块3的数据（内存处理），发现29在26和30的中间，于是通过磁盘块3的P2指针，得到磁盘块8的地址，将磁盘块8加载到内存，这是第三次IO

之后基于磁盘块8的数据（内存处理），得到了29这条数据，查找结束，一共进行了3次磁盘IO操作

---

3层的B+树在实际的应用场景离可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的

如果没有索引，扫描所有数据项，每一个数据项都要发生一次磁盘IO，那么百万级别的数据中查找总共需要百万次的IO

覆盖索引和回表

InnoDB索引结构

在讨论覆盖索引和回表之前，我们需要先了解聚簇索引和二级索引。

假设我们有这么一张表，DDL内容如下：

CREATE TABLE product (
  id BIGINT PRIMARY KEY,     -- 主键
  name VARCHAR(100),
  category_id INT,
  description TEXT,
  stock_count INT,
  -- ... 其他字段
  INDEX idx_category (category_id) -- 我们在 category_id 上创建了一个索引
);

聚簇索引

当一张表有主键时，聚簇索引又叫做主键索引。

聚簇索引是按照每张表的主键构造一颗B+树，对MySQL而言，InnoDB会基于主键来构建这颗树；这棵树叶子节点中存放的是表每一行(包含全量字段)的数据记录。

类似按拼音排序的字典，拼音（主键）和内容（整行数据）是存放在一起的。

二级索引

二级索引又叫做非聚簇索引/辅助索引。

二级索引一般是我们手动设计并创建的索引，上面的例子中就是idx_category。二级索引所对应的B+树叶子节点存储的数据是 索引字段+主键字段，并不会像聚簇索引那样存储一行完整的数据。

类似字典的“偏旁部首检字表”。它只告诉你这个“偏旁”（category_id）对应的字的拼音（id）在第几页，但不会告诉你字的完整解释（整行数据）。

回表

SELECT name, description FROM product WHERE category_id = 123;

此时索引命中流程如下：

1. 查询条件是category_id，刚好是辅助索引。所以 InnoDB 根据 category_id 的辅助索引树，找到 category_id = 123 的所有记录，假设有3行，也就是在辅助索引树上有 3 个符合条件的叶子节点。

2. 这三个叶子节点的数据中，并不包含实际的行记录，但 category_id 都是 123，id 分别是 10, 20, 30

3. 但也仅此而已了，我们最终查询的结果需要 name 和 description 数据，但是这三个辅助索引树的叶子节点里只有 id 和 category_id 的值。

4. 于是 InnoDB 只能根据拿到的三个 id 值，重新回去查以主键 id 构建的聚簇索引树

5. “id = 10 的完整数据是什么？” -> 找到，取出 name 和 description。

   “id = 20 的完整数据是什么？” -> 找到，取出 name 和 description。

   “id = 30 的完整数据是什么？” -> 找到，取出 name 和 description。

上述“拿着二级索引查到的主键值，再返回聚簇索引查整行数据”的过程，就叫做回表。

分析上述流程，我们会发现导致回表的原因在于: select 的字段并未包含在辅助索引中。因此，当使用二级索引查询，但需要的列不在这个二级索引中时，就会发生“回表”。

回表是一个随机性IO，这一次二级索引拿到的符合条件的记录有3条，下一次可能是1w条，数据库就需要执行 1 次索引树查询 + 1w 次回表（随机 I/O），性能会非常差。

覆盖索引

知道回表是如何触发的，那么覆盖索引就是指: 索引列完美覆盖查询列的场景。

我们修改索引结构：

CREATE TABLE product (
  id BIGINT PRIMARY KEY,     -- 主键
  name VARCHAR(100),
  category_id INT,
  description TEXT,
  stock_count INT,
  -- ... 其他字段
  INDEX idx_multi (category_id, name) -- 索引扩展
);

查询语句:

SELECT id, name FROM product WHERE category_id = 123;

这一次，在根据 category_id = 123 去辅助索引树查找时，还是定位到那三个叶子节点。

但这次叶子节点的数据扩展了，包含 category_id, name, id 数据。

InnoDB 发现查询所需要的 id 和 name 字段在辅助索引树的叶子节点里都有，不再需要进行回表操作，这就是覆盖索引。

最佳实践

禁止使用SELECT *

通过上述讨论我们可以得出一个最佳实践：在对性能有严格要求的场景下，禁止使用 SELECT * 操作。

因为索引的设计必不可能包含所有列，而SELECT *会查询所有列记录，必定无法进行覆盖索引，必定回表，影响性能。

最左匹配原则与索引覆盖

一开始学习的时候很容易把这两个概念混在一起。实际上这两个概念是独立但是高度相关的。

概括总结就是：

最左匹配原则解决的是如何高效定位数据，可以理解为受到WHERE和ORDER BY的影响。

覆盖索引解决的是定位到数据后是否能直接满足查询需求，是否还需要回表。受到SELECT内容的影响。

他们的共同点是都和索引有关，因此在设计索引时需要综合考虑，同时兼顾最左匹配原则以及覆盖索引，避免回表查询。

最左匹配原则

主要的目的是为了高效筛选，定位符合查询条件的数据，还在查询条件过滤这一步。

这是由 B+ 树索引的数据结构决定的。

当创建一个联合索引 INDEX idx_abc (a, b, c) 时，可以将其想象成一个“多级排序”的电话簿：

1. 首先，所有条目严格按照 a 排序。
2. 在 a 相同的情况下，再按照 b 排序。
3. 在 a 和 b 都相同的情况下，最后按照 c 排序。

最左匹配原则就是：你必须从“最左边”的列（a）开始使用，才能利用上这个“排序”结构来快速缩小查询范围。

• WHERE a = ? -> 能用索引（高效定位）。
• WHERE a = ? AND b = ? -> 能用索引（高效定位）。
• WHERE a = ? AND b = ? AND c = ? -> 能用索引（高效定位）。

为什么 WHERE b = ? 不行？

• 因为 b 只有在 a 确定的情况下才是有序的。
• 如果直接查 b，b 在整个索引中是“乱序”的（B+树的第一层是按 a 排序的），数据库无法快速定位，只能全索引扫描（Index Full Scan）或全表扫描（Table Scan）。

所以从查询流程的先后顺序来看，最左匹配原则是首要目的，是让你能用上索引的 B+ 树快速搜索能力，而不是进行全表扫描。如果连最左匹配都不满足，那么只好全扫，性能最差，更谈不上覆盖索引了。

覆盖索引

覆盖索引的目的是：仅仅通过辅助索引，查询条件过滤完，定位到符合条件的辅助索引树叶子节点后，能不能直接满足查询需求，不用再回表。

所以从查询流程的先后顺序来看，覆盖索引场景在最左匹配原则生效的后面。

最佳实践

在设计索引时，最左匹配是必须要遵守的原则。这直接决定了是否能让 WHERE 子句命中索引，是优化的前提。

覆盖索引是在最左匹配的基础上，尽可能让查询只通过一次二级索引（辅助索引）树就获取到查询所需的所有列数据，省略回表的IO消耗。

Reference

https://www.cnblogs.com/TheMagicalRainbowSea/p/18760275

https://tech.meituan.com/2014/06/30/mysql-index.html