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

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

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

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

所以b树其实就是平衡树

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

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

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

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

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

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

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

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

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

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

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

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

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

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

他是如何维持平衡的？

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

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

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

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

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

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

找到插入位置：
- 从根节点开始，根据待插入关键字与当前节点关键字的比较结果，决定是向左子树还是向右子树移动。
- 重复此过程，直到找到适当的插入位置。
插入关键字：
- 如果找到的插入位置为空（即节点不存在），则直接插入新关键字。
- 如果该位置已有关键字，将新关键字插入到关键字列表中，并保持列表的有序性。
检查并调整平衡：
- 插入后，如果节点的关键字数量超过最大限制（m-1），则需要进行分裂。分裂前：
- 将中间的关键字提升到父节点，并将原节点分裂为两个子节点，分别包含提升关键字的前半部分和后半部分。分裂后：
- 如果父节点也需要分裂，重复此过程，直到树重新平衡。
更新父节点：
- 在分裂过程中，可能需要更新父节点的关键字和子节点指针。
- 如果分裂达到根节点，可能需要创建新的根节点。

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