Innodb的B+树索引(1)

mysql> CREATE TABLE test(
    ->     id INT,
    ->     age INT,
    ->     name CHAR(1),
    ->     PRIMARY KEY(id)
    -> ) ;
Query OK, 0 rows affected (0.03 sec)

insert into test values (1,2,'a');
insert into test values (2,3,'bb');
insert into test values (3,4,'ccc');
insert into test values (4,5,'dddd');

在之前3月17号和4月9号的文章中，我们讲过innodb的数据页结构，如果对下面的内容有什么不理解的话，还请在文章分类中翻看之前的文章，防止大家忘记，这里我把图再贴过来：

如果将中间的数据记录部分写的再详细一点，就是下面这个样子：

数据页中的数据记录之间通过偏移量来进行连接，如下：

也就是说，数据页中的数据记录，通过一个链表的形式连接起来，查找下一条记录的依据就是本条记录中的偏移量的值，也就是next_record的值。

下面我们再说说索引的概念，大家都知道，索引类似于一个字典的目录，索引的创建是为了查询高效，或者说直观的概念就是在某个列上创建索引，那么这个列上的查询速度就会变快，但是索引也不是越多越好，索引的维护需要一定的成本。

那么在有索引的时候，MySQL是怎么利用索引的呢？

PART

1 单个数据页查询原理

要想知道索引的查询原理，还得从数据页之间的关联说起，截止目前，我们已经知道，在一个数据页中，数据记录之间是通过偏移量连接起来的一个链表，我们设想这样一个情况，如果一个查询SQL命中了某一个数据页，例如当我们执行一个

select * from test where id=6

的SQL时（其中id为主键），那么在这个数据页上过滤记录的时候，我们就要从第1个数据记录开始，按照链表的方式遍历这个数据页，一直到遍历到id=6的数据，我们就得到了我们想要的数据记录，还好这个值比较小，id只是6而已，考虑下面的情况：

这种情况下，我们的数据页中有60w条记录，当然这个数字是我杜撰的，可能没有这么大，如果我们查找id=143533的记录，那么需要遍历的记录数就非常多了，这肯定是我们不想看到的。为了解决这个问题，Innodb将一个数据页中的记录进行分组，分成若干个组，每个组的记录数在1~8个之间。然后将每个分组中的最后一个记录的偏移量记录下来，这里需要引入一个叫做"槽"的概念（也称之为"slot"），这个"槽"就是来保存最后一个记录的偏移量的。那么"槽"的位置在哪儿？看上图，它的位置其实是在倒数第二部分的Page Dictionary部分，也就是File Tailer的上方。为了描述方便，我们这个给出一个示意图：

这样，有了槽的概念，我们在一个数据页中查找一条记录的时候，就可以直接从槽开始查，因为一个分组内根据主键是排序的，我们使用二分法在槽中进行查找，假设我们要查找id=6的记录，记录的主键id=6值大于4而小于8，那么我们就定位到这条记录在槽8所对应的的分组，由于槽所对应的记录是该分组中最大的，而槽本身是用来保存偏移量的，那么我们可以从槽为4的记录开始遍历，这样，我们最多只需要遍历4条记录，就可以找到我们想要的结果。对于id=143533的记录也是一样的，首先我们在槽中做一个二分查找，然后再去遍历其中的某条记录，这样就大大简化了我们的查找过程。

PART

02 跨数据页查询原理

我们已经知道，在单个数据页中，是通过槽的二分法定位+分组记录遍历来得到一条记录的，那么如果我们要查询一个范围内的记录，而这些记录又不在同一个数据页上面，这个时候应该怎么办呢？我们怎么知道当前数据页的下一个数据页位置？答案是双向链表。

在MySQL中，数据页之间的关联是通过双向链表来关联的，这个双向链表的指针就在数据页的File Header中，除此之外，File Header中还包含当前数据页的页号，画成示意图就是：

也就是说，截止目前，我们的认知是如果我们查找某一条记录，如果在当前记录页中没有找到，那么MySQL将会顺着这个双向数据页链表一直找，直到找到这条记录为止。

但是，这样的查找也是存在问题的，如果一个表中的记录数很多比如1000w条数据，而一个数据页中的记录很少，假设只有500条，那么这得找到什么时候去呢？就像我们在数据页的单链表中查找某条记录一样。

遍历是不可能遍历的，这辈子都不会遍历的。在这里，Innodb做了一个很巧妙的处理，利用上级目录项来定位到底应该选择哪一个数据页，而不是按照双向链表查找。这里还是给出示意图，由于篇幅有限，这里将单个数据页进行简化，简化成下面的样子：

也就是只包含File Header里面的当前页号和数据记录之间的链表，其他部分舍弃掉。

这样，多个数据页之间的链接示意图就会变成：

到这里，我们知道了数据页之间是通过双向链表链接的，如果我们需要在多个数据页之间进行查询，这个时候就要用到前文提到的上级目录项，这个目录项包含两个重要信息，分别是每个数据页的最小数据记录值、数据页的号码。画成示意图就是：

在这种情况下，当我们需要查找id=6的记录时，会先在上层的目录项中查找到对应的id列的值范围，因为6大于4而小于7，所以我们判断出来我们想要的记录在数据页15上面，此时我们定位到数据页15上，利用槽的二分法+分组记录定位的方法，找到我们想要的记录，这样就方便多了。

需要注意的是，上级目录项中的内容随着表中记录数的变多，它也会相应的增长，而Innodb对于这个目录项，也是将它封装成数据页的形式来保存的，这样我们的示意图就变成了：

随着表的记录数越来越多，对于上层目录项来说，它也会越来越多，很明显，遍历上层目录项的代价也会越来越高，这种情况下，最好的方式是对上层的目录项在创建更高级别的目录项，类似这样：

到这里，其实已经能够看出来一个雏形了，这就是一棵B+数，最下面一层的称之为叶子节点，上面的称之为非叶子节点，非叶子节点是对叶子节点的一个"索引"，引导你到真实的数据记录上面去。上面这棵树，便是我们所说的表的B+树索引。

我们可以看到，叶子节点上包含了该条数据记录的所有字段数据，我们称这种索引为聚集索引。在我们的建表语句中，我们使用id列作为主键，那么这棵树，就是以id列为索引键的聚集索引。

PART

03 索引的原理

当我们拥有了聚集索引，当我们再去查询id=14536的数据的时候，就会从聚集索引的根节点出发，一层一层的去判断，先判断id值，在确定下一层需要查找的数据页，一直到叶子节点一层，再根据槽的二分查找+分组记录遍历的方法，最终查找到目标记录的速度也就非常快了，否则，用全表的顺序遍历，肯定性能很差。

看到这里，可能有的同学会担心这棵树的会越来越高，最后查询的速度也会减慢，我们现在试想这样一组数据，假设目录项每一层的数据页可以保存1000条目录项记录，如果我们这棵树的高度是4，那么一共可以保存的记录数就是：

1000*1000*1000*1000=1000000000000=10000亿条数据

这样的记录数，可以满足绝大部分的业务场景了。