Mysql底层原理四：B+树索引

B+树索引（索引的原理）

1.前言

前边我们详细唠叨了InnoDB数据⻚的7个组成部分，知道了各个数据⻚可以组成⼀个双向链表，⽽每个数据⻚中的记录会按照主键值从⼩到⼤的顺序组成⼀个单向链表，每个数据⻚都会为存储在它⾥边⼉的记录⽣成⼀个⻚⽬录，在通过主键查找某条记录的时候可以在⻚⽬录中使⽤⼆分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录（如果你对这段话有⼀丁点⼉疑惑，那么接下来的部分不适合你，返回去看⼀下数据⻚结构吧）。⻚和记录的关系示意图如下：

2.没有索引的查找

2.1 在一个页中查找

以主键为搜索条件
以其他列为搜索条件
对⾮主键列的查找的过程可就不这么幸运了，因为在数据⻚中并没有对⾮主键列建⽴所谓的⻚⽬录，所以我们⽆法通过⼆分法快速定位相应的槽。这种情况下只能从最⼩记录开始依次遍历单链表中的每条记录，然后对⽐每条记录是不是符合搜索条件。很显然，这种查找的效率是⾮常低的。

2.2 在很多个页中查找

在很多页的时候，我们应该是先定位到对应的页，然后到页中根据槽来查找。但是在没有索引的情况下，由于我们并不能快速定位到记录所在的页，所以只能从第一个页沿着链表遍历所有的页，是不是超级超级蠢。

3.一个简单的索引方案

问题：为什么我们要遍历所有的数据页拿？

因为各个页之间没有规律，我们并不知道怎么去匹配记录，所以不得不遍历所有的数据页。如果我们想快速定位到需要查找的记录该怎么办，其实参照记录目录的方法，我们是不是也可以建立一个有序的的目录🙏，建立这个目录必须完成以下这些事：

下一个页的记录主键值必须大于上一个页记录的主键值
页分裂（一个页放不下的时候，分成两个页）时，依旧要保证上面说的关系。

1）准备工作

建表：

mysql>	CREATE	TABLE	index_demo(->    	c1	INT,->    	c2	INT,->    	c3	CHAR(1),->    	PRIMARY	KEY(c1)->	)	ROW_FORMAT	=	Compact;
Query	OK,	0	rows	affected	(0.03	sec)

插入数据：

mysql>	INSERT	INTO	index_demo	VALUES(1,	4,	'u'),	(3,	9,	'd'),	(5,	3,	'y');
Query	OK,	3	rows	affected	(0.01	sec)
Records:	3 	Duplicates:	0 	Warnings:	0

这时候的页如图所示：

2）插入数据测试

再插入一条记录：

mysql>	INSERT	INTO	index_demo	VALUES(4,	4,	'a');
Query	OK,	1	row	affected	(0.00	sec)

因为页10只能放3个记录，所以我们不能不再分配一个页:

问题：为什么页号不是连续的？

新分配的数据页编号可能并不是连续的，也就是我们使用的页空间上并不是连续的。它们只是通过维护上下页来建立链表关系。另外，⻚10中⽤户记录最⼤的主键值是5，⽽⻚28中有⼀条记录的主键值是4，因为5 > 4，所以这就不符合下⼀个数据⻚中⽤户记录的主键值必须⼤于上⼀个⻚中⽤户记录的主键值的要求，所以在插⼊主键值为4的记录的时候需要伴随着⼀次记录移动，也就是把主键值为5的记录移动到⻚28中，然后再把主键值为4的记录插⼊到⻚10中，这个过程的示意图如下：

3) 给页建目录

以页28为例，它对应目录项2，这个目录项包含主键值，页号。比方说我们想查找主键值为20的记录，具体步骤粪两步：

先从⽬录项中根据⼆分法快速确定出主键值为20的记录在⽬录项3中（因为 12 < 20 < 209），它对应的⻚是⻚9。
再根据前边说的在⻚中查找记录的⽅式去⻚9中定位具体的记录。

记住，这个目录有个别名，就是索引，哈哈

4. InnoDB的索引方案

