图文并茂说MySQL索引——入门进阶必备

àì夳堔傛蜴生んèń 2022-10-07 11:48 229阅读 0赞

> 本篇是我阅读《MySQL是怎样运行的》一书的笔记，我简化了一些概念，删除了一些不容易新手入门理解的内容，增加了第八节`MRR`说明，在这里分享给大家。

### 文章目录 ###

*  1.索引介绍
 *  2.当你插入记录，页中有什么变化？
 *  3.聚集索引
 *  4.非聚集索引(二级索引)
 *  5.联合索引
 *  6.索引覆盖
 *  7.非聚集索引一定会查询多次吗？如何避免回表？
 *  8.MRR的原理（Disk-Sweep Multi-Range Read）
 *  9.普通索引和唯一索引，应该建立哪个？（进阶选读）
 *   *  9.1 查询过程
     *  9.2 更新过程
     *  9.3 change buffer的使用场景
 *  10.B+树的应用场景

# 1.索引介绍 #

你一定看到过这样的例子，索引是什么，你要查字典，不可能从第一页翻到最后一页去查找，你会先查找拼音或者偏旁部首，然后直接跳转到对应的页小范围的一条一条查找，这样会快得多。

索引也是类似，建立索引就是按照某种规则建立一颗`B+`树，在`B+`树查询到符合要求的记录就类似于查询到拼音或者偏旁部首一样，最后回表就能很快的查找到完整具体的记录。在这里，我会带大家来看看记录的插入是如何变化的，记录原理是什么。

假设数据表`index_demo`是这样的：

CREATE TABLE index_demo(
        c1 INT,
        c2 INT,
        c3 CHAR(1),
        PRIMARY KEY(c1)
    )charset=utf8mb4;

你插入的每条记录的行格式，我们将其简化为如下

![20210617163408898.png][]

*  `record_type`：记录头信息的一项属性，表示记录的类型，**`0`表示普通记录，`1`表示目录项记录，`2`表示`Infimum`记录(最小记录的上一条记录)，`3`表示`Supremum`记录(最大记录的下一条记录)。**
 *  `next_record`：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁。
 *  各个列的值：这里只记录在`index_demo`表中的三个列，分别是`c1`、`c2`和`c3`。
 *  其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

所以，你插入记录后，结构应该是这样的。

![20210617165022958.png][]

--------------------

# 2.当你插入记录，页中有什么变化？ #

我们假设每个数据页最多能存放`3`条记录（实际上一个数据页非常大，可以存放好多条记录）。

向`index_demo`插入`3`条记录

INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');

变化如下:  
![20210617165500828.png][]

可以看到，这些记录组成了单链表，并且按照主键值从小到大的顺序将记录排序。`innodb`要求插入记录必须这么做。

接着我们在插入一条记录

INSERT INTO index_demo VALUES(4, 4, 'a');

`innodb`还要求，**下一个数据页**用户记录的主键值**大于上一个页**中用户记录的主键值。

而页`10`最多存放`3`条数据记录，所以不得不再分配一个新页。

![20210617170324516.png][]

细心的小伙伴看到此图主键值`4`的记录在`5`的后面，别急，下面马上讲到。

这里分配的页号为什么是`28`而不是`11`呢？学过数据结构的人就知道，链表新增结点都是随机分配一块空间，在内存上并不是连续的，这里就假设为`28`，用来说明这个内存的不连续性。

不管对页中的记录是增加、删除还是修改，我们必须遵守"**下一个数据页**用户记录的主键值**大于上一个页**中用户记录的主键值"这个规则。为了维持这个规则，往往伴随记录的移动，甚至需要为记录分配新页，这个过程也叫**页分裂**。

![20210617172001662.png][]

假设此时你往表中插入了很多条记录，如下

![20210617172308773.png][]

之前说过，查字典不可能从头开始一个个往后查，记录也是一样，不可能一条条顺序往后找，那么`innodb`是怎么做的呢？

那就是给这些记录一个目录！

![2021061717242641.png][]

文章开头就提到了的`record_type`属性，它的各个取值代表的意思如下：

