《MySQL实战45讲》——学习笔记04-05 “深入浅出索引、最左前缀原则、索引下推优化“

朴灿烈づ我的快乐病毒、 2023-09-28 22:27 12阅读 0赞

### 04 | 深入浅出索引（上） ###

#### 1. 什么是索引？ ####

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样，书有500页，每页存的都是书的内容，目录可能只有5页，只存了页码；通过目录能快速找到某个主题的页码，从而快速找到内容；

#### 2. 索引的常见模型 ####

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，称之为索引模型；这里介绍三种常见也比较简单的数据结构：哈希表、有序数组、搜索树；

*  **哈希表**

是一种以键-值（key-value）存储数据的结构，输入待查找的键即key，就可以找到其对应的值即Value；

哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个数组下标，然后把value放在数组的这个位置；

hash的问题就是冲突，不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况；处理这种情况的一种方法是，"拉链法"，即同数组下标的值放在一个链表中；假设，现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

![e1353eb462d64050afbb9f1a7f62fcd3.png][]

图中，User2和User4根据身份证号算出来的key值都是N；查ID\_card\_n2对应的名字，处理步骤就是：首先将ID\_card\_n2通过哈希函数算出N；然后，按顺序遍历N下的链表，找到User2；

需要注意的是，图中四个ID\_card\_n的值（key值）**并不是递增的**；新增User记录时只需要根据hash函数找位置，然后将新元素加入链表，速度很快；但缺点是，因为key不是有序的，所以哈希索引做区间查询的速度是很慢的；你可以设想下，如果你现在要找身份证号在\[ID\_card\_X, ID\_card\_Y\]这个区间的所有用户，就必须全部扫描一遍了；

所以，**哈希表这种结构适用于只有等值查询的场景**（where key = N），比如Memcached及其他一些NoSQL引擎；

*  **有序数组**

有序数组在等值查询和范围查询场景中的性能就都非常优秀；还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：

![90af7d5346cf4a40a6aa6fd65fcf7436.png][]

这里假设数组按照身份证号递增的顺序保存的；这时候如果你要查ID\_card\_n2对应的名字，即查有序列表中的某个元素，用二分查找就可以快速得到，这个时间复杂度是O(log(N))；

同时很显然，这个索引结构支持范围查询；例如，你要查身份证号在\[ID\_card\_X, ID\_card\_Y\]区间的User，可以先用二分法找到ID\_card\_X（如果不存在ID\_card\_X，就找到大于ID\_card\_X的第一个User），然后向右遍历，直到查到第一个大于ID\_card\_Y的身份证号，退出循环；

**如果仅仅看查询效率，有序数组就是最好的数据结构了**；但是他的**缺点就出在新增和删除的效率上；**你往中间插入/删除一个记录就必须得挪动后面所有的记录，最坏以及平均复杂度都达到了线性阶O(n)，成本太高；

所以，有序数组索引只适用于静态存储引擎，比如你要保存的是前一年某个城市的所有人口信息，这类不会再修改的数据；

*  **二叉搜索树**

还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：

![31f13a732d9e41968acc7ea5bf23bd64.png][]

> 二叉搜索树的特点是：**父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值**；

这样如果你要查ID\_card\_n2的话，按照图中的搜索顺序就是按照UserA->UserC->UserF->User2这个路径得到；这个时间复杂度是O(log(N))；当然为了维持O(log(N))的查询复杂度，你就需要保持这棵树是平衡二叉树；为了做这个保证，更新的时间复杂度也是O(log(N))；

当然需要注意的是：在极端情况下，数据偏向树的某一侧时，二叉搜索树会变成链表，那么搜索的时间复杂度就会退化为O(n)；

树可以有二叉，也可以有多叉；多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增；二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树；其原因是，**要尽量减少磁盘IO的访问次数**，因为每访问一层，理论上就会多一次磁盘IO，所以要尽量减少数高，从而就要增加N叉树的N的值；

以InnoDB的一个整数字段索引为例，这个N差不多是1200；这棵树高是4的时候，就可以存1200的3次方个值，这已经17亿了；想象一下，一个10亿多行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘；实际上，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了；

#### N叉树的N的值如何确定？ ####

**通过key值和页的大小来确定；**N叉树中非叶子节点存放的是索引信息，索引包含Key和Point指针；Point指针固定为6个字节，一个整数（bigint）字段索引的长度为 8个字节，那么单个索引就是6+8=14个字节；如果B+树中页大小为16Kb，那么一个页就可以存储**16 X 1024** ***÷ 14** ≈ **1170***个索引，此时N就等于1170；

我们通过改变Key的大小，就可以改变N的值；同样，页越大，一页存放的索引就越多，N就越大；

#### **B树与B+树** ####

