聚簇索引和非聚簇索引

聚簇索引与非聚簇索引

1. 聚簇索引(主键索引)

InnoDB会自动为主键id创建一棵名为主键索引（又叫做聚簇索引）的B+树，这个B+树的最重要的特点就是叶子节点包含了完整的用户记录，大概长这个样子。

主键索引的B+树的每一个节点内的记录都是按照主键值由小到大的顺序，采用单向链表的方式进行连接的。

2. 非聚簇索引(非主键索引、二级索引)

InnoDB存储引擎会根据搜索条件在该二级索引的叶子节点中找到name为蝉沐风的记录，但是二级索引中只记录了name、phone和主键id字段（谁让我们用的是SELECT *呢），因此InnoDB需要拿着主键id去主键索引中查找这一条完整的记录，这个过程叫做回表。
想一下，如果二级索引的叶子节点上有我们想要的所有数据，是不是就不需要回表了呢？是的，这就是覆盖索引。

3. 什么是回表

我们可以通过二级索引找到B+树中的叶子结点，但是二级索引的叶子节点的内容并不全，只有索引列的值和主键值。我们需要拿着主键值再去聚簇索引（主键索引）的叶子节点中去拿到完整的用户记录，这个过程叫做回表。

回表的代价

我们根据name字段查找二级索引的叶子节点的代价还是比较小的，原因有二：

叶子节点所在的页通过双向链表进行关联，遍历的速度比较快；
MySQL会尽量让同一个索引的叶子节点的数据页在磁盘空间中相邻，尽力避免随机IO。

但是二级索引叶子节点中的主键id的排布就没有任何规律了，毕竟name索引是对name字段进行排序的。进行回表的时候，极有可能出现主键id所在的记录在聚簇索引叶子节点中反复横跳的情况（正如上图中回表的3条线表示的那样），也就是随机IO。如果目标数据页恰好在内存中的话效果倒也不会太差，但如果不在内存中，还要从磁盘中加载一个数据页的内容（16KB）到内存中，这个速度可就太慢了。
是不是说完了回表的代价之后，我会给出一种更高效的搜索方式？不是，回表已经是一种比较高效的搜索方式了，我们需要做的就是尽量地减少回表操作带来的损耗，总结起来就是两点：

能不回表就不回；
必须回表就减少回表的次数。

4. 索引覆盖、索引下推

4.1 索引覆盖

想一下，如果非聚簇索引的叶子节点上有你想要的所有数据，是不是就不需要回表了呢？比如我为name和phone字段创建了一个联合索引，如下图：

如果我们恰好只想搜索name、phone以及主键字段，
SELECT id, name, phone FROM user_innodb WHERE name = “蝉沐风”; 复制代码
可以直接从叶子节点获取所有数据，根本不需要回表操作。
我们把索引中已经包含了所有需要读取的列数据的查询方式称为覆盖索引（或索引覆盖）。

4.2 索引下推

4.2.1 概念

还是拿name和phone的联合索引为例，我们要查询所有name为「蝉沐风」，并且手机尾号为6606的记录，查询SQL如下：
SELECT * FROM user_innodb WHERE name = “蝉沐风” AND phone LIKE “%6606”; 复制代码
由于联合索引的叶子节点的记录是先按照name字段排序，name字段相同的情况下再按照phone字段排序，因此把%加在phone字段前面的时候，是无法利用索引的顺序性来进行快速比较的，也就是说这条查询语句中只有name字段可以使用索引进行快速比较和过滤。正常情况下查询过程是这个样子的：

InnoDB使用联合索引查出所有name为蝉沐风的二级索引数据，得到3个主键值：3485，78921，423476；
拿到主键索引进行回表，到聚簇索引中拿到这三条完整的用户记录；
InnoDB把这3条完整的用户记录返回给MySQL的Server层，在Server层过滤出尾号为6606的用户。

如下面两幅图所示，第一幅图表示InnoDB通过3次回表拿到3条完整的用户记录，交给Server层；第二幅图表示Server层经过phone LIKE “%6606”条件的过滤之后找到符合搜索条件的记录，返给客户端。

值得我们关注的是，索引的使用是在存储引擎中进行的，而数据记录的比较是在Server层中进行的。现在我们把上述搜索考虑地极端一点，假如数据表中10万条记录都符合name=’蝉沐风’的条件，而只有1条符合phone LIKE “%6606”条件，这就意味着，InnoDB需要将99999条无效的记录传输给Server层让其自己筛选，更严重的是，这99999条数据都是通过回表搜索出来的啊！关于回表的代价你已经知道了。
现在引入索引下推。准确来说，应该叫做索引条件下推（Index Condition Pushdown，ICP），就是过滤的动作由下层的存储引擎层通过使用索引来完成，而不需要上推到Server层进行处理。ICP是在MySQL5.6之后完善的功能。
再回顾一下，我们第一步已经通过name = “蝉沐风”在联合索引的叶子节点中找到了符合条件的3条记录，而且phone字段也恰好在联合索引的叶子节点的记录中。这个时候可以直接在联合索引的叶子节点中进行遍历，筛选出尾号为6606的记录，找到主键值为78921的记录，最后只需要进行1次回表操作即可找到符合全部条件的1条记录，返回给Server层。
很明显，使用ICP的方式能有效减少回表的次数。
另外，ICP是默认开启的，对于二级索引，只要能把条件甩给下面的存储引擎，存储引擎就会进行过滤，不需要我们干预。