【源码学习】InnoDB存储引擎中的索引方案B+树
前言
当我们提到InnoDB的索引方案B+树索引时，总会想B+树到底是什么样？以及组成B+树索引的其他结构到底是什么样？下面就揭开InnoDB中的B+树索引结构的面纱！本文依次从记录存储结构->数据页结构->B+树索引展开
B+树的组成及演进
记录存储结构
我们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。InnoDB存储引擎有4种不同类型的行格式，分别是Compact、Redundant、Dynamic和Compressed行格式，随着时间的推移，他们可能会设计出更多的行格式，但是不管怎么变，在原理上大体都是相同的，差异不在详细介绍。主要简单介绍下Compact行格式，如图：
从图中可以看出来，一条完整的记录其实可以被分为记录的额外信息和记录的真实数据两大部分。
变长字段长度列表
我们知道MySQL支持一些变长的数据类型，比如VARCHAR(M)，我们也可以把拥有这些数据类型的列称为变长字段，变长字段中存储多少字节的数据是不固定的，所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来，这样才不至于把MySQL服务器搞懵，所以这些变长字段占用的存储空间分为两部分：1.真实的数据内容，2.占用的字节数
在Compact行格式中，把所有变长字段的真实数据（非NULL的）占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表，各变长字段数据占用的字节数按照列的顺序逆序存放。
NULL值列表
简单来说就是把这些值为NULL的列统一管理起来，存储到NULL值列表中，这块区域采取二进制bit位
来存储，一行数据里有多少个字段允许null，那么这个区域就会以bit位的形式存放
记录头信息
注：重点关注下record_type和next_record
记录的真实数据
记录的真实数据除了我们自己定义的列的数据以外，MySQL会为每个记录默认的添加一些列（也称为隐藏列），具体的列如下：
数据页结构
页(Page)是InnoDB中磁盘和内存交互的基本单元，也是InnoDB管理存储空间的基本单元，默认是16KB，常见的页类型有8种,如数据页，undo页，系统页，事务数据页等,以下是页结构示意图。
首先看下记录在页中是如何存储的,记录在页中利用记录的next_record属性组成一个单向链表，如图：
现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表，那如果我们想根据主键值查找页中的某条记录该咋办呢？比如说这样的查询语句：
SQL
SELECT * FROM table WHERE c1 = 3;
最笨的办法：从Infimum记录（最小记录）开始，沿着链表一直往后找，总有一天会找到，但是即使页中存储的记录不是非常多，这样的遍历查询也是一种极差的查询体验，所以InnoDB的设计者从书的目录中找到灵感。
我们平常想从一本书中查找某个内容的时候，一般会先看目录，找到需要查找的内容对应的书的页码，然后到对应的页码查看内容。InnoDB的设计者为我们的记录也制作了一个类似的目录，他们的制作过程是这样的：
将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组，具体的分组规则不在详述。
每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方，这个地方就是所谓的Page Directory，也就是页目录。页面目录中的这些地址偏移量被称为槽（英文名：Slot），所以这个页面目录就是由槽组成的，如图：
现在看怎么从这个页目录中查找记录。因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用所谓的二分法来进行快速查找。5个槽的编号分别是：0、1、2、3、4，所以初始情况下最低的槽就是low=0，最高的槽就是high=4。比方说我们想找主键值为6的记录，过程是这样的：
计算中间槽的位置：(0+4)/2=2，所以查看槽2对应记录的主键值为8，又因为8 > 6，所以设置high=2，low保持不变。
重新计算中间槽的位置：(0+2)/2=1，所以查看槽1对应的主键值为4，又因为4 < 6，所以设置low=1，high保持不变。
因为high - low的值为1，所以确定主键值为6的记录在槽2对应的组中。此刻我们需要找到槽2中主键值最小的那条记录，然后沿着单向链表遍历槽2中的记录，直到找到主键值为6的那条记录即可。由于一个组中包含的记录条数只能是1~8条，所以遍历一个组中的记录的代价是很小的。
所以在一个数据页中查找指定主键值的记录的过程分为两步：
通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。
通过记录的next_record属性遍历该槽所在的组中的各个记录。
总结：
各个数据页组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录
B+树索引
大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
定位到记录所在的页。
从所在的页内中查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那结果可想而知。
为后续画图方便，定义一个简化了的行格式示意图
故把记录放到页中的简单示意图如下
如果继续往页10中插入记录，由于页10中已经存不下新的记录了，于是会新分配一个页来存储记录，如图
因为要保证“下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值”所以会有一个页分裂的过程，如图所示
由于数据页的编号可能并不是连续的，所以在向表中插入许多条记录后，可能是这样的效果：
因为这些16KB的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：
页的用户记录中最小的主键值，我们用key来表示。
页号，我们用page_no表示。
所以我们为上边几个页做好的目录就像这样子：
我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为20的记录，具体查找过程分两步：
先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 32），它对应的页是页9。
再根据前边说的在页中查找记录的方式去页9中定位具体的记录。
但是这个简易的索引方案，因为要在查找时使用二分法快速定位具体的目录项，所以所有目录项都必须在物理存储器上连续存储，但是这样做有个问题：
InnoDB是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。
于是，InnoDB的设计者们需要一种可以灵活管理所有目录项的方式。他们灵光乍现，忽然发现这些目录项其实长得跟我们的用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以他们复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录,就是前面在介绍记录存储结构时有提到的record_type,如图所示：
从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录，它们的主要区别是目录项记录的record_type值是1，而普通用户记录的record_type值是0，它们所使用的的页的类型都是同一个，页的组成结构也是一样的，都会为主键值生成Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。
虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，该咋办呢？当然是新分配一个页存储新的目录项记录，如图：
所以如果我们想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为20的记录为例：
确定目录项记录页
通过目录项记录页确定用户记录真实所在的页。
在真实存储用户记录的页中定位到具体的记录。
那么问题来了，在这个查询步骤的第1步中我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？其实也简单，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：
如果简化一下，那么我们可以用下边这个图来描述它：
这玩意儿就是我们常说的一种数据结构，它的名称是B+树，不论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到B+树这个数据结构中了，所以我们也称这些数据页为节点。从图中可以看出来，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中B+树最上边的那个节点也称为根节点。
我们前边介绍B+树索引的时候，为了大家理解上的方便，先把存储用户记录的叶子节点都画出来，然后接着画存储目录项记录的内节点，实际上B+树的形成过程是这样的：
每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录。
随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到页a或者页b中，而根节点便升级为存储目录项记录的页。
这个过程需要大家特别注意的是：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。
B+树和红黑树、B树的对比
红黑树亦或AVL树其本质上还是一个二叉树，但是此类树通过适当的方案达到自平衡避免了二叉树一边倒的可能性，解决了二叉树极端情况蜕化成链表问题，若二叉树蜕化成链表，每次查询都变成了全表扫描，就失去了加索引的意义；由于二叉树的特点，其树高不可避免的比B+树等多路搜索树要高很多，导致IO成本较高。
假设B+树中存储用户记录的页能存储100条用户记录，存储目录项记录的页能存储1000条目录项记录，那么一个3层的B+树能存储：10001000100 = 100000000 条记录，而平衡二叉树存储这么多记录至少要20层。
B树是一种多路自平衡的搜索树，它类似普通的平衡二叉树，不同的一点是B树允许每个节点有更多的子节点，它的特点如下：
所有键值分布在整颗树中（索引值和具体data都在每个节点里）
任何一个关键字出现且只出现在一个结点中
搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）
在关键字全集内做一次查找，性能逼近二分查找
传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等，这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了，原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中，一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右，速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间，这说明程序大部分时间会阻塞在磁盘 IO 上，那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘，而B树虽然也是多路搜索树，但是根据其特点可知其树更高，且不具有B+树区间查询、天然有序的特点，故B+树更适合做数据库索引。
总结
本文通过图示的方法，直观简要的介绍了InnDB存储引擎中B+树其核心构成部分，数据页、记录存储结构等组成要素，以及B+树形成的一个过程，基本可以清晰的了解到一个查询语句查询时是如何搜索目标数据的，最后简要介绍了为何MySQL选择B+树作为索引方案。