《恋上数据结构第 1 季》B 树，java 基础案例教程第二版答案

• 4阶B树
  

数据结构与算法笔记目录：《恋上数据结构》 笔记目录

**想加深

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

Java 基础推荐看这个**： Java 强化笔记目录

B 树是一种平衡的多路搜索树，多用于文件系统、数据库的实现；

仔细观察 B 树，有什么眼前一亮的特点？

• 1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点

• 拥有二叉搜索树的一些性质

• 平衡，每个节点的所有子树高度一致

• 比较矮

m 阶 B 树的性质

==========================================================================

数据库实现中一般用几阶 B 树？

• 200 ~ 300

B 树 vs 二叉搜索树

==============================================================================

B 树 和 二叉搜索树，在逻辑上是等价的；

多代节点合并，可以获得一个超级节点

• 2 代合并的超级节点，最多拥有 4 个子节点（至少是 4 阶 B 树）

• 3 代合并的超级节点，最多拥有 8 个子节点（至少是 8 阶 B 树）

• n 代合并的超级节点，最多拥有 2n 个子节点（ 至少是 2n 阶 B 树）

m 阶 B 树，最多需要 log2m 代合并；

搜索

=====================================================================

跟二叉搜索树的搜索类似：

1. 先在节点内部从小到大开始搜索元素

2. 如果命中，搜索结束

3. 如果未命中，再去对应的子节点中搜索元素，重复步骤 1

添加 – 上溢

==========================================================================

新添加的元素必定是添加到叶子节点：

插入 55：

插入 95：

再插入 98 呢？（假设这是一棵 4 阶 B 树）

• 最右下角的叶子节点的元素个数将超过限制

• 这种现象可以称之为：上溢（overflow）

添加 – 上溢的解决(假设 5 阶)

上溢节点的元素个数必然等于 m；

假设上溢节点最中间元素的位置为 k

• 将 k 位置的元素向上与父节点合并

• 将 [0, k - 1] 和 [k + 1, m - 1] 位置的元素分裂成 2 个子节点

这 2 个子节点的元素个数，必然都不会低于最低限制（┌ m/2 ┐ ? 1）

一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决

• 最极端的情况，有可能一直分裂到根节点

添加示例：

插入 98：

插入 52：

插入 54：

删除

=====================================================================

删除 – 叶子节点

假如需要删除的元素在叶子节点中，那么直接删除即可；

例：删除 30

删除 – 非叶子节点