0：普通的用户记录  
1：目录项记录  
2：`Infimum`记录  
3：`Supremum`记录

可以看到，目录项记录的`record_type`值是`1`，而普通用户记录的`record_type`值是`0`。

目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有`InnoDB`自己添加的隐藏列。

**那`innodb`怎么查询呢？**

以查找主键为`8`的记录为例。

1.  先到存储目录项记录的页（页`30`）中通过二分法快速定位到用户记录页，因为`5< 8< 12`，所以定位到对应的记录所在的页就是页`28`。
2.  再到存储用户记录的页`28`中根据单链表遍历定位到主键值为`8`的用户记录。

目录项比较多一页放不下怎么办？那就和用户记录一样进行页分裂。

我们假设一个目录页最多存放`4`条目录项记录(真实情况是可以存放很多条)，如果此时再插入一条主键值为`320`的用户记录，那就需要再分配一个新的页去存放目录了。

![20210617173851264.png][]

从图中可以看出，我们插入了一条主键值为`320`的用户记录之后需要两个新的数据页：

1.  为存储该用户记录而新生成了页`31`。
2.  因为原先存储目录项记录的页`30`的容量已满（我们前边假设只能存储`4`条目录项记录），所以不得不需要一个新的页`32`来存放页`31`对应的目录项。

假如还是查找主键为`8`的记录，此时`innodb`该如何查询？

1.  确定目录项在哪个页。页`30`的目录项记录的主键值的范围是`[1, 320)`，页`32`表示的目录项记录的主键值范围`[320, +∞)`，显然主键值为`8`的记录在页`30`中。
2.  通过目录页确定用户记录页。因为`5< 8< 12`，所以用户记录在页`28`中。
3.  在真正用户记录页中定位到具体记录。这个就是单链表遍历即可。

如果表中的数据确实是很多，会产生很多存储目录项的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？

那就是为这些存储目录的页再生成一个更高级的目录页，就像是一个多级目录一样。

![20210617192940956.png][]

我们生成了一个存储更高级目录项的页`33`，这个页中的两条记录分别代表页`30`和页`32`，如果用户记录的主键值在`[1, 320)`之间，则到页`30`中查找更详细的目录项记录，如果主键值范围是`[320, +∞)`，就到页`32`中查找更详细的目录项记录。随着表中记录的增加，这个目录的层级会继续增加。

> 有人做过这样一个计算，假如叶子结点代表的数据页可以存放`100`条用户记录，所有目录页可以存放`1000`条目录项记录，那么：  
> 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录。  
> 如果B+树有2层，最多能存放1000×100=100000条记录。  
> 如果B+树有3层，最多能存放1000×1000×100=100000000条记录。  
> 如果B+树有4层，最多能存放1000×1000×1000×100=100000000000条记录。（一千亿条记录）  
> 一般都不会超过这个数字，也就是说B+树一般不超过4层，可以通过二分法快速定位记录，然后小范围遍历即可。

--------------------

# 3.聚集索引 #

刚刚上面几节所画的`B+`树全部都是按照**聚集索引**(主键值)排序的，可以说`B+`树本身就是一个索引。聚集索引有以下`2`个特点

1.使用主键值大小进行记录和页的排序，都是按照主键值升序排列，记录之间是单链表结构，页与页之间是双链表结构。

2.`B+`树的叶子结点是完整的用户记录，也就是叶子结点存储了所有列的值(包括隐藏列)。

具有这`2`个特点的`B+`树称为聚集索引，聚集索引**不需要**显式使用`INDEX`语句创建，如下

CREATE INDEX 索引名称 ON 表名(字段);
    ALTER TABLE 表名 ADD INDEX 索引名称(字段);

`innodb`自动为我们创建聚集索引。

