B+树：mysql索引原理

提前阅读

https://time.geekbang.org/column/article/77830
https://www.cnblogs.com/xingxia/p/mysql_btree.html

参考

https://mp.weixin.qq.com/s/JIAlh5aBAX4P-8Cm5YBPmQ

总结

1.B+树定义：

• b+树也是一个M叉平衡搜索树,m是由mysql中page大小/索引大小所得
• b+树的非叶子节点不存数据，只存储索引
• b+树的叶子节点存储数据，且是一个有序的双链表，使用双链表有倆点作用
  • 当删除节点时需要知道前置节点
  • 使用双链表可以用于asc和desc排序

2.mysql中有聚簇索引和非聚簇索引，聚簇索引的数据结构符合上面的定义，而非聚簇索引的数据结构的叶子节点其实存储的是主键索引，而非数据。

3.页的相关认知

• 不管是磁盘还是操作系统，读取数据都是按页来读取的。

• 读取一页数据就是一次io操作，读取2页数据就是俩次io操作，而b+树中每个节点存储的就是一页的数据，而一页的中存储多少条数据，也就是m叉树，是mysql提前就算好的。

• m越大，也就意味着树的高度越低，高度越低就意味着读取io次数越少，读取io次数越少也就意味查找效率更高，所以提高mysql中页的大小也是优化索引查询的一种策略。

4. 看了https://time.geekbang.org/column/article/77830这篇文章要知道页分裂时是怎么平衡的？其实本质和23树平衡非常相似，如果你知道为什么23树永远是一个非常平衡的🌲的话，页分裂的平衡过程也就知道了。看下面的文章解释就会知道什么情况下出现页分裂了。

上面说到构建B+树索引时会提前算好该树是几叉树，那么具体是怎么计算的呢？我们举一个int类型字段为索引的例子，看下文：

• 定义一个非叶子节点且它的子节点也为非叶子节点的数据结构如下：

/**
* 这是B+树非叶子节点的定义。
* 
* m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = (m-1)*4+m*8
*/
public class BPlusTreeNode {
    public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
    public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子节点指针
}

keywords是一个int数组，存放的是int的索引值，举个例子，如果是一个m叉树，那么该数组存储的就是m-1个元素，比如keywords=[3, 5, 8, 10]，则4个键值将数据分为5个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)。

children是一个BPlusTreeNode类型的数组，存储的是该节点的子节点，如果是该节点是一个m叉树，则该节点的子节点应该存储的是m个节点数据。

既然我们想让其一个节点占用一页的大小，那么其公示为PAGE_SIZE = (m-1)*4+m*8，继而可以反推出m的值，其值就是该节点的m叉树。

解释一下这个公式的由来，keywords是一个整形数组，每个元素占用4个字节，且长度为m-1,所以占用大小为(m-1) * 4。

而children是一个引用数组，在java或者c语言中的引用地址在32位系统中占用的是4个字节，在64位系统中的占用的是8个字节。所以children数组占用的大小为 m x8

• 定义一个叶子节点的数据结构如下：

/**
* 这是B+树中叶子节点的定义。
*
* B+树中的叶子节点跟内部节点是不一样的,
* 叶子节点存储的是值，而非区间。
* 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。
*
* k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = k*4+k*8+8+8
*/
public class BPlusTreeLeafNode {
public static int k = 3;
public int[] keywords = new int[k]; // 数据的键值
public long[] dataAddress = new long[k]; // 数据地址

public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}

可以发现该节点占用大小为k*4+k*8+8+8,那么想让该节点占用一个页的话，只需要通过公式PAGE_SIZE = k*4+k*8+8+8,即可算出叶子节点应该存储k个节点数据了。

• 定义一个非叶子节点且它的子节点也为叶子节点的数据结构如下：

/**
* 这是B+树非叶子节点且子节点为叶子节点的定义。
* 
* m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = (m-1)*4+m*8
*/
public class BPlusTreeLastNode {
    public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
    public BPlusTreeLeafNode[] children = new BPlusTreeLeafNode[m];//保存子节点指针
}

可以发现该结构和BPlusTreeNode结构的唯一区别在于：children数组的类型不一致，但是计算公式是一致的PAGE_SIZE = (m-1)*4+m*8，也就是说在一个B+tree树中的所有非叶子节点的字节点数量是一致的。

