• 页内是按照c2列的大小进行排序形成的一个单向链表。
• 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成的一个双向链表。
• 各个存放目录项的页根据页中记录的c2列的大小排成的双向链表。

所以如果我们现在想通过c2列的值查找某些记录的话就可以使用我们刚刚建好的这个B+树了，以查找c2列的值为4的记录为例，查找过程如下：

• 确定目录项记录页
  • 根据根页面，也就是页44，可以快速定位到目录项记录所在的页为页42（因为2 < 4 < 9）。
• 通过目录项记录页确定用户记录真实所在的页。
  • 在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。
• 在真实存储用户记录的页中定位到具体的记录。
  • 到页34和页35中定位到具体的记录。
• 但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

大家可能页看到了，当最后定位到对应记录的时候，得到的是一个主键，而得到主键后仍然需要到聚簇索引中再查一遍，这个过程也被称为回表 。也就是根据c2列的值查询一条完整的用户记录需要使用到2 棵 B+ 树！！！

可能您会想，为什么需要回表呢？直接查出来不行吗？

当然可以，但是您想想，一个表中，每当我们建立一个索引就需要把记录拷贝一份到B+树，是不是太浪费存储空间了。因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引 或者辅助索引 。

联合索引

我们有时候也会使用多个列做联合索引，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层：

• 先把各个记录和页按照c2列进行排序。
• 在记录的c2列相同的情况下，采用c3列进行排序

为c2和c3列建立的索引的示意图如下：

• 每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。
• B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

以 c2 和 c3 列的大小为排序规则建立的B+树称为联合索引，它的意思与分别为 c2 和 c3 列建立索引的表述是不同的，不同点如下：

• 建立联合索引只会建立如上图一样的 1 棵B+树。
• 为 c2 和 c3 列建立索引会分别以c2和c3列的大小为排序规则建立 2 棵B+树。

总结

• 对于InnoDB存储引擎来说，在单个页中查找某条记录分为两种情况：
  1. 以主键为搜索条件，可以使用Page Directory通过二分法快速定位相应的用户记录。
  2. 以其他列为搜索条件，需要按照记录组成的单链表依次遍历各条记录。
• 没有索引的情况下，不论是以主键还是其他列作为搜索条件，只能沿着页的双链表从左到右依次遍历各个页。
• InnoDB存储引擎的索引是一棵B+树，完整的用户记录都存储在B+树第0层的叶子节点，其他层次的节点都属于内节点，内节点里存储的是目录项记录。InnoDB的索引分为两大种：
  • 聚簇索引
    • 以主键值的大小为页和记录的排序规则，在叶子节点处存储的记录包含了表中所有的列(索引既数据)。
  • 二级索引
    • 以自定义的列的大小为页和记录的排序规则，在叶子节点处存储的记录内容是列 + 主键 ，所以每次查找的数据都会先得到主键，而得到主键后仍然需要到聚簇索引中再查一遍，这个过程也被称为回表 。也就是根据c2列的值查询一条完整的用户记录需要使用到2 棵 B+ 树！！！

最后

最后说一下，本文的参考文章： MySQL的索引 。

本文的很多内容也是来自这篇文章，本人只在文章中插入了有关自己对于文章的理解，如果说的不对，还望指教。

大家也可以去看一下原文。