> 注意：  
>   有一个点很容易混淆，走`PRIMARY`索引和全表扫描有什么区别呢？他们其实**都是在聚集索引上操作**的（聚集索引`B+`树的叶子结点是根据主键排好序的完整的用户记录，包含表里的所有字段），区别就在于  
>   
>   全表扫描将聚集索引`B+`树的叶子结点依次顺序扫描并判断条件，在以下几种情况会走全表扫描：
> 
>  *  `select * from demo_info`这种无条件的查询语句
>  *  `select * from demo_info where common_field != 'a'`这种条件字段`common_field`没有建索引的情况
>  *  `select * from demo_info order by key1 limit 10000, 1`条件字段`key1`建了索引但是`MySQL`认为走二级索引的成本比全表扫描成本高的情况。  
>       
>     
> 
>   `PRIMARY`索引是利用二分思想将聚集索引`B+`树到指定范围区间进行扫描，比如`select * from demo_info where id in (1, 2)`这种条件字段是主键`id`，可以很好的利用到索引进行二分的快速查询。

--------------------

# 4.非聚集索引(二级索引) #

你肯定遇到过这样的情况，每次查询的时候，`where`条件并不是按照主键`id`去筛选条件，比如查询`test`表中的`session_id`是"`abc`"的记录

select * from test where session_id = "abc";

很显然，除了主键使用默认聚集索引以外，你并没有手动添加其他的索引。那么根据条件去筛选的时候就只能沿着链表依次遍历了。有没有更好的方法呢？

当然有！我们可以多建几颗`B+`树啊，不同的`B+`树可以采用不同的排序规则。比如刚刚的`index_demo` 表中的`c2`列的值的大小作为记录和页的排序规则，再建这样一个规则的`B+`树。

![20210617213724991.png][]

看看这个图，是不是和聚集索引很像？但是还是有点不同。

1.  `B+`树的叶子结点存储的不是完整的用户记录，没有全部列的信息，**只有`c2`列和主键列这两个列的值。**
2.  目录项记录不再是主键+页号，而是`c2`列+页号。
3.  使用记录`c2`列的大小进行记录和页的排序。不管是用户记录页还是目录页，都是按照`c2`列的大小升序排列的单链表结构。

创建了非聚集索引后，现在想要查询`where c2 = 4`的记录的步骤如下：

1.  确定第一条符合`c2 = 4`的目录项所在的页。
2.  确定第一条符合`c2 = 4`的用户记录所在的页。
3.  找到符合`c2 = 4`的第一条用户记录。找到该记录后，由于只存储了`c2`列和主键`c1`，所以需要根据该记录的主键信息到聚集索引中查找完整的用户记录（**回表**）。然后返回非聚集索引的叶子节点处，找到刚才定位到的符合条件的记录，继续往后扫描，因为`c2`列没有唯一键`unique`约束，可能满足`c2 = 4`的有多条记录，搜索完本页就跳到下一页第一条记录继续往后扫描，每找到一条满足的记录就进行一次回表操作，重复这个过程，直到下一条记录不满足`c2 = 4`为止。

> 注意：值为`NULL`的非聚集索引记录都会被放到`B+`树的最左边。在上图中，如果插入`c2 = NULL`的记录，那么该`B+`树叶子节点中，将会在`c2 = 2`记录的左边，因为`MySQL`认为`NULL`值是最小的。

--------------------

# 5.联合索引 #

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比如说我们想让`B+`树按照`c2`和`c3`列的大小进行排序，那么

1.  先把各个记录和页按照`c2`列进行排序。
2.  在记录的`c2`列相同的情况下，采用`c3`列进行排序

为`c2`和`c3`列建立的索引，如下：

![20210617223218165.png][]

每条**目录项记录**都由`c2`、`c3`、页号这三个部分组成，各条记录先按照`c2`列的值进行排序，如果记录的`c2`列相同，则按照`c3`列的值进行排序。可以看图中的页`50`和页`55`，当`c2 = 4`的时候，`c3`按照从小到大的顺序一次是`"a"`，`"o"`，`"u"`，

每条**用户记录**由`c2`、`c3`和主键`c1`列组成。

--------------------

# 6.索引覆盖 #

`explain`查询`sql`执行计划时，`Extra`显示`Using index`时，能够触发索引覆盖。**索引覆盖无需回表**，需要查询的字段已经都在该`B+`树上了。索引已经“覆盖了”我们的查询需求，所以称为覆盖索引。

