【考研408&数据结构】一文讲透B树与B+树

B树

这里的B是啥b？

说到b树 可能很多人心里没点b树 就是说 不知道这b树到底是啥b

认识一个事物从他的名字开始

B-tree 这里的“B”代表的是Balanced 表示平衡

所以b树其实就是平衡树

那么说到底 什么叫平衡 呢？

平衡二叉树就是最典型 的平衡 没有学到平衡二叉树的朋友 可以移步到这里->啥b都能学明白的平衡二叉树

这里平衡就是指 最高子树的高度 -最矮子树的高度 <2

也就是 不能差太多嘛 核心的思想就是 所有子树高度差不多

我们把他的核心思想记住 再看二叉平衡树中的“二” 凭什么只能是这个数字呢 ？为什么不能三叉 四叉 五仰八叉...

所以b树就来了 他可以理解成平衡二叉树的泛化

把平衡二叉树的核心思想再增强一个档次 绝对平衡 ---所有子树 必须一样高

然后再把“二”泛化 就得到了B树

学过Java的朋友这时候肯定能跳起来说“哦~！用Java的角度理解就是 b树其实就是二叉平衡树的抽象类 二叉树其实是b树这个抽象类的其中一种具体实现类 还有很多其他3叉平衡树 、四叉五叉等等都是b树的实现类 ”

有了具体实现类 咱理解b树的抽象规则 那不就简单多了 何必在王道书上每条性质在做阅读理解？

抽象性质解读

我们通常将二叉、三叉、五叉这里的数字称之为阶数 五叉平衡树 就是五阶b树

那么抽象 来说就是m阶平衡树

m阶 最多m路呗 这一点肉眼可见

再来观察上图小细节 哦其实每一坨椭圆是结点 结点当中使用了若干个关键字（里边装着的数字） 使用关键字 把路径分成了m条路径 这里用数学的区间就好理解了

这里面每一个结点当中的每个关键字就是x轴上的分段点 分段点左边比分点小 反之 右边比分段点大 左小右大呗 这一点和平衡二叉树一样

值得注意的是 非叶结点中被划分的是指向下一个结点的指针 而叶节点下面被划分的是指向具体的值的指针

平衡

他是如何维持平衡的？

节点键值数量：每个节点最多可以有m-1个关键字，其中m是树的阶（最小度数）。这意味着每个节点最多有m个子节点。

通过限制每个节点的键值数量，B树能够保持每个节点的负载大致相同，这有助于平衡树的结构，避免某些节点过载而其他节点空闲。

根节点至少有2个子节点（在非空B树中）：这样可以保证树的根节点不会过于倾斜。

内部节点至少有⌈m/2⌉-1个键值：保证树的深度不会过浅。

叶子节点都在同一层：保持树的高度一致。

节点键值和子节点指针一一对应：每个键值对应一个子节点指针，形成了有序的键值索引。

讲完性质讲操作了

B树的插入操作

1. 找到插入位置：
   • 从根节点开始，根据待插入关键字与当前节点关键字的比较结果，决定是向左子树还是向右子树移动。
   • 重复此过程，直到找到适当的插入位置。
2. 插入关键字：
   • 如果找到的插入位置为空（即节点不存在），则直接插入新关键字。
   • 如果该位置已有关键字，将新关键字插入到关键字列表中，并保持列表的有序性。
3. 检查并调整平衡：
   • 插入后，如果节点的关键字数量超过最大限制（m-1），则需要进行分裂。 分裂前：

   

   • 将中间的关键字提升到父节点，并将原节点分裂为两个子节点，分别包含提升关键字的前半部分和后半部分。 分裂后：

   

   • 如果父节点也需要分裂，重复此过程，直到树重新平衡。
4. 更新父节点：
   • 在分裂过程中，可能需要更新父节点的关键字和子节点指针。
   • 如果分裂达到根节点，可能需要创建新的根节点。

B树的删除操作 --删 用左边的最右或是右边的最左来替补

1. 找到要删除的关键字：
   • 从根节点开始，根据待删除关键字与当前节点关键字的比较结果，决定是向左子树还是向右子树移动。
   • 重复此过程，直到找到包含待删除关键字的节点。
2. 删除关键字：
   • 如果待删除关键字是叶子节点中的唯一关键字，直接删除该节点。 若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字直接前驱:当前关键字左侧指针所指子树中“最右下”的元素
   • 如果待删除关键字不是叶子节点中的唯一关键字，可以选择用前一个或后一个关键字替换它，然后在叶子节点中删除该替换的关键字。
3. 检查并调整平衡：
   • 删除后，如果节点的关键字数量低于最小限制（⌈m/2⌉-1），则需要进行合并。
   • 尝试与兄弟节点合并，如果兄弟节点有足够的关键字，可以借用或合并。
   • 如果合并后父节点的关键字数量也低于最小限制，可能需要继续合并直到树重新平衡。
4. 更新父节点：
   • 在删除和合并过程中，可能需要更新父节点的关键字和子节点指针。
   • 如果删除影响到根节点，可能需要调整根节点。

删后 右边的最左下角 82来替补！

他的本质 实际上就是在不断的匹配不等式 要求在删除以后 满足原先不等式的性质！

B树的插入与删除操作都需要精心设计以保持树的平衡。插入操作通过分裂节点来处理节点过载，而删除操作通过合并节点来处理节点欠载。这些操作确保了B树的高度保持在对数级别，从而保证了操作的时间复杂度为O(log n)。

B+树

由于考研只要求考察他的概念和性质 这里只讲解概念和性质

一棵m阶的B+树需满足下列条件：

• 每个分支结点最多有 m 棵子树（孩子结点）。
• 非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。
• 可以理解为：要追求“绝对平衡”，即所有子树高度要相同
• 结点的子树个数与关键字个数相等。(这是和B树很大的不同)
• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻
• 叶结点按大小顺序相互链接起来。
• 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

值得注意

• 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶子结点中的每个索引项只是包含了 对应子树最大关键字和指向该孩子树的指针，不含有该关键字对应记录的存储地址。
• 在B+树中，终端结点包含全部关键字及相应记录的指针，即非终端结点出现过的关键字也会在这重 复出现一次。而B树是不重复的。