从数据页和B+树的角度看索引失效原因

📚 全文字数 : 6k+

⏳ 阅读时长 : 8min 📢

关键词 : 数据页结构、索引的B+树结构、索引失效原理

场景再现，有多少朋友有过的？

面试官👴：我看你建立熟悉数据库索引，那索引失效有哪些场景？

我👦：巴拉巴拉，把从晚上背的6，7条失效场景一字不落的背出来了

我👦：心里想，这问题能难道我？

面试官👴：能具体一点吗，上一位面试者也是这么说的

我👦：额，心里想，我没背过这个知识点啊，芭比Q了

前言

文章开头的面试场景不是我编出来的，兄弟们，刚毕业一两年面试的我就出现过这种问题。仅仅问你失效场景，只要准备过面试的人都能答出来。但是再往下问问，就不知道怎么答了。

这篇文章将从InnoDB存储引擎的索引B+树和数据页的角度一起来看实际的索引失效问题，设计的内容比较多，关于【数据页】和【索引的知识结构】只是可以翻看我之前的文章有更详细的内容。

大纲

先看大纲，让自己知道今天要讲的内容。

什么是索引失效

我们知道创建索引的目的是为了提高查询速率，但并不是创建了索引就能让查询速率显著提高的。

稍不注意，你是在列上建了索引，可能你写的查询条件也是索引列，但最终执行计划没有走它的索引，从而走了全表扫描，这种建了索引而实际索引没用的情形就是索引失效。

从数据页看B+树

（1）在叶子节点一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表，便于范围查询。叶子节点的每一个Key指向一条记录。

（2）非叶子节点取的是叶子节点里面Key的最小值。这意味着所有非叶子节点的Key都是冗余的叶子节点。同一层的非叶子节点也互相串联，形成了一个双向链表

在了解索引和索引失效之前，我们应该对数据页，数据页中数据的存储方式，如何构建B+树的这些原理搞清楚！

这些对后续理解为啥使用B+树，B+树的特性会有很大的帮助，而不是为了应付才去死记硬背一些没什么营养的答案。

数据页结构

MySQL读取数据都是以【数据页】为单位读取的，而不是需要读取一条记录的时候就读记录本身，以数据页为读取单位的话，需要将其整体读取内存中，但是各个数据页之间是不连续的。

而数据页默认大小为16KB，意味着每次至少是将16KB的内容疏导内存中。

左侧的是组成数据页的7大部分，右侧是这几部分的简要说明。

不同数据页之间既然不是连续的，那怎么知道这个数据页的下个页在哪？

其实File Header中有两个指针，分别指向上一个数据页和下一个数据页，各数据页整体看起来就是双向链表。

这里也讲下两个比较重要的：行记录部分User Records是存储用户的数据记录，Infimum（最小记录） + Supremum（最大记录） 是两个虚拟的伪记录

数据页用户记录

数据页16KB大小的内容中肯定有不止一条用户记录，我们先来看单挑记录长什么样，我们之前的文章有分享InnoDB中Compact行记录格式，之前对行记录知识没了解的同学可以先传送过去看下：

我们看记录头信息的关键字段

delete_flag：删除标记 0未删除、1已删除

n_owned：同一页同一组内最大记录会记录组里的记录数量

record_type：0：表示普通记录，1：表示B+树非叶子节点记录 2：表示最小记录(Infimum) 3：表示最大记录(Supremum)

next_record：指向的是下一条记录的「记录头信息」和「真实数据」之间的位置

上面说的这几个标签很重要，这对我们站在数据页的角度看用户记录帮助很大！下图数据页用户记录中的各个方块位置分别对应这几个行记录头信息的字段。

从图中可以看出数据页中的记录按照顺序组成单链表，而且还对记录进行了分组，这里叫做页记录【槽】。

• 第一个分组中的记录只能有 1 条记录
• 最后一个分组中的记录条数范围只能在 1-8 条之间
• 剩下的分组中记录条数范围只能在 4-8 条之间
• 槽指向的是不同组的最后一个记录（组内最大记录）

这里做个小总结：页目录就是由多个槽组成的，槽相当于分组记录的索引，槽内有1-8条记录，而且都是按照主键进行顺序排列。

