B+树的生成过程怎么去看懂B+树

分手后的思念是犯贱 2023-10-03 21:26 24阅读 0赞

![format_png][]

## 前提 ##

看B+树 看不懂树结构什么意思 这一篇可以帮你理解树结构生成的过程

在说B+ 树之前 需要知道 一页的大小是多少

show global status like 'innodb\_page\_size'

![format_png 1][]

这个是看出 一页是 16384 也就是 16384/1024 = 16kb innodb中一页的大小默认是 16kb

## 正文 ##

创建表结构 指定引擎为 Innodb

CREATE TABLE tree(
    id int PRIMARY key auto_increment,
    t_name VARCHAR(20),
    t_code int 
    ) ENGINE=INNODB
    复制代码
    复制代码

查看一下当前表的索引情况

show index from tree

B树和B+树的显示都是BTREE 但是实际使用的B+树 但是B+树也是B树的升级版 称之为B树也是没有问题的

![format_png 2][]

创建数据 这里会有一个小知识点 如果看过上一篇文章的朋友可以明白是为什么

INSERT into tree VALUES(3,"变成派大星",3);
    INSERT into tree VALUES(1,"变成派大星",1);
    INSERT into tree VALUES(2,"变成派大星",2);
    INSERT into tree VALUES(4,"变成派大星",4);
    INSERT into tree VALUES(7,"变成派大星",7);
    INSERT into tree VALUES(5,"变成派大星",5);
    INSERT into tree VALUES(6,"变成派大星",6);
    INSERT into tree VALUES(8,"变成派大星",8);
    复制代码
    复制代码

![format_png 3][]

## 疑问 ##

为什么创建数据的时候数据是乱的但是在创建好数据 被拍好顺序了

## 基础知识 ##

我们在寻找答案之前 想明白一些基础知识

细心的朋友可以看出来 我们插入Id 时候数据是乱的 插入进去之后 数据就自动帮我通过Id 进行排序了 这是为什么呢？接着往下看

我们如果对于B+树有点了解的话就知道B+树是每页16KB 进行数据储存 在进行数据查询的时候也是一页一页的去查询

相当于下面的数据

首先每一页都有很多数据 就像 我们平常去写分页的时候我们返回给前端的数据也会有很多属性

![format_png 4][]

这个可能比较抽象 我是把他当成平常 分页查询的思想代入进去

我们可以把一页想成是一个对象

@Data
    public class page {
    
    List<UserRecords> data;
    
    ....省略其余属性
    }
    复制代码
    复制代码

我们先看一下 一页数据的图是什么样子 仅仅是进行逻辑思考画的图

这里的Data 就相当于 一页中的数据区域

![format_png 5][]

但是这里是有限制的 上面我们说到 一页的数据只能是16Kb 也就是 一个Page 里面的data只能16Kb 数据 当超过16Kb 就会新开一个对象相当于在进行创建树的时候增加了判断

Java代码思路模拟：

![format_png 6][]

当 Page 对象的大小已经达到16Kb 就算完成这一页 把这一页放到 磁盘中等待使用就行了 到时候进行查询数据的时候会直接返回这一页 里面包含这些数据

我们回到最初的问题 为什么我们在进行插入的时候明明Id 是乱的 等到插入到数据的时候 数据就变成有序的了 我们知道 同时这个数据是根据主键进行排序的 也就Innobd 的数据储存一定是要依赖主键的 有些人会想 我就是不创建主键 他还能排序吗？

## 疑问二 ##

我们在疑问一的基础上 产生出的疑问 不设置主键 Mysql怎么办

## 解答 ##

InnoDB对聚簇索引处理如下：

*  如果定义了主键，那么InnoDB会使用主键作为聚簇索引
 *  如果没有定义主键，那么会使用第一非空的唯一索引（NOT NULL and UNIQUE INDEX）作为聚簇索引
 *  如果既没有主键也找不到合适的非空索引，InnoDB会自动帮你创建一个不可见的、长度为6字节的row\_id，而且InnoDB 维护了一个全局的 dictsys.row\_id，所以未定义主键的表都共享该row\_id，每次插入一条数据，都把全局row\_id当成主键id，然后全局row\_id加1

很明显，缺少主键的表，InnoDB会内置一列用于聚簇索引来组织数据。而没有建立主键的话就没法通过主键来进行索引，查询的时候都是全表扫描，小数据量没问题，大数据量就会出现性能问题。