--------------------

# 7.非聚集索引一定会查询多次吗？如何避免回表？ #

比如有一个联合索引`idx_c2_c3(c2, c3)`，`select c3 from 表名 where c2 = 4;`就只需要查询一次辅助索引就可以了，因为我需要查询的值正好是索引之一，一棵索引树上就能获取`SQL`所需的列数据（索引覆盖），无需回表，速度更快。

> 注意：当你建立`c2`, `c3`联合索引之后却看到`Extra`显示`Using index condition; Using filesort`，一般是使用了`where c2 = "xx" order by c3 desc`这样的形式，有人认为`Using filesort`就是因为`c3`需要`order by`才导致外部排序，实际上是你联合索引顺序建反了，`index(c2, c3)`错误的写成了`index(c3, c2)`，导致`B+`树优先按照`c3`排序，`c3`相同时，才按照`c2`排序，这样和写的`sql`意义不符合，具体可以看上面联合索引的图片理解

--------------------

# 8.MRR的原理（Disk-Sweep Multi-Range Read） #

每次根据主键回表时，虽然是按照非聚集索引排好序的，但是这些记录的主键`id`是无序的，也就是说，这些非聚集索引记录对应的聚集索引记录所在的页面也是无序的。每次回表都要重新定位页的位置，将聚集索引页读取出来，这些非连续`I/O`的性能开销很大。

因为大多数的数据都是按照主键递增顺序插入得到的，所以我们可以认为，如果按照主键递增顺序查询的话，对磁盘的读比较接近顺序读，能够提升读性能。

于是，便有了`MRR`(`Disk-Sweep Multi-Range Read`，多范围读取)的优化措施。即先读取一部分满足条件的非聚集索引记录，将它们的主键值排好序之后再统一回表，相比于每读取一条非聚集索引记录就回表，这样会节省一些`I/O`开销（比如记录更有可能在同一页）。

`MRR`优化的设计思路如下：

1.  根据非聚集索引`a`，定位到满足条件的记录，将`id`值放入`read_rnd_buffer`中;
2.  将`read_rnd_buffer`中的`id`进行递增排序；
3.  排序后的`id`数组，依次到主键`id`索引中查记录，并作为结果返回。

这里`read_rnd_buffer`的大小是由`read_rnd_buffer_size`参数控制的 (运行`show variables like 'read_rnd_buffer_size'`查看大小，默认`256K`)。如果步骤`1` 中，`read_rnd_buffer`放满了，就会先执行完步骤`2`和`3`，然后清空`read_rnd_buffer`。之后继续找索引`a`的下个记录，并继续循环。

按照官方文档的说法，计算成本的时候，会更倾向于不使用`MRR`，把`mrr_cost_based`设置为`'off'`(默认是`'on'`)，就是固定使用`MRR`了。经过我的测试，如果按照非主键`id`排序，则无论如何不会使用`MRR`。

默认情况下，`mrr_cost_based`是`on`，查看`sql`执行计划如下。

explain select * from demo_info where key2 between 124 and 135

![20210722161456409.png][]

`Extra`并没有出现`Using MRR`。

查询结果

select * from demo_info where key2 between 124 and 135

![20210722161621131.png][]

结果集是按照索引`key2`的顺序排列的。

然后运行如下代码，只要没有使用非主键`id`的`order by`排序，优化器能使用`MRR`的时候就一定会使用。

set optimizer_switch="mrr_cost_based=off"
    explain select * from demo_info where key2 between 124 and 135

![20210722161310380.png][]

查看运行结果

![20210722161907242.png][]

由于我们在`read_rnd_buffer`中按照`id`做了排序，所以最后得到的结果集也是按照主键`id`递增顺序的

如果执行排序之后呢？

explain select * from demo_info where key2 between 124 and 135 order by key2

![20210722162222581.png][]

结果显示，按照非主键`id`排序，一定不使用`MRR`

`MRR`能够提升性能的核心在于，这条查询语句在索引上做的是一个范围查询，可以得到足够多的主键`id`。这样通过排序主键`id`以后，再去主键索引查数据，才能体现出“顺序性”的优势。