这也是典型的可以使用【二分法】快速定位要查询的记录在那个槽，进而进行遍历槽内的记录，避免了通过遍历整个数据页来查找记录。

看到这里：

现在我们应该形成了一个模型图是形成了一个有序的双向链表，而每页里面的数据记录，是按照指定的字段值，从小到大排序，形成了一个单向链表。

数据页构建B+树索引

为了更简洁的说明索引，对上面的页结构做做一个显示上的优化，底层的东西是没有任何变化的。

实际的数据会由非常多的页组成，而数据页形成有序双向链表的方式，会让链表看起来很长，那么MySQL又是怎么做来进行优化的呢？

1：多数据页的时候无法快速定位到页，既然此时形成的数据页链表也是有序的，InnoDB的设计者们，就把数据页的编号和主键最小值记录下来，然后形成一个称为索引页的数据页，我们这里把存储的记录称为目录项。

2：索引页的数据记录record_type = 1非叶子节点记录，比如这里是索引页存储的也编号和最小值记录，上面我们也讲了record_type分别代表的记录类型。

3：同样的索引页记录过多，存不下这些目录项，那么怎么办，那就再在索引页中在再归纳出一层索引页来咯！

好吧，我知道了，所以最形构建成了我们印象中的B+树结构。

图中我们存储了一些主键记录为【1-9】的记录，淡绿色方块是recordtype的类型值，这里记录了在什么类型的数据页值分别是多少，紫色方块next_record,绿色方块是主键记录和最大最小记录。

B+树查询过程

看到这里我们缕一缕B+树的查询逻辑，加深下对B+数索引结构的记忆，查询部分我们可以分为两部分去理解，一个是数据页之间，另一部分是数据页内部。

根据上图B+树结构，需求是查询主键为5的的记录。

• 从最上层的非叶子节点【页10】开始，查询的主键为5，而页10的主键在【1-6】，5小于6，因此通过二分法定位，到【页17】
• 在非叶子节点【页17】，继续使用上面的方式，因为主键值5大于4
• 继续到【页14】继续查找，到了【页14】时，已经到达页
• 到达页之后，就到了第二部分了
• 先根据页目录中的槽来进行二分法查找，确定在哪个槽
• 确定在哪个槽之后，遍历槽内记录，也就是分组记录，最后找到主键5的记录

可以看到，查找流程，先定位记录所在哪一个页，然后通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽号），最后在分组内进行遍历查找，查找结束。

看到这里我们已经知道B+树的数据页组成和内部数据记录了，如何一步步进行二分法查询的，接下来，我们继续看不同的索引下的B+树的样子！

索引的B+树结构

创建不同的索引实际对应的B+树也会有不同的形态，这里就从三种不同的索引类型来看B+树的结构，这里都是基于InnoDB存储引擎。

我们先建个简单的表来这几种结构进行说明

CREATE TABLE `test_index` (
  `id` INT NOT NULL AUTO_INCREMENT,
  `col1` VARCHAR(45) NULL,
  `col2` VARCHAR(45) NULL,
  `crate_time` DATETIME NULL,
  PRIMARY KEY (`id`)
)COMMENT = '';

聚簇索引

以聚簇索引构建B+树索引的叶子节点中，存储了表中所有的数据。

上一个章节关于B+树的结构图，其实就是聚簇索引结构，使用主键值的大小进行记录和页的排序，叶子节点存储的是完整的用户记录，这里就不再继续贴图了。

二级索引

二级索引（非聚集索引）构建的B+树索引的叶子节点不存储表中的数据，而是存储该列对应的主键。

我们以test_index表的col1列建立一个索引，col1是不是主键，以col1构建的B+树结构如下：

从图中我们可以看到和聚簇索引的区别：

• 叶子节点和非叶子节点都是使用col1列（非主键）的大小进行页记录排序，而聚簇索引使用的是主键
• 叶子节点存储的数据是col1和主键两个列
• 索引页的记录存储的是col1和页号

什么是索引覆盖和回表？

【索引覆盖】二级索引进行查找数据时，如果查询的数据能在二级索引找到，那么就是索引覆盖操作

【回表】查询的数据不在二级索引里，就需要先在二级索引找到主键值，需要去聚簇索引中获得数据行，这个过程就叫是回表

