Mysql索引篇：聚簇索引

type

status

date

slug

summary

1、概述

根据前面的知识我们已经知道，在一个数据页内，可以通过页目录进行二分查找快速查找数据行，但是 InnoDB 存储引擎不知道你要查找的记录所在的页号。我们需要有一种方式快速定位到你要的主键数据所在的数据页，而不是从第一页开始遍历。所以我们需要为所有的数据页建立一个可以快速查找的数据结构，这就引出了索引的物理数据结构。

索引的物理数据结构又可以分成聚簇索引和非聚簇索引（二级索引），它们区别就在于叶子节点存放的是什么数据：

聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点；

二级索引的叶子节点存放的是主键值，而不是实际数据。

2、聚簇索引

聚簇索引的特点表的数据都是存放在叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚簇索引，且由于数据在物理上只会保存一份，所以聚簇索引只能有一个。

InnoDB 在创建聚簇索引时，会根据不同的场景选择不同的列作为索引：

如果有主键，默认会使用主键作为聚簇索引的索引键；

如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键；

在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键；

例如下面就是一个聚簇索引的数据结构：

聚簇索引的两个特点：

按照主键的大小对用户记录和数据页进行排序，记录用单向链表连接，数据页使用双向链表连接；

B+树的叶子节点保存了用户的完整记录。

现在要查找主键ID为14的记录，需要经历这几个步骤：

就从页99中，快速检索到对应的目录项数据页124；

在页124中，快速检索到对应的数据页27；

在页27中，快速检索到主键为14的记录。

2.1 索引页和数据页

从上面我们可以看到非叶子结点（索引页）和叶子结点（数据页）用的其实复用了 InnoDB 中的页结构。

还记得MySQL的行格式吗？它决定了记录在磁盘里的存储格式。以COMPACT为例，存储格式如下图：

这里面的记录头信息有一个 record_type 字段，用来表示行记录的类型

0：普通用户记录

2：Infimum 记录（初始情况下，一个数据页中只有 Infimum 记录和 Supremum 这两条记录）

3：Supremum 记录

当值为 0 时，表示普通的用户记录，每一行用户记录存储实际的数据。

当值为 1 时，表示目录项记录，每一行用户记录存储子页的最小 id 和页地址。

现在把一个目录项页放到多个数据页之上，就变成下面这个结构

目录项记录 record_type 值为 1，普通用户记录的 record_type 值是 0

如此一来，目录页跟数据页一样，都可以为主键值生成 Page Directory（页目录），从而在根据主键值查找记录时，使用二分法来加快查询速度。

还是以查找主键值为 20 的记录为例，大致就可以分为 2 步走：

先目录项页（页30）通过二分法快速找到对应的目录项记录。因为 12<20<209，所以目标记录在页 9。

到页 9中继续根据二分法快速找到主键为 20 的用户记录。

2.2 聚簇索引可以存储多少数据

假设所有存放用户记录的叶子节点的数据页可以存放 100 条用户记录，所有存放目录项记录的非叶子节点的数据页可以存放 1000 条目录项记录，那么：

如果 B+ 树只有 1 层，也就是说只有 1 个用于存放用户记录的节点，那么只能存 100 条用户记录。

如果 B+ 树有 2 层，则最多存放 1000*100= 100000 条用户记录。

如果 B+ 树有 3 层，则最多存放 1000*1000*100= 100000000 条用户记录。

如果 B+ 树有 4 层，则最多存放 1000*1000*1000*100= 100000000000 条用户记录。

也就是说，如果有 4 层的话最多存 1000亿条记录，很显然表里不会有这么多数据。所以在一般情况下，我们用到的 B+树不超过 4 层。

基于此，通过主键值去查询某条记录，最多只需要进行 4 个页面内的查找（3个存储目录项的页，1个存储用户记录的页）。而在每个页面内有存在页目录 Page Directory，所以在页面内也可以通过二分法快速定位记录。

3、二级索引