我在之后的文章将会忽略这个概念，直接认为每读取一条非聚集索引记录就立即回表操作，但是不排除面试会问到这个问题，大家需要了解一下。

--------------------

# 9.普通索引和唯一索引，应该建立哪个？（进阶选读） #

首先说明，普通索引和唯一索引都是非聚集索引，写法上就是`index`和`unique index`的区别。

## 9.1 查询过程 ##

假设执行查询的语句是 `select id from table where t = 6`，我们对`t`这个字段建立了索引。

*  对于普通索引来说，查找到满足条件的第一个记录后，需要查找下一个记录，直到碰到第一个不满足`t=6`条件的记录。
 *  对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索。

这个不同带来的性能差距会有多少呢？微乎其微，都是常量级别的查找。

大家都知道，`InnoDB`的数据是按数据页为单位来读写的。当需要读一条记录的时候，并不是将这条记录本身从磁盘读出来，而是以页为单位，将其整体读入内存。在`InnoDB`中，每个数据页的大小默认是`16KB`。

因为引擎是按页读写的，所以说，当找到`t=6`的记录的时候，它所在的数据页就都在内存里了。那么，对于普通索引来说，要多做的那一次“查找和判断下一条记录”的操作，就只需要一次指针寻找和一次计算。

当然，如果`t=6`这个记录刚好是这个数据页的最后一个记录，那么要取下一个记录，必须读取下一个数据页，这个操作会稍微复杂一些，但也只是增加少量的`IO`成本，除非数据量极为巨大。

## 9.2 更新过程 ##

为了说明普通索引和唯一索引对更新语句性能的影响这个问题，需要先了解一下`change buffer`

当需要更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，`InnoDB`会将这些更新操作缓存在`change buffer`中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行`change buffer`中与这个页有关的操作。通过这种方式就能保证这个数据逻辑的正确性。

需要说明的是，虽然名字叫作`change buffer`，实际上它是可以持久化的数据。也就是说，`change buffer`在内存中有拷贝，也会被写入到磁盘上。

将`change buffer`应用到旧的数据页，得到新的数据页的过程，称为`merge`。除此之外，系统有后台线程会定期`merge`。在数据库正常关闭（`shutdown`）的过程中，也会执行`merge`操作。

如果能够将更新操作先记录在`change buffer`，减少读磁盘，语句的执行速度会得到明显的提升。而且，数据读入内存是需要占用`buffer pool`的，所以这种方式还能够避免占用内存，提高内存利用率。

那么什么条件下可以使用`change buffer`呢？

对于唯一索引来说，所有的更新操作都要先判断这个操作是否违反唯一性约束。比如，要插入`t=7`这个记录，就要先判断现在表中是否已经存在`t=7`的记录，而这必须要将数据页读入内存才能判断。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用`change buffer`了。

**因此，唯一索引的更新就不能使用`change buffer`，只有普通索引可以使用。**

`change buffer`用的是`buffer pool`里的内存，因此不能无限增大。`change buffer`的大小，可以通过参数`innodb_change_buffer_max_size`来动态设置。这个参数设置为`50`的时候，表示`change buffer`的大小最多只能占用`buffer pool`的`50%`。

理解了`change buffer`的机制后，那么我们再一起来看看如果要在这张表中插入一个新记录`t=7`的话，`InnoDB`的处理流程是怎样的。

第一种情况是，这个记录要更新的目标页在内存中。这时，`InnoDB`的处理流程如下：

*  对于唯一索引来说，找到合适的位置，判断到没有冲突，插入这个值，语句执行结束；
 *  对于普通索引来说，找到合适的位置，插入这个值，语句执行结束。

这样看来，普通索引和唯一索引对更新语句性能影响的差别，只是一个判断，只会耗费微小的`CPU`成本。

但这不是我们关注的重点。

第二种情况是，这个记录要更新的目标页不在内存中。这时，`InnoDB`的处理流程如下：

