深耕MySQL - InnoDB的索引方案之B+树索引_mysql innodb b+树

1. 数据页

首先建立一张表：

create table index_demo(
	c1 int,
	c2 int,
	c3 char(1),
	primary key(c1)
) ROW_FORMAT=COMPACT;
1
2
3
4
5
6

记录放到页里面的示意图：

我们在根据根据某个搜索条件查找一条记录时，为什么要遍历所有的数据页呢？原因是各个页中的数据并没有规律，我们并不知道搜索条件会匹配哪些页中的记录，所以不得不依次遍历所有的数据页。如果想快速定位到需要查找的记录在哪些数据页中，该咋办？

还记得我们为了根据主键值快速定位一条记录在页中的位置而设置的页目录吗？

我们也可以为快速定位记录所在的数据页而建立一个别的目录，在建这个目录的过程必须完成两件事：

(1) 下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值；

(2) 给所有的页建立一个目录项;

2. 页分裂

如何理解下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值？

现假设每个数据页最多存放3条记录，向index_demo中插入3条记录：

insert into index_demo values(1,4,'u'),(3,9,'d'),(5,3,'y');
1

这些记录已经按照主键值的大小串联成了一个单向链表了：

index_demo表中的3条记录都插入到了编号为10的页中，此时再插入一条记录：

insert into index_demo values(4,4,'a')
1

因为页10最多只能存放3条记录，所以不得不分配一个新页：

为什么分配的新页的页号是28而不是11呢？

新分配的数据页编号可能并不是连续的，因为我们使用的这些页在磁盘上可能并不挨着，它们只是通过维护上一页和下一页的编号而建立了链表关系。

页10中用户记录最大的主键5，而页28中用户记录最大的主键是4，5>4并不符合“下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值”的要求，因此在插入主键为4的记录时需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，再把主键值为4的记录插入到页10中。

这个过程表明：对页中的记录进行增删改查操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程就是页分裂。

3. 目录项

给所有的页建立一个目录项：

由于数据页的编号可能并不是连续的，因此想index_demo表中插入许多条记录后，可能会形成如下的结果：

由于这些大小为16KB的页在磁盘上并不挨着，如果想从这么多页中根据主键值快速定位某些记录所在的页，就需要给他们编制一个目录，每个页对应一个目录项，每个目录项包括下面两个部分：

(1) 页的用户记录中最小的主键值，用key表示；

(2) 页号，用page_no表示；

以页28为例，它对应的目录项为2，这个目录项中包含着页号28以及该页中用户记录主键的最小值5，因此我们只需要将几个目录项在物理存储器上连续存储，比如放到数组中存储，就可以实现根据主键值快速查找某条记录的功能了。

比如，我们想要查找主键为20的记录，具体步骤为：

(1) 因为12<20<35，所以可以根据二分法（1,5,12,35）快速确定出主键为20的记录在目录项3中，它对应的页号为9；

(2) 然后再根据在页中查找记录的方式去页9中查找定位具体的记录即可；

这个目录就是索引。

4. InnoDB中的索引方案

为数据页制作目录项是一个简易的索引方案，是因为我们在根据主键值进行查找时，为了使用二分法快速定位具体的目录项，而假设多有目录项都可以在物理存储器上连续存储，但是这样做存在下面的问题：

InnoDB使用页作为管理存储空间的基本单位，也就是说最多只能保证16KB的连续存储空间。虽然一个目录项占用不了多大的存储空间，但是架不住表中的记录越来越多，此时就需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表来说是不现实的。

因此，InnoDB设计了一种可以灵活管理所有目录项的方式，即复用之前存储用户记录的数据页存储目录项记录。那么怎么区分一条记录时普通的用户记录还是目录项记录呢？那就是record_type属性：

0 - 普通的用户记录

1 - 目录项记录

2 - infimum记录

3 - supermum记录

因此，我们把上面使用到的目录项放到数据页中，就有了下面的形式：

目录项记录和用户记录用的是一样的数据页，页的组成结构也是一样的，都会为主键值生成Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查找速度。

现在以查找主键20的记录为例：

(1) 先到存储目录项记录的页30中，根据二分法快速定位到对应的目录项记录 ，因为12<20<35，因此定位到对应的用户记录所在的页就是页9；

(2) 再到存储用户的页9中，根据二分法快速定位到主键值为20的用户记录；

虽然说目录项记录中值存储主键值和页号，比用户记录需要的存储空间小多了，但是一个页只有16KB，能存储的目录项记录也是有限的，如果表中的数据太多了，以至于一个数据页无法存放所有的目录项，此时就需要添加目录项了。

假设一个存储目录项记录的页中最多只能存放4条目录项记录，此时我们想index_demo表中再插入一条主键值为90的用户记录，那就需要分配一个新的数据页来存储目录项记录了：

现在存储目录项记录的页不止一个，此时如果想根据主键值20查找一条用户记录，则大致需要3个步骤：

(1) 确定存储目录项记录的页；

现在存储目录项记录的页有页30和页32，页30表示的目录项记录主键值的范围是[1,90），页32表示的目录项记录主机主键值不小于90，所以主键为20的记录对应的目录项记录在页30中。

(2) 通过存储目录项记录的页确定用户记录真正所在的页；

(3) 在真正存储用户记录的页中定位到具体的记录；

那么问题又来了，我们需要定位目录项记录的页，但是这些页在存储空间上也不挨着，如果表中的数据非常多，就会产生很多存储目录项记录的页，那么怎么根据主键值快速定位一个存储目录项记录的页呢？那就是为这些存储目录项记录的页再生成一个更高级的目录：

这颗树就是我们所说的B+树，也是InnoDB使用的索引方案。

无论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到B+树这个数据结构中，将这些数据页称为B+树的节点。

用户记录都存放在B+树的叶子节点上，目录项记录都存放在非叶子节点上，一个B+树的节点其实可以分为很多层，InnoDB规定最下面的那层为第0层，之后层级依次往上加。

一个页中存放的记录数量是非常大的，假设所有存放用户记录的叶子节点所代表的数据页可以存放100条记录，所有存放目录项记录的非叶子节点所代表的数据页可以存放1000条记录，那么：

(1) 如果B+树只有1层，就是说只有1个用于存档用户记录的节点，那么最多可以存放100条用户记录；

(2) 如果B+树有2层，最多能存放1000x100=100000条用户记录；

(3) 如果B+树有3层，最多能存放1000x1000x100=100 000 000条用户记录；

(4) 如果B+树有4层，最多能存放1000x1000x1000x100=100 000 000 000条用户记录；

你的表中能存放100 000 000 000条用户记录吗？

一般情况下，我们用到的B+树都不会超过4层，这样在通过主键值去查找某条用户记录时，最多只需要进行4个数据页的查找，又因为数据页内存在Page Directory，因此可以在页面内通过二分查找快速定位用户记录。