一张表只能有一个聚簇索引，那为了实现非主键字段的快速搜索，就引出了二级索引（非聚簇索引/辅助索引），它也是利用了 B+ 树的数据结构，但是二级索引的叶子节点存放的是主键值，不是实际数据。

下面是对name单个列建立的二级索引

二级索引的特点：

叶子节点存放的不再是完整的用户记录，而是只记录name列和主键值；

数据页中存放的用户记录和目录项记录由原本的按照主键排序变为按照name列排序；

目录项记录除了存储索引列（name）和页号之外，同时还存储了主键值；

如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作「回表」，也就是说要查两个 B+ 树才能查到数据。不过，当查询的数据是主键值时，因为只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作「覆盖索引」，也就是只需要查一个 B+ 树就能找到数据。回表和覆盖索引只能在二级索引发生。

3.1 联合索引

假设我们为name列和phone列建立联合索引（注意字段顺序），自然也是创建一棵B+树，这棵B+树和之前又稍微有点不同：

叶子节点存放的是name列、phone列和主键值；

目录项记录除了存储索引列（name、phone）和页号之外，同时还存储了主键值；

数据页中存放的用户记录和目录项记录由原本的按照主键排序变为按照name列排序，如果name列相同，那就按照phone列排序；（如果phone列再一样呢？你现在明白为什么要存储主键值了吗？）

还是和二级索引一样，利用B+树快速定位到数据页，然后页内快速定位到记录，找到记录中的主键id，再回表，如果找到多条符合条件的记录，就多回几次表。

3.1.1 最左匹配原则

最左匹配原则：指的是联合索引中，优先走最左边列的索引。

模糊查询中必须要满足最左匹配原则。比如我们要查询姓张的用户，我们的条件查询可以为 "where name like ‘张%’"，但是不能是 where name like '%张%'或者是 where name like '%张'，因为索引可以用于查询条件字段为索引字段，根据字段值必须是最左若干个字符进行的模糊查询，也就是需要是 张% 这样的添加才可以使用。

Mysql 优化器的优化能力：对于上面这个 (name,phone) 两个联合索引字段，我们使用 where name = '张三' and phone = '2'索引可以生效的，当我们是颠倒了他们的顺序使用where phone = '1' and name = '王五'，索引同样也是可以生效的，在 Mysql 查询优化器会判断纠正这条sql语句该以什么样的顺序执行效率最高，最后才生成真正的执行计划，我们能尽量的利用到索引时的查询顺序效率最高，所以 Mysql 查询优化器会最终以这种顺序（where name = '张三' and phone = '2'）进行查询执行。

索引的复用能力：当已经有了 (name,phone) 这个联合索引后

查询条件里面只有 name 的语句，因为可以支持最左前缀，一般就不需要单独在 name 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

查询条件里面只有 password 的语句，是无法使用 (name,phone) 这个联合索引的，这时候你需要同时维护 (name,phone)、 (password) 这两个索引。

联合索引建议使用原则：

将区分度高的字段放在前面，区分度低的字段放后面。例如假设区分度由大到小为 b,a,c。那么我们就对 (b,a,c) 建立索引。在执行 sql 的时候，优化器会帮我们调整 where后 a,b,c 的顺序，让我们用上索引。

最左匹配原则遇到范围查询就停止匹配，所以建索引的时候把等值查询的字段放在前面，范围查询的字段放后面。

3.2 覆盖索引

覆盖索引（又称为索引覆盖）即从非主键索引中就能查到的记录，而不需要查询主键索引中的记录，避免了回表的产生减少了树的搜索次数，显著提升性能。

为了使用覆盖索引，一般需要创建一个包含所有需要返回的列的普通索引或者联合索引。

例如，下面的查询语句可以使用联合索引进行优化：

可以创建包含 (age, id, name) 三个列的联合索引，查询语句使用了 age 列作为过滤条件，同时需要返回 id 和 name 两个列的值。由于联合索引中包含了要返回的两个列，因此可以直接从索引中获取数据，避免了二次查找的开销。

