B+树：mysql索引原理

2022-12-06  本文已影响0人  PENG先森_晓宇

提前阅读

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+树定义：

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

3.页的相关认知

  1. 看了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;
行记录的格式简化如下：

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

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

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

迭代一

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

  1. 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
图片
  1. 给所有的页建立一个目录项
图片

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

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

迭代二

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

图片

现在以查找主键为 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+树， 图形描述如下：

图片

索引结构总结

聚簇索引

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

图片

特点：

非聚簇索引

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

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


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

联合索引

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

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

索引优点和缺点

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

优点

  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，这就是页分裂现象，如下

上一篇 下一篇

猜你喜欢

热点阅读