当前位置：首页 > news >正文

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

news 来源：原创 2024/4/29 3:53:31

04 | 深入浅出索引（上）

1. 什么是索引？

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

2. 索引的常见模型

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

哈希表

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

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

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

图中，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引擎；

有序数组

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

这里假设数组按照身份证号递增的顺序保存的；这时候如果你要查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)，成本太高；

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

二叉搜索树

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

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

这样如果你要查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+树

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

关于B+树、B树相关的对比可参考：彻底搞懂MySQL为什么要使用B+树索引
相关代码可以参考：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)，两棵索引树的示例示意图如下：

主键索引与非主键索引

根据叶子节点的内容，索引类型分为主键索引和非主键索引；
主键索引的叶子节点存的是整行数据；在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个字节；显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小；

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

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

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

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

这就是典型的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索引重建?如何操作？ - 墨天轮

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，需要执行几次树的搜索操作，会扫描多少行？

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

在k索引树上找到k=3的记录，取得ID=300；
再到ID索引树查到ID=300对应的R3；
在k索引树取下一个值k=5，取得ID=500；
再回到ID索引树查到ID=500对应的R4；
在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）这个联合索引来分析；

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

当需求是查到所有名字是“张三”的人时，可以快速定位到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 层进行筛选的条件，下推到存储引擎层来进行筛选判断，这样能有效减少回表；

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

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

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

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

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

索引下推小结：

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

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

本文学习资料：

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

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