*  对于唯一索引来说，需要将数据页读入内存，判断到没有冲突，插入这个值，语句执行结束；
 *  对于普通索引来说，则是将更新记录在`change buffer`，语句执行就结束了。

**将数据从磁盘读入内存涉及随机IO的访问，是数据库里面成本最高的操作之一**。`change buffer`因为减少了随机磁盘访问，所以对更新性能的提升是会很明显的。

如果业务有大量插入数据的操作，`where`条件如果是唯一索引判断插入，会比普通索引有明显的阻塞感。

>   如果大家对于`IO`成本和`CPU`成本的计算感兴趣，可以见我另一篇文章：[MySQL查询为什么选择使用这个索引？——基于MySQL8.0.22索引成本计算][MySQL_MySQL8.0.22]

## 9.3 change buffer的使用场景 ##

通过上面的分析，大家知道了使用`change buffer`对更新过程的加速作用，也清楚了`change buffer`只限于用在普通索引的场景下，而不适用于唯一索引。那么，现在有一个问题就是：**普通索引的所有场景，使用`change buffer`都可以起到加速作用吗？**

因为`merge`的时候是真正进行数据更新的时刻，而`change buffer`的主要目的就是将记录的变更动作缓存下来，所以在一个数据页做`merge`之前，`change buffer`记录的变更越多（也就是这个页面上要更新的次数越多），收益就越大。

因此对于写多读少的业务来说，页面在写完以后马上被访问到的概率比较小，此时`change buffer`的使用效果最好。这种业务模型常见的就是账单类、日志类的系统。

反过来，假设一个业务的更新模式是写入之后马上会做查询，那么即使满足了条件，将更新先记录在`change buffer`，但之后由于马上要访问这个数据页，会立即触发`merge`过程。这样随机访问`IO`的次数不会减少，反而增加了`change buffer`的维护代价。对于这种业务模式来说，`change buffer`反而起到了副作用。

--------------------

# 10.B+树的应用场景 #

由于篇幅原因，我这里另开一篇，请见下一篇：[MySQL中B+树索引的应用场景大全  
][MySQL_B_]

--------------------

欢迎一键三连~  
  
有问题请留言，大家一起探讨学习  
  
\----------------------Talk is cheap, show me the code-----------------------

[20210617163408898.png]: /images/20221005/a3b231eae94647cb93a437c2ee49741a.png
[20210617165022958.png]: /images/20221005/d013da70cafd47e6a554e148a69d4125.png
[20210617165500828.png]: /images/20221005/ebe35223831d4851948a402d48b7380b.png
[20210617170324516.png]: /images/20221005/daab72bf4d9f4047868df7fc336176fb.png
[20210617172001662.png]: /images/20221005/b93c572ca36d43e8a085ab41b590c2f0.png
[20210617172308773.png]: /images/20221005/863dd2202b864aae85c748fd5d5e371c.png
[2021061717242641.png]: /images/20221005/07a838b5c1044a43b1d530564b304a53.png
[20210617173851264.png]: /images/20221005/529ee18396064bee90ff0c1993f2cbaa.png
[20210617192940956.png]: /images/20221005/53e67420bf46404ea091f42b907f2530.png
[20210617213724991.png]: /images/20221005/51bff631d7534c0689b6e607554edf69.png
[20210617223218165.png]: /images/20221005/2fa46d759e7b428391976e4f4dade1b5.png
[20210722161456409.png]: /images/20221005/878cf2e3d8e6483aad6ea2564282fbc5.png
[20210722161621131.png]: /images/20221005/2eea034e0fb64a35a4518069b1db1066.png
[20210722161310380.png]: /images/20221005/0665f64c495d4e3fa88d2c00d6efe724.png
[20210722161907242.png]: /images/20221005/60e9d6fd335a4122bd1ddcc1ffee8443.png
[20210722162222581.png]: /images/20221005/39ddad684df34ec18c153d3c4a26cda7.png
[MySQL_MySQL8.0.22]: https://blog.csdn.net/qq_34115899/article/details/120217907
[MySQL_B_]: https://blog.csdn.net/qq_34115899/article/details/118308424