4.1 上述的索引方案有什么问题？

当表中数据不断增多的时候，目录项非常耗费空间，这对于记录数比较多的表不太现实
我们时常会对记录做增删，假设我们把页28中的记录全部删除了，页28也就没有必要存在，同时目录项2也没有存在的必要了。

设计InnoDB的大叔们灵光乍现，发现这些目录项其实和数据页长的差不多，只不过目录项存储的列值时主键和页号，所以他们复用了数据页的结构来存储目录项，为了区分，利用头信息的record_type属性。它的各个取值代表意思如下：

0：普通记录
1：目录项
2：最小记录
3：最大记录

4.2 最终实现的样子

从图中可以看出，我们新分配了一个编号为30的页用来专门存储目录项记录。这里再次强调一遍 目录项记录和普通的 用户记录的不同点：

目录项记录的record_type值是1，而普通用户记录的record_type值是0。
目录项记录只有主键值和页的编号两个列，而普通的用户记录是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。
还记得我们之前在唠叨记录头信息的时候说过一个 min_rec_mask的属性么，只有在存储目录项的页中的**主键值的目录项记录的min_rec_mask值为1，**其他都是0

假设我们按照某个主键20去查找记录，大致步骤分以下几步：

先看页的目录，也就是30的页通过二分法（这里指的是槽）找到对应的目录项记录，因为12<20<209，所以定位到页9。
再到页9中，根据二分法快速定位到对应的用户记录。

问题：虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的空间存储小多了，但是一个页也就16kb，能存放的目录项记录也是有限的，那如果表中的记录数据太多，以至于一个数据页不足以存放所有的目录项记录，该怎么办？

4.3 当一个页目录不够的时候怎么办

当然是再准备一个目录页啦，～为了⼤家更好的理解新分配⼀个⽬录项记录⻚的过程，我们假设⼀个存储⽬录项记录的⻚最多只能存放4条⽬录项记录（请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插⼊⼀条主键值为320的⽤户记录的话，那就需要分配⼀个新的存储⽬录项记录的⻚喽：

从图中可以看出，我们插入一个主键值为320的时候需要两个数据页：

为存储该记录，新增页31
因为原先存储的目录项记录30已经满了，所以新生成一个目录项页32

假设我们还是要查找主键为20的记录，大致步骤分以下几步：

确定目录项记录页（先确定记录在哪个目录页内），我们现在的存储⽬录项记录的⻚有两个，即⻚30和⻚32，⼜因为⻚30表示的⽬录项的主键值的范围是[1, 320)，⻚32表示的⽬录项的主键值不⼩于320，所以主键值为20的记录对应的⽬录项记录在⻚30中。
确定记录所在页（确定真实记录在哪个页内），在一个存储目录项记录的页中通过主键值二分法定位的一条目录项记录
在数据页中查找主键为20的记录

4.4 当一层页目录越来越多时怎么办

问题：如果数据量特别大，目录页就会越来越多，查询性能就会低下，这时候怎么办？

如图，我们⽣成了⼀个存储更⾼级⽬录项的⻚33，这个⻚中的两条记录分别代表⻚30和⻚32，如果⽤户记录的主键值在[1, 320)之间，则到⻚30中查找更详细的⽬录项记录，如果主键值不⼩于320的话，就到⻚32中查找更详细的⽬录项记录。

如果画的更加好一点，最终的样子是这样的：

这玩意是不是长得特别像倒过来的数呀，上头是树根，下头是树叶，我们称之为 B+数。

无论是存放用户记录的数据页还是存放目录像记录的数据页，都放到这个B+数结构中了，所以我们都称之为节点。**从图中我们可以看出用户记录时存放到B+树最底层的节点上，我们称之为叶子节点。**其余用来存放目录项的节点称之为非叶子节点。

存储能力：

4.5 常说的聚簇索引是什么

我们上边介绍的B+树本身就是一个目录，或者说本身就是一个索引，它有两个特点：