但是发现叶子节点和非叶子节点的k值有可能是不一样的。 也就是说有非叶子节点存储的节点个数和叶子节点存储的节点个数是不相同的。

正文

你现在拼命转动大脑，开始去思考如何设计出这样的一个索引结构。你就在脑子里想，索引设计中需要解决哪些问题，以及要达成什么样的目标。

1. 我要怎么样才能在索引目录（数据结构）中快速找到具体的某条数据记录呢？那么这个数据结构需要有顺序规律，我按照这个规律就可以定位到具体的某条数据。
2. MySQL中的数据中的记录如何能够快速找到呢？是不是可以将记录进行排序，然后根据 二分法 快速找到对应的数据记录。
3. MySQL中架构老大一开始定义数据是按照数据页存放的，每个数据页默认是16kb, 每次满了，就会重新有新的一页。我的索引目录数据应该也是放到页中，而且索引的数据尽量少些，这样每页可以放更多的目录信息。
4. 我怎么样才能查询效率最高呢？其实每次慢都是慢在磁盘IO上，我再后面设计中一定要减少磁盘IO的访问，越少访问磁盘IO越好。
5. 磁盘中的空间还是不连续的啊，那我还得有个指针去连接下一条记录的位置。

带着这些问题和思考，你开始设计啦。

索引设计迭代

你想着我就拿一个例子具象化的思考设计索引。下面是一个新建的表：