![ef6a613a9c984e30a0a0026387cacfc2.png][]

![15e3aa504b5949c5998c98bb9caf89aa.png][]

*  B树简单地说就是多叉树，每个叶子会存储数据，和指向下一个节点的指针；
 *  B+树是B树的改进，简单地说是：只有叶子节点才存数据，非叶子节点是存储的指针；所有叶子节点构成一个有序链表；

关于B+树、B树相关的对比可参考：[彻底搞懂MySQL为什么要使用B+树索引][MySQL_B]  
相关代码可以参考：[Java手写AVL树（非常详细）][Java_AVL]

#### InnoDB 的索引模型 ####

N叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了；不管是哈希还是有序数组，或者N叉树，它们都是不断迭代、不断优化的产物或者解决方案；数据库技术发展到今天，跳表、LSM树等数据结构也被用于引擎设计中；由于InnoDB存储引擎在MySQL数据库中使用最为广泛，所以下面就以InnoDB为例，分析一下其中的索引模型；

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表；每一个索引在InnoDB里面对应一棵B+树；

假设，我们有一个主键列为ID的表，表中有字段k，并且在k上有索引；这个表的建表语句是：

mysql> create table T(
    id int primary key, 
    k int not null, 
    name varchar(16),
    index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵索引树的示例示意图如下：

![fae4cc3414a14f5aaa3c01afa00a8574.png][]

#### 主键索引与非主键索引 ####

>  *  根据叶子节点的内容，索引类型分为主键索引和非主键索引；
>  *  主键索引的叶子节点存的是整行数据；在InnoDB里，主键索引也被称为聚簇索引（clustered index）；
>  *  非主键索引的叶子节点内容是主键的值；在InnoDB里，非主键索引也被称为二级索引（secondary index）；

#### **基于主键索引和普通索引的查询有什么区别？** ####

如果语句是select \* from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树；  
如果语句是select \* from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次；**这个过程称为回表**；

也就是说，基于非主键索引的查询需要多扫描一棵索引树；

#### 索引维护&页分裂/页合并 ####

> B+树的叶子节点是有序的，在插入新值的时候需要做必要的维护；

以上面这个图为例，如果插入新的行ID值为700，则只需要在R5的记录后面插入一个新记录；如果新插入的ID值为400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置；而更糟的情况是，如果R5所在的**数据页已经满了**，根据B+树的算法，这时候**需要申请一个新的数据页，然后挪动部分数据过去**；这个过程称为**页分裂**；

在这种情况下，性能自然会受影响；**除了性能外，页分裂操作还影响数据页的利用率**；原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%；当

然有分裂就有合并；当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并；合并的过程，可以认为是分裂过程的逆过程；

#### 为什么建议建表语句里一定要有自增主键？ ####

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的：NOT NULL PRIMARY KEY AUTO\_INCREMENT；插入新记录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值；

**也就是说，自增主键的插入数据模式，刚好符合追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂**；

而有业务逻辑的字段做主键，**则往往不容易保证有序插入**，这样写数据成本相对较高；

除了考虑性能外，我们还可以从存储空间的角度来看；

由于每个非主键索引的叶子节点上都是主键的值；如果用业务字段如身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用整型做主键，则只要4个字节，如果是长整型（bigint）则是8个字节；**显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小**；

所以，从性能和存储空间方面考量，自增主键往往是更合理的选择；即满足：

*  **自增的特性保证了插入数据不会引起页分裂，保证了性能；**
 *  **作为每个二级索引的叶子节点，整形的主键索引类型占用空间相对小，从而保证二级索引数占用空间小；**

**有没有什么场景适合用业务字段直接做主键的呢？**还是有的；比如，有些业务的场景需求是这样的：

1.  只有一个索引；
2.  该索引必须是唯一索引；

这就是典型的KV场景；由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题；这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树；

#### 重建索引 ####

在实际的工作中，我们经常会delete数据，我们都知道，delete操作不会立即回收空间，反而频繁的delete操作会产生大量的磁盘碎片，这时候可能会影响到执行计划等，所以我们就需要整理磁盘碎片，通过就会用到上述几种方式的操作；

当一张表的索引较多时，索引文件占用磁盘空间较大，有时就需要重建索引；在官方文档中提供如下的三种方案：

>  *  Dump and Reload Method，整个数据库迁移，先dump出来再重建表（这个一般只适合离线的业务来做）；
>  *  ALTER TABLE Method，例如ALTER TABLE t1 ENGINE=InnoDB 其实等价于REBUILD表（REBUILD表就是重建表的意思），所以索引也等价于重新创建了；
>  *  REPAIR TABLE Method，用于修复被破坏的表，不过innodb存储引擎不支持；

此外，**OPTIMIZE TABLE**也可以对索引进行重建，其过程几乎不影响表的其他并发操作，推荐使用；

如果准备删除并重建索引，需要注意：

如果删除，新建主键索引，会同时去修改普通索引对应的主键索引，性能消耗比较大；  
删除重建普通索引貌似影响不大，不过要注意在业务低谷期操作，避免影响业务；

参考：

[MySQL如何进行索引重建操作？][MySQL]

[MySQL索引重建?如何操作？ - 墨天轮][MySQL_ -]

### 05 | 深入浅出索引（下） ###

#### 使用索引时，一条查询语句的执行流程 ####

下面是这个表的初始化语句：

mysql> create table T (
    ID int primary key,
    k int NOT NULL DEFAULT 0, 
    s varchar(16) NOT NULL DEFAULT '',
    index k(k))
    engine=InnoDB;
    
    insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

思考在下面这个表T中，如果执行 select \* from T where k between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？

![9cef6f727e0045d4bb505350cf2b7f48.png][]

现在，我们一起来看看这条SQL查询语句的执行流程：

> 1.  在k索引树上找到k=3的记录，取得ID=300；
> 2.  再到ID索引树查到ID=300对应的R3；
> 3.  在k索引树取下一个值k=5，取得ID=500；
> 4.  再回到ID索引树查到ID=500对应的R4；
> 5.  在k索引树取下一个值k=6，不满足条件，循环结束；

在这个过程中，**回到主键索引树搜索的过程，我们称为****回表**；可以看到，这个查询过程读了k索引树的3条记录（步骤1、3和5），回表了两次（步骤2和4）；

在这个例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表；那么，有没有可能经过索引优化，避免回表过程呢？

#### 覆盖索引 ####

覆盖索引如果执行的语句是select **ID** from T where k between 3 and 5，这时只需要查ID的值，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表；也就是说，在这个查询里面，**索引k已经“覆盖了”我们的查询需求，我们称为覆盖索引**；

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段；

当然，为了冗余字段支持覆盖索引，该联合索引会占用更多的存储空间，并且索引字段的维护总是有代价的，因此在建立冗余索引来支持覆盖索引时就需要权衡考虑了；

> 注意：对于二级索引，**会默认和主键做联合索引；**

#### 最左前缀原则 ####

如果为每一种查询都设计一个索引，索引是不是太多了，这时就要考虑建立"联合索引"，让它尽量覆盖更多的高频查询场景；

B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录；为了直观地说明这个概念，我们用（name，age）这个联合索引来分析；

![0713d46998f3401b9bfa1bb3517b1729.png][]

> 如图，**索引项是按照索引定义里面出现的字段顺序排序的**；

当需求是查到所有名字是“张三”的人时，可以快速定位到ID4，然后向后遍历得到所有需要的结果；如果你要查的是所有名字第一个字是“张”的人，你的SQL语句的条件是"where name like‘张%’"；这时，**你也能够用上这个索引**，查找到第一个符合条件的记录是ID3，然后向后遍历，直到不满足条件为止；

> **最左匹配原则**：在通过联合索引检索数据时，从索引中最左边的列开始，一直向右匹配，如果遇到范围查询(>、<、between、like等)，就**停止**后边的索引字段匹配；

可以看到，只要满足最左前缀，就可以利用索引来加速检索；这个最左前缀可以是：

>  *  联合索引的最左N个字段；
>  *  也可以是字符串索引的最左M个字符；

#### 如何安排索引内的字段顺序？ ####

这里我们的评估标准是，索引的复用能力；因为可以支持最左前缀，所以当已经有了(a,b)这个联合索引后，一般就不需要单独在a上建立索引了；因此，**第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的**；

如果既有联合查询，又有基于a、b各自的查询呢？查询条件里面只有b的语句，是无法使用(a,b)这个联合索引的，这时候你不得不维护另外一个索引，也就是说你需要同时维护(a,b)、(b)这两个索引；

这时候，我们要考虑的**原则就是索引数占用的空间了**；比如上面这个市民表的情况，name字段是比age字段大的，那就创建一个（name,age）的联合索引和一个 (age) 的单字段索引；

#### 索引下推 Index Condition Pushdown (ICP) ####

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

mysql> select * from tuser where name like'张%'and age = 10 and ismale = 1;

根据最左前缀索引规则，所以这个语句在搜索索引树的时候，因为对第一个name字段用到了模糊查询，因此只能先用“张”，找到第一个满足条件的记录ID3；尽管没能用上联合索引中的所有字段，但总比全表扫描要好；

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

**在MySQL5.6之前，不支持索引下推优化（index condition push down)**，只能从ID3开始一个个回表；到主键索引上找出数据行，再对比字段值；

