3、B+树索引

c

3

30（页号）

9

a1列

0

90

1

页A

8

页B

2

m

记录2

a3列

l

首先我们想到的是一个比较笨一点的方法：1、找到数据所在的页2、从页中获取主键值所在的槽3、遍历这个槽的分组数据，得到结果由于数据页是一个双向链表组成的，所以我们可以遍历这个链表，从最小的数据页开始，依次去遍历，直到找到当前的数据页中包含了我们要查的这个主键值。确定了数据页之后，再找到这个数据页的Page Direction，使用二分法找到当前要查询记录所在的分组，最后在遍历这个分组就可以得到结果了。嗯……，这样做没毛病，完全可以把我们想要的数据找出来。但是上面已经说了，这个数据库里面有百万条数据，可能分出的数据页有几十万之多。如果我们要查询一条符合条件的数据，从第一个数据页开始一直往下遍历，如果数据靠前还好，但是数据如果排在非常后面那么检索的速度就会大幅降低。最极端的是可能遍历完所有的数据页之后没有一条匹配的结果，最终是花了最长的时间，没有任何结果。查询查了个寂寞~

76

12

37（页号）

30

a2列

上面说了B+树是可以提高Level的，也就是提高层级。一般情况下B+树不会超过4层。

记录4

像上面的这个方法在强大的InnoDB当中肯定是不予采纳的，否则MySQL也做不到如此强大。那么InnoDB究竟是怎么做的呢？相信大家都已经猜出来了，那就是每每在面试当中都要提上一嘴的索引！那么索引它到底是个啥东西呢？接着往下看

这里我们简化一下B+树，大概就是这样

g

22

d

r

我们在数据库中肯定不只是这么一点数据，设想一下如果存在有百万条数据，那么InnoDB会分好多好多的页。这时候我们如果需要查询一条数据，比如查询主键值=2356的数据。那么在InnoDB里面会怎么样去查呢？

5

记录1

6

记录3

17

a

最大记录

最小记录

被提取出来的一页中同样也存储着一些数据，但是数据的每个列却存的都是下层每个页的最小主键值和对应的页码，它们和我们的用户数据非常相似，那这两种记录到底是怎么区分呢？哈哈，这其实就关联到了前面记录头信息的record_type属性。其中有一个值一直都没有讲到，其实这个就用到了这个值。细心的小伙伴已经看出来了，在提取出来的页中的记录那个record_type属性已经变成了1。还记得1是什么意思吗？1表示当前B+树非叶子节点的记录唉？这里提到了B+树，那什么是B+树呢？哈哈，答案就是上图，这就是B+树。存储我们用户记录的各个页被称为叶子节点，在最上面的成为根节点，然后剩余的就是非叶子节点了。可是上面图中似乎并没有非叶子节点啊。显而易见，是的，没有。因为现如今的数据还不足与让整个B+树继续提高Level

InnoDB数据页的7个组成部分，各个数据页之间组成一个双向链表，而每个数据页中的记录都会按照主键值从小到大进行排序组成一个单向链表，在每个数据页中都会为记录生成一个页目录，然后再通过主键值在页目录中用二分法快速定位对应的槽，接着再遍历槽对应的分组中的记录就可以快速找到指定的记录了。

37

s

21

22（页号）

34

11

页C

89（页号）

这边提一嘴关于索引类型。聚簇索引：一级索引叶子节点存储的是本行记录，查到叶子节点也就查到了本条记录。索引即数据，数据即索引。是由InnoDB自己创建的二级索引：也就是一些我们自己建立的索引，同样也是由一个B+树组成，只不过它的叶子节点存储的只是本条记录的主键值，查到主键值之后再回到聚簇索引上找，这也就是我们常说的回表。这也就是说，                  每当我们自己创建一个索引都会增加一个B+树，需要做一些排序等维护工作。如果索引创建过多就会引起内存爆棚，同时增加维护成本。联合索引：其实也是一个二级索引，只不过是同时用了两个列及以上的索引。它的构造也会与二级索引一样，只不过排序的时候有个不同，它会先根据第一个索引排序，如果相等再用第二个以此类推。所以我               们常说使用索引特别是联合索引要符合最左匹配原则。在索引查询的过程中会从第一个索引开始比对，依次才能找到下面的索引数据，如果一开始就提供不了第一个索引数据，那么InnoBD只能全表扫描了覆盖索引：也是一个二级索引，只不过我们在查询的时候所需要查询出的列索引里面已经有了，就不需要回表在去查了。

检索数据其实无非就是去遍历然后判断，一个页逐个遍历非常消耗性能，那么我们是不是就要想办法尽量去减少遍历的次数呢？是的，InnoDB就是这样做的。那到底怎么样才能够减少遍历的次数呢？我们知道数据页是一个按照主键值从小到大排序的。那是不是我们就可以把主键给提出来，然后标识上这个主键对应的是哪一个页。当在检索的时候就可以拿这个主键值去判断当前的数据是不是在这个页里面。是不是非常像Page Direction。具体的图形呈现如下：

好，基本的结构都已经完成了，那么接下来正式开始介绍索引了。画了这么多图这个索引它究竟到底是个什么东东呢？其实，索引我们就可以理解为是一个目录，他非常类似于数据页中的页目录，只不过在这里它被称为了索引。

y

15

页A、页B、页C这些页在物理上是不相连的，但是逻辑上是相连的，也就是通过双向链表相关联！

next_record

record_type

现如今的数据在页里面是这个样子，最上面是File Header里面存储的页号。其下就是页里面存储的数据。当然数据不可能才这么少。我们假设每页最多存储三条数据。

File Header部分