20200415——索引融会贯通 真正的索引的形式 B+树 回表

因为主键只有一个，那么Mysql中的InnoDB中的聚集索引只有一个。

聚集索引

下面是一个以B+树形式组织的拼音索引，在B+树中，每一个节点里都有N个按顺序排列的值，且每个值的中间和节点的头尾都有指向下一级节点的指针。在查找过程中，按顺序从头到尾遍历一个节点中的值，当发现要找的目标值恰好在一个指针的前一个值之前、后一个值之后时，就通过这个指针进入下一级节点。当最后到达叶子节点，也就是最下层的节点时，就能够找到自己希望查找的数据记录了。

如同学习到的B+树一一昂，这个树非叶子节点是不存数据的，只有在叶子节点中，他才会存放数据。

在上图中如果希望找到险字，那么我们首先通过拼音首字母在根节点上按顺序查找到了X和Y之间的指针，然后通过这个指针进入了第二级节点···, xia, xian, xiang, ···。之后在该节点上找到了xian和xiang之间的指针，这样就定位到了第519页开始的一个目标数据块，其中就包含了我们想要找到的险字。

非聚集索引

下面是一个模拟部首索引的组织形式。我们由根节点逐级往下查询，但是在最后的叶子节点上并没有找到我们想找的数据，那么在使用这个索引时我们是如何得到最终的结果的呢？回忆之前字典中“检字表”的内容，我们可以看到，在每个字边上都有一个页码，这就相当于下面这一个索引中叶子节点上险字与院字中间的指针，这个指针会告诉我们真正的数据在什么地方。

下图中，我们把非聚集索引（部首索引）和聚集索引（拼音索引）合在一起就能看出非聚集索引最后到底如何查找到实际数据了。非聚集索引叶子节点上的指针会直接指向聚集索引的叶子节点，因为根据聚集索引的定义，所有数据都是按聚集索引组织存储的，所以所有实际数据都保存在聚集索引的叶子节点中。而从非聚集索引的叶子节点链接到聚集索引的叶子节点查询实际数据的过程就叫做——回表。

全覆盖索引

如果一个索引覆盖所有需要查询的字段的值，我们就称之为“覆盖索引”。我们知道在InnoDB存储引擎中，如果不是主键索引，叶子节点存储的是主键和列值。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢。而覆盖索引就是把要查询出的列和索引是对应的，不做回表操作。

举例：创建一个索引（username，age）

在查询数据的时候执行sql

 select username,age from user where username='Java' and age = 22;

要查询出的列和索引是对应的，不要做回表操作。

那么如果我们只是想要验证险字的偏旁是否是双耳旁“阝”呢？这种情况下，我们只要在部首索引中阝下游的叶子节点中找到了险字就足够了。这种在索引中就获取到了SQL语句中需要的所有字段，所以不需要再回表查询的情况中，这个索引就被称为这个SQL语句的全覆盖索引。

在实际的数据库中，非聚集索引的叶子节点上保存的“指针”就是聚集索引中所有字段的值，要获取一条实际数据，就需要通过这几个聚集索引字段的值重新在聚集索引上执行一遍查询操作。如果数据量不多，这个开销是非常小的；但如果非聚集索引的查询结果中包含了大量数据，那么就会导致回表的开销非常大，甚至超过不走索引的成本。所以全覆盖索引可以节约回表的开销这一点在一些回表开销很大的情况下就非常重要了。

范围查询条件

上图是一个联合索引idx_eg(col_a, col_b)的结构，如果我们希望查询一条满足条件col_a = 64 and col_b = 128的记录，那么我们可以一路确定地往下找到唯一的下级节点最终找到实际数据。这种情况下，索引上的col_a和col_b两个字段都能被使用。

但是如果我们将查询条件改为范围查询col_a > 63 and col_b = 128，那么我们就会需要查找所有符合条件col_a > 63的下级节点指针，最后不得不遍历非常多的节点及其子节点。这样的话对于索引来说就得不偿失了，所以在这种情况下，数据库会选择直接遍历所有满足条件col_a > 63的记录，而不再使用索引上剩下的col_b字段。数据库会从第一条满足col_a > 63的记录开始，横向遍历之后的所有记录，从里面排除掉所有不满足col_b = 128的记录。