但是，问题真的只是查询影响吗？不是的，对于生成的ROW\_ID，其自增的实现来源于一个全局的序列，而所以有ROW\_ID的表共享该序列，这也意味着插入的时候生成需要共享一个序列，那么高并发插入的时候为了保持唯一性就避免不了锁的竞争，进而影响性能

## 解答 ##

我们看完疑问二的解答就知道 即便我们不设置主键 数据也会帮我们去生成一个默认的主键 有点像 类默认生成构造器的思想

有了主键之后呢？

![format_png 7][]

为什么会自动排序 大家都知道了 其实在文章之初就会有很多人明白是为什么 大概脑子里会有答案

## 疑问三 ##

为什么要进行排序

## 解答 ##

我们都知道 在进行数据查找的时候 比如几个基础的查找算法的 前提都是 先进行排序 再者 List 和 Map 的一些区别肯定都很熟悉了 当然是为了更快 所以无需的Id 会对插入效率造成影响 也就是为什么很多文章说使用自增Id比UUID 或者雪花算效率高的原因 第一个是UUID他们是随机的 每次都要重新排序 甚至可能会因为排序的原因造成页数据的更换 还有就是 UUID 一般都比较长 一页是16Kb 数据越短 一页的数据就会越多 查询的速度也就比较快

这里说完为什么排序 还有一个点就是上面的**页目录**

## 疑问三 ##

页目录的作用是什么？

通过上一篇文章可以明白 页目录的作用是减少范围

![format_png 8][]

这里的第三层是数据 上面都是目录 可以增加数据的检索效率

![format_png 9][]

如果没有目录我们需要去直接遍历数据区域 会降低效率 目录能帮我们缩小范围 这里 我们查询 ID = 3 我们可以通过目录知道 1 < 3 < 4 如果 在1 中没有找到对应数据 但是 因为 3 < 4 就不会接着往下查询了 直接返回空结果

当第一页没有的时候去第二页查询 不会直接跳到第二页查询

![format_png 10][]

为了提高效率 当目录数据数量过多时 就会网上延伸一层树 同时可以减少磁盘的IO次数

![format_png 11][]

关于所有叶子节点都处于同一深度是如何实现的？这与B+树具体的插入和删除算法有关。简单解释一下插入时的情况，根据插入值的大小，逐步向下直到对应的叶子节点。如果叶子节点关键字个数小于2t，则直接插入值或者更新卫星数据；如果插入之前叶子节点已经满了，则分裂该叶子节点成两半，并把中间值提上到父节点的关键字中，如果这导致父节点满了的话，则把该父节点分裂，如此递归向上。所以树高是一层层的增加的，叶子节点永远都在同一深度。

## 小总结 ##

*  内部节点并不存储真正的信息，而是保存其叶子节点的最小值作为索引。
 *  每次插入删除都进行更新(此时用到parent指针)，保持最新状态。
 *  B+ 树非叶子节点上是不存储数据的，仅存储键值
 *  B+只在底层树储存数据，上层就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。
 *  B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。
 *  一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。
 *  因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。
 *  那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单
 *  有心的读者可能还发现上图 B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。
 *  其实上面的 B 树我们也可以对各个节点加上链表。这些不是它们之前的区别，是因为在 MySQL 的 InnoDB 存储引擎中，索引就是这样存储的。
 *  我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

[format_png]: https://img-blog.csdnimg.cn/img_convert/279a9fb088e611a68eac45357f103361.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/8fb005a7471ff6cdf0c284b6ad820c76.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/924938bb760f98f1f796e23f2639affb.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/db13eda7c46fe41341f82517adc91e9f.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/b7444375096046a3931ada13c80c4eb5.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/8e4f796aaa5c11fc07bdddda0bc0ec41.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/c8721db48166a93ea980145822d0f13c.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/8126424fa5a715709da4eb874ca4c2b5.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/d4bb4ad2c3830a9f94d4e4d6835cadaf.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/2cedc36e22effee3839fca6a324681b0.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/6e90b825e32fcb9af4768aa896bc8525.webp?x-oss-process=image/format,png
[format_png 11]: https://img-blog.csdnimg.cn/img_convert/9b4d1ad5e9b574a1b4dd925006ab30c1.webp?x-oss-process=image/format,png