联合索引

同时为多个列建立索引称为联合索引，以这些列的大小为排序规则建立的B+树索引。

我们以test_index表的col1、col2列建立联合索引，col1和col2列大小进行排序，构建的B+树结构如下：

联合索引构建的B+树的特点也很明显：

• 叶子节点的数据记录是由col1、col2和主键组成
• 而索引页非叶子节点的记录则是由col1、col2和页号组成
• 节点中的col1和col2都是先按照col1进行排序，然后再按照col2排序

索引失效原理

如果对前面对于B+树和查询过程和对应的索引结构不清楚的话，建议多读两遍，理解B+树结构对我们理解为什么索引会失效很重要。

这里继续用test_index表来举两个例子，对为什么会失效有个更清楚的认识。

最左前缀查询原理

test_index表的col1和col2组成联合索引

执行查询：select * from test_index where col1='a' and col2= 'bb'

col1在B+树上是有序的，我们通过二分法查找可以定位到 col1 = 'a'的位置，在col1确定的情况下，col2是相对col1有序，同样能能利用二分法定位到 col2= 'bb'的位置，所以上面的查询语句中两个字段都可以利用上索引。

但是如果执行如下查询的话情况就不同了。

执行查询：
sql1：select * from test_index where col2= 'bb'
sql2：select * from test_index where col1 >'a' and col2 = 'bb'

• sql1中col2顺序的前提是col1也是顺序的，如果col1不能确定的话，那么无法利用二分法在无序的列上利用索引进行查询。
• sql2中col1因为有序的能利用二分法找到a，但是因为col2有序的前提是col1的值确定，但是 col1 > a ,col1的值可能是b、c、d等，所以col1可以利用到索引，而col2是用不到的。

这也就是为什么我需要遵循最左原则，这下明白了吧！

like模糊匹配查询

左右模糊匹配的时候，也就是 like %col2 或者 like %col2% 这两种方式都会造成索引失效，我们看具体原因：

B+树叶子结点记录是字符串时，按照组成字符串字母的顺序排序的，%号放左边，两个%%号，查询的结果如下：

• %号放左边时，匹配的是尾部的字母，而尾部字是母没有顺序的，因为字符串不能按顺序查询，索引索引会失效
• 两个%%号是因为只有首字母进行索引排序，其他字母却是无需的，因此用不上索引

当然索引失效的场景还有很多，比如：

• 对索引列使用函数，表达式计算
• 索引列进行了隐式转换
• where语句中使用or
• 等等

只要我们理解了索引树的特点、原理，那么就能理解为什么这些场景下索引会失效，就能从更好避免索引失效！

is nul、is not null问题

is null和is not null会导致索引失效吗?

这是个比较经典的问题，可能80%的同学会误解认为is null、is not null、!=这些判断条件会导致索引失效。

真实情况在MySQL官方文档中也有说明：

MySQL can perform the same optimization on col_name IS NULL that
it can use for col_name = constant_value. For example, MySQL can use 
indexes and ranges to search for NULL with IS NULL.

mysql的sql查询语句中使用is null、is not null、!=对索引并没有任何影响，
并不会因为where条件中使用了is null、is not null、!=这些判断条件导致索引失效而全表扫

导致索引失效而全表扫描的通常是因为一次查询中回表数量太多。

比如如果一条查询语句导致的回表范围超过全部记录的20%，则会出现索引失效的问题。而is null、is not null、!=这些判断条件经常会出现在这些回表范围很大的场景，然后被人误解为是这些判断条件导致的索引失效。

总结

MySQL的InnoDB存储引擎，是按数据页来读写的，数据页之间通过双向链表组织起来，数据页中的用户记录则是用单向链表的方式组织。

为了加快记录所在的数据页，InnoDB采用B+树做索引，并且每个节点都是数据页，但是非叶子节点的数据页我们称为目录项（索引页）。

在数据页内通过设计页目录来存储槽的方式来挺高查询效率，因为主键值有序，用户记录也可以通过二分查找法进行检索。

聚簇索引、二级索引、主键索引的B+树结构是不同的，熟悉他的结构对我们利用好索引帮助很大，对于理解【回表】和【索引覆盖】更得心应手！