**而MySQL5.6引入的索引下推优化**，可以在索引遍历过程中，**对索引中包含的字段先做判断**，如此处的age字段，直接过滤掉不满足条件的记录，**减少回表次数**；图3和图4，是这两个过程的执行流程图；

> **索引下推是把本应该在 server 层进行筛选的条件，下推到存储引擎层来进行筛选判断，这样能有效减少回表；**

下面分别是有无索引下推优化下的执行流程图：

![5f4d90d3e7014512ae762e5e410ac8db.png][]

不用索引下推的执行过程：

> 第一步：存储引擎利层用索引找出name以'张'开头的数据行：张三、张三、张六、张三这四条索引数据；  
> 第二步：再根据这四条索引数据中的 id 值，逐一进行回表扫描，从聚簇索引中找到相应的行数据，将找到的行数据返回给 server 层；  
> 第三步：在server层根据age = 10和ismale = 1这2个条件进行筛选，最终只留下ID4、ID5的用户的数据信息；

![816bfcbdccfa4fa381fdf50a2e486ddf.png][]

使用索引下推的执行过程：

> 第一步：存储引擎利层用索引找出name以'张'开头的数据行：张三、张三、张六、张三这四条索引数据；  
> 第二步：根据age = 10这个条件，对4条索引数据进行判断筛选，最终只留下ID4、ID5的索引信息；（注意：这一步不是直接进行回表操作，而是根据age = 10这个条件，对四条索引数据进行判断筛选）  
> 第三步：将符合条件的索引对应的 id 进行回表扫描，根据ismale = 1这个条件进行筛选，最终将找到的行数据返回给 server 层；