使用记录主键值的大小进行记录和页的排序，这包括以下三个方面的含义：
- ⻚内的记录是按照主键的⼤⼩顺序排成⼀个单向链表。
- 各个存放⽤户记录的⻚也是根据⻚中⽤户记录的主键⼤⼩顺序排成⼀个双向链表。
- 存放⽬录项记录的⻚分为不同的层次，在同⼀层次中的⻚也是根据⻚中⽬录项记录的主键⼤⼩顺序排成⼀个双向链表。
B+树的叶子节点存储的是完整的用户记录（这个记录中存储了所有列的值）

我们把具有这两种特性B+树称之为聚簇索引。所有完整的⽤户记录都存放在这个聚簇索引的叶⼦节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使⽤INDEX 语句去创建（后边会介绍索引相关的语句），InnoDB存储引擎会⾃动的为我们创建聚簇索引。另外有趣的⼀点是，在InnoDB存储引擎中，聚簇索引就是数据的存储⽅式（所有的⽤户记录都存储在了叶⼦节点），也就是所谓的索引即数据，数据即索引。

4.6 二级索引

问题：上面所说的索引都是围绕主键建立的，当搜索条件是其他列怎么办？

我们可以多建⼏棵B+树，不同的B+树中的数据采⽤不同的排序规则。⽐⽅说我们⽤c2列的⼤⼩作为数据⻚、⻚中记录的排序规则，再建⼀棵B+树，效果如下图所示：

这个B+树与上面说的聚簇索引有几处不同：

页内使用记录c2列的大小顺序成一个单链表
各个存放⽤户记录的⻚也是根据⻚中记录的c2列列⼤⼩顺序排成⼀个双向链表。
存放⽬录项记录的⻚分为不同的层次，在同⼀层次中的⻚也是根据⻚中⽬录项记录的c2列⼤⼩顺序排成⼀个双向链表。
B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
目录像记录中也不再是主键+页号的搭配，而变成了c2列+页号的搭配。

假设我们现在想通过c2列为4的记录为例，查找过程如下：

根据最高层级的页44确定下一级的目录页42，因为（2<4<9）
根据页42可以找到真实数据所在的页
在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2<4<=4,所以可以确定用户记录存放到页34和页35
到真实页之后，再通过二分法槽找到具体的记录
最重要的一步二级索引的就是回表：根据主键再去聚簇索引中查找一遍完整的用户记录

问题：为什么用回表操作，不是将数据存储到叶子节点那？

如果把完整的⽤户记录放到叶⼦节点是可以不⽤回表，但是太占地⽅了呀～相当于每建⽴⼀棵B+树都需要把所有的⽤户记录再都拷⻉⼀遍，这就有点太浪费存储空间了。因为这种按照⾮主键列建⽴的B+树需要⼀次回表操作才可以定位到完整的⽤户记录，所以这种B+树也被称为⼆级索引（英⽂名secondary index），或者辅助索引。由于我们使⽤的是c2列的⼤⼩作为B+树的排序规则，所以我们也称这个B+树为为c2列建⽴的索引。

4.7 联合索引

我们也可以同时以多个列的大小作为排序规则，建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

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

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

如图所示，我们需要注意以下几点：

每个目录项记录都是由c2、c3和页号组成，各条记录先按照c2排序，再按照c3排序
叶子节点是由c2、c3和主键c1组成。

其实，本质也是个二级索引，只是无论目录项记录还是数据页记录多了个列而已。

5.InnoDB索引细节

5.1 索引的生成过程（比较重要）

每当为某个表创建一个B+树索引的时候，就会为这个索引创建一个根节点页面。最开始既没有目录页，也没有数据页。
随后向表中插入数据时，先把用户记录存储到根节点中。
继续向根节点插入数据后，此时根节点的数据会复制到一个新的页，比如页a,然后对这个页做页分裂，得到一个新页，比如页b。往后新插入的数据就会放到a或者b中，根节点就升级成了目录页

一个b+树索引的根节点自诞生之日后，就不会再移动。这样只要我们对某个表建⽴⼀个索引，那么它的根节点的⻚号便会被记录到某个地⽅，然后凡是InnoDB存储引擎需要⽤到这个索引的时候，都会从那个固定的地⽅取出根节点的⻚号，从⽽来访问这个索引。