B树与B+树基础

没有写完，以后再补吧。

本文创建于 2024-11-27；修改于 2024-11-27；

1. B树的性质

一棵 M 阶B树 T，满足以下条件：

1. 每个结点至多拥有M棵子树
2. 根结点至少拥有两棵子树
3. 除了根结点以外，其余每个分支结点至少拥有 M/2 棵子树
4. 所有的叶结点都在同一层上
5. 有 k 棵子树的分支结点则存在 k-1 个关键字，关键字按照递增顺序进行排序
6. 关键字数量满足 ceil(M/2) - 1 <= n <= M-1

2. B树 和 B+ 树的区别

B树：所有节点存储数据；

B+树：叶子节点存储数据，内节点用于索引；

应用场景：

在内存中使用 B+树 存储数据的索引，索引对应的数据存储在硬盘内；这样可以做到一次寻址访问数据，性能很高。

3. B树添加节点

B树 会将新节点插入到叶子节点，当叶子节点数据达到阈值(图中是5)时，开始分裂，如图所示：

4. B树 删除节点

有如下 B树，想要删除节点A，由于B树的性质，”关键字数量满足 ceil(M/2) - 1 <= n <= M-1” ，所以，我们无法直接将A节点删除：

1. 使用 合并 方法进行删除节点：

1. 从父节点 借位 进行删除节点：

因为此时如果把 F 推下去合并，L 的左子树就不再满足 B树性质，所以要从父节点借位以满足性质。

• 借不到就合并：

1. 如果要删除的节点是一个内节点，则通过 借位 将内节点移动到叶子节点再进行叶子节点的删除流程。

2. 删除流程总结：

   • 借 || 合 -> 删