3.3 索引下推（ICP）

上面我们说到满足最左前缀原则的时候，联合索引的最左匹配原则会一直向右匹配直到遇到范围查询(>、<、between、like) 就会停止匹配。例如表存在 (username,is_del) 联合索引，执行下面 SQL 语句。

在MySQL 5.6之前，只能从匹配的位置一个个回表到主键索引上查询出相应的全行数据，然后再对比字段值筛选出未删除的用户数据。整个过程如下：

存储引擎读取二级索引记录。

根据索引中的主键值，定位并读取完整的行记录（所谓的回表查询）。

存储引擎把记录交给Server层去检测该记录是否满足WHERE条件。

如果有多个主键值，重复2和3步骤，多次回表查询并判断记录是否满足WHERE条件。

下面图每一个虚线箭头表示回表一次。存储引擎根据通过联合索引找到 name like '张%' 的主键id（1、4），逐一进行回表扫描，去聚簇索引找到完整的行记录，Server 层再对数据根据 age=10 进行筛选。需要回表两次，而且把我们联合索引的另一个字段 age 浪费了。

MySQL 5.6 引入了索引下推（Index Condition Pushdown，简称 ICP）的优化技术，可以进一步提高覆盖索引的效率。索引下推指的是把 WHERE 子句中的一些条件下推到存储引擎层面进行过滤，减少要读取的行数。当查询语句使用覆盖索引时，MySQL 可以在索引中直接检测 WHERE 子句中的条件，而不必去加载表中的行，从而减少了 I/O 操作和 CPU 计算等开销。

对于上面这个 SQL，使用索引下推技术后，存储引擎根据 (name，age) 联合索引，找到 name like '张%'，由于联合索引中包含 age 列，所以存储引擎直接再联合索引里按照 age=10 过滤，按照过滤后的数据再一一进行回表扫描，只回表了一次。查看执行计划，看到 Extra 列里 Using index condition，这就是经典的索引下推。

Mysql 默认启用索引下推，我们也可以通过修改系统变量 optimizer_switch 的 index_condition_pushdown 标志来控制

索引下推使用条件：

只能用于 range、 ref、 eq_ref、ref_or_null 访问方法。

只能用于 InnoDB 和 MyISAM存储引擎及其分区表。

对于 InnoDB 的表，索引下推只能用于二级索引，因为在聚簇索引中最下方的叶子节点保存了整行数据，所以使用索引下推并不会起到减少查询全行数据的效果。

引用了子查询的条件不能下推；

引用了存储函数的条件不能下推，因为存储引擎无法调用存储函数。

索引下推一般可用于所求查询字段（select列）不是/不全是联合索引的字段，查询条件为多条件查询且查询条件子句（where/order by）字段全是联合索引。总之，覆盖索引和索引下推是 MySQL 查询优化中常用的技术，可以显著提高查询效率和降低数据库的负载。在使用时，需要根据具体的业务场景和查询需求进行选择和优化，以达到最佳的性能表现。

4、MyISAM的索引方案

不同的存储引擎存放数据的方式不一样，产生的文件数量和格式也不一样，InnoDB文件包含2个，MEMORY文件包含1个，MyISAM文件包含3个。我们接下来关注的就是MyISAM中的文件。

.MYD文件，D代表Data，是MyISAM的数据文件，存放用户记录，也就是我们插入的表数据；

.MYI文件，I代表Index，是MyISAM的索引文件。一个索引就会有一棵B+树，所有的B+树都保存在这个文件当中。

也就是说，不同于InnoDB的“索引即数据”的思想，MyISAM存储引擎中的索引和数据是分开存储的。

MyISAM中的B+树长啥样子呢？其实样子和InnoDB差不多，区别就是MyISAM的B+树的叶子节点存储的是用户记录对应的磁盘地址，所以从索引文件.MYI中找到对应的索引键（建立索引的列的值）后，会到.MYD中找到对应的用户记录。以主键为例我再再再画个图：