**索引下推 小结**：

索引下推 ICP 针对的是在“仅能利用最左前缀索的场景”下（而不是能利用全部联合索引），对不在最左前缀索引中的其他联合索引字段加以利用——在遍历索引时，就用这些其他字段进行过滤(where条件里的匹配)；过滤会减少遍历索引查出的主键条数，从而减少回表次数，提示整体性能；

如果查询利用到了索引下推ICP技术，在Explain输出的Extra字段中会有“Using index condition”；即代表本次查询会利用到索引，且会利用到索引下推；

下篇文章：[《MySQL实战45讲》——学习笔记06-07 “全局锁、表锁、行锁“][MySQL_45_06-07]

本文学习资料：

[04 | 深入浅出索引（上）-极客时间][04 _ _-]

[05 | 深入浅出索引（下）-极客时间][05 _ _-]

[e1353eb462d64050afbb9f1a7f62fcd3.png]: https://img-blog.csdnimg.cn/e1353eb462d64050afbb9f1a7f62fcd3.png
[90af7d5346cf4a40a6aa6fd65fcf7436.png]: https://img-blog.csdnimg.cn/90af7d5346cf4a40a6aa6fd65fcf7436.png
[31f13a732d9e41968acc7ea5bf23bd64.png]: https://img-blog.csdnimg.cn/31f13a732d9e41968acc7ea5bf23bd64.png
[ef6a613a9c984e30a0a0026387cacfc2.png]: https://img-blog.csdnimg.cn/ef6a613a9c984e30a0a0026387cacfc2.png
[15e3aa504b5949c5998c98bb9caf89aa.png]: https://img-blog.csdnimg.cn/15e3aa504b5949c5998c98bb9caf89aa.png
[MySQL_B]: https://blog.csdn.net/weixin_35871519/article/details/113303881
[Java_AVL]: https://blog.csdn.net/fengxiandada/article/details/124046346
[fae4cc3414a14f5aaa3c01afa00a8574.png]: https://img-blog.csdnimg.cn/fae4cc3414a14f5aaa3c01afa00a8574.png
[MySQL]: https://blog.51cto.com/u_15338523/3586768
[MySQL_ -]: https://www.modb.pro/db/162001
[9cef6f727e0045d4bb505350cf2b7f48.png]: https://img-blog.csdnimg.cn/9cef6f727e0045d4bb505350cf2b7f48.png
[0713d46998f3401b9bfa1bb3517b1729.png]: https://img-blog.csdnimg.cn/0713d46998f3401b9bfa1bb3517b1729.png
[5f4d90d3e7014512ae762e5e410ac8db.png]: https://img-blog.csdnimg.cn/5f4d90d3e7014512ae762e5e410ac8db.png
[816bfcbdccfa4fa381fdf50a2e486ddf.png]: https://img-blog.csdnimg.cn/816bfcbdccfa4fa381fdf50a2e486ddf.png
[MySQL_45_06-07]: https://blog.csdn.net/minghao0508/article/details/126691008
[04 _ _-]: https://time.geekbang.org/column/article/69236
[05 _ _-]: https://time.geekbang.org/column/article/69636