CREATE TABLE demo(
  c1 INT,
  c2 INT,
  c3 CHAR(1),
  PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

行记录的格式简化如下：

我们只在示意图里展示记录的这几个部分：

• record_type：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 暂时还没用过，下面讲。
• next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。
• 各个列的值：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。
• 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

把一些记录放到页里的示意图就是： 图片

注意：一页可以存放16kb的数据，并不是图上的3条数据，这里只是一个示例。

迭代一

我们为什么要遍历所有的数据页或者记录？因为各个页中的记录并没有规律，不知道这条数据出现在哪个数据页中。那么如何快速定位要查找的数据在哪个数据页中呢？我们需要建立一定的规律，如下：

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

图片

• 页中的数据根据主键按顺序排序
• 不同页中的数据，下一页数据大于上一页数据
• 新分配的数据页编号可能并不是连续的。它们只是通过维护者上一个页和下一个页的编号而建立了 链表 关系

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

图片

• key表示目录中最小的主键值。
• page_on表示对应的页码。

查找主键值为 20 的记录，具体查找过程分两步：

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

迭代二

迭代一中的目录项是怎么存储的呢？我们是不是也可以用行记录格式存储到数据页中呢。答案是肯定的，我们通过行记录格式中的record_type等于1表示是目录记录，如下图所示：

图片

• 目录项记录的 record_type 值是1，而 普通用户记录的 record_type 值是0。
• 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列 ，另外还有InnoDB自己添加的隐藏列。

现在以查找主键为 20 的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

1. 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为 12 < 20 < 209 ，所以定位到对应的记录所在的页就是页9。
2. 再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。

迭代三

随着数据量变多，势必一个目录项存放不下，因为一页只有16kb大小，就会分裂出多页，如下图所示：

图片

那么现在查找主键值为 20 的记录，流程如下：

1. 我们现在的存储目录项记录的页有两个，即页30和页32 ，又因为页30表示的目录项的主键值的 范围是 [1, 320) ，页32表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在页30中。
2. 通过目录项记录页确定用户记录真实所在的页。
3. 在真实存储用户记录的页中定位到具体的记录。

迭代四

如果我们表中的数据非常多则会产生很多存储目录项记录的页，如果直接这么查，也是很慢，我们是不是可以针对目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，如下图所示：

图片

那么现在查找主键值为 20 的记录，流程如下：

1. 生成了一个存储更高级目录项的页33，这个页中的两条记录分别代表页30和页32, 主键20的记录在 [1, 320) 之间，则到页30中查找更详细的目录项记录。
2. 在页30中通过二分法查找主键为20记录的用户记录页码。
3. 在真实存储用户记录的页中定位到具体的记录。

迭代小结

以上这个数据结构就是我们索引最终的数据结构，B+树， 图形描述如下：

图片

• 所有的叶子节点存放全量的用户记录信息，包含所有的字段。
• 所有的目录节点只存放索引字段、主键以及对应的页码信息，要求信息越少越好，因为一页最多16kb，只有目录信息越少，每页存放的信息越多，树的层级就越小，树的层级越小，那么和磁盘的IO就越少，查询就会越快。一般来说，B+树4层，就可以存放上亿数据了。

索引结构总结

聚簇索引

我们按照前面的迭代推演出了基于主键的索引结构，是一颗B+树，我们把这种索引叫做聚簇索引。

图片

特点：

• 聚簇索引中的叶子节点存放了用户记录的全部数据，它就是innoDB中数据存放的格式，即数据即聚簇索引，聚簇索引即数据，这也是聚簇索引名字的由来吧，数据和索引聚集在一起。
• InnoDB要求表必须有主键。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐 含字段作为主键，这个字段长度为6个字节，类型为长整型，这样始终就会有一个聚簇索引。

非聚簇索引

既然有了聚簇索引，那么肯定有非聚簇索引，非聚簇索引也叫二级索引或者辅助索引。

它是在什么场景出现的呢？比如我们想以别的列作为搜索条件，总不能是从头到尾沿着链表依次遍历记录一遍，肯定要慢死了。这时候就需要建立非聚簇索引，那它的索引结构和聚簇索引有什么区别呢？

• 索引目录的内容由2部分组成，索引列的值+页码，通过索引列的值唯一确定新插入的列是在哪个页中，也可以唯一确定从那个页中查询。
• 索引的叶子节点存放内容为索引列的值+主键值。

那可能你有疑问了，只有主键值，我要查记录的其他信息怎么办呢？我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根 据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程称为 回表 。也就 是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树！回表的过程会耗时，为什么不直接存放所有的数据记录呢？如果把完整的用户记录放到叶子结点是可以不用回表。但是太占地方了，相当于每建立一课B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

联合索引

联合索引是一种特殊的非聚簇索引，那么它的数据结构又是怎么样的呢？

比方说我们想让B+树按照c2和c3列的大小进行排序，为c2和c3建立的索引的示意图如下： 图片

• 每条目录项都有c2、c3、页号这4个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序
• B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

索引优点和缺点

我们在了解了索引的数据结构以后，就更加明白索引的优缺点了。

优点

1. 提高数据查询的效率，降低数据库的IO成本。
2. 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
3. 在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低了CPU的消耗。

缺点

1. 创建索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间也会增加。
2. 索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间
3. 降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
4. B+索引中的数据都是有序的，比如插入一条主键较小的数据，势必导致其他数据进行移动，页码发生调整，这种现象也叫做页分裂，这也是为什么推荐主键要求自增。

页分裂

B+数中不管是非叶子节点还是叶子节点中的数据都是有序的，且每个节点其实都是一页的数据,而每页中的又有m个节点，m个节点的值是有序的，且页之间也是有序的。

聚簇索引页分裂

上面讲了，主键建议使用自增主键，这样可以避免页分裂，为什么这样说呢？我们知道主键自增的情况下可以避免页分裂，因为数据排序都是从左到右，从小到大排序的，自增的数据自然会出现在最右侧（二叉搜索树的右节点肯定比父节点大）。

页分裂不止发生在叶子节点，在存储索引的非叶子节点也存在页分裂。

非聚簇索引页分裂

我们大多数说的建议主键使用自增主键，可以避免页分裂，其实不管是聚簇索引还是非聚簇索引，都是B+树数据结构，也就是说不管是聚簇索引还是非聚簇索引，页中的数据都是有序的，也就是非聚簇索引也存在页分裂。

而且非聚簇索引不管什么情况下都存在页分裂，为什么这么说呢？非聚簇索引有nomal和unique俩种类型，这俩种类型都不是自增型的，所以都会出现页分裂的情况，以下图为例：

比如有一个c2列的nomal索引，且每页最多存储4条数据，现在数据如下

此时插入一条数据如下

insert demo(c1,c2,c3) values(10,7,21)

为了保证数据的有序性，页4中需要将c2为8的数据，移到下一页也就是页7，这就是页分裂现象，如下