数据结构之B树

B树是一种平衡树数据结构，主要用于数据库和文件系统等大规模数据存储和检索的应用。它是一种自平衡的多路搜索树，能够保持数据有序，并允许高效的插入、删除和搜索操作。

B树的定义
B树（B-Tree）具有以下性质：
1. 每个节点包含若干个键值和指向子节点的指针：
- 一个节点最多可以包含 \(m-1\) 个键值和 \(m\) 个指针（其中 \(m\) 是B树的阶，通常大于等于3）。
- 所有键值按升序排列。
2. 根节点至少有两个子节点，除非它是叶节点。
3. 内部节点的键值个数范围：
- 非根节点至少包含 \(\lceil \frac{m}{2} \rceil - 1\) 个键值。
- 最多包含 \(m-1\) 个键值。
4. 叶节点都在同一层。

B树的操作
插入操作
1. 查找插入位置：从根节点开始，根据键值大小找到适当的叶节点。
2. 插入键值：将键值插入叶节点。如果叶节点已满，则需要分裂（split）：
- 将叶节点分成两个节点，将中间键值提升到父节点。
- 如果父节点也已满，递归进行分裂。

删除操作
1. 查找删除键值：从根节点开始，找到包含该键值的节点。
2. 删除键值：
- 如果删除的键值在叶节点中，直接删除。
- 如果在内部节点中，用前驱或后继键值替代，然后删除前驱或后继键值。
- 处理删除后节点的键值数少于 \(\lceil \frac{m}{2} \rceil - 1\) 的情况，通过合并或借用兄弟节点的键值来维护B树的性质。

B树的优点
1. 高效的磁盘读写：由于每个节点可以包含多个键值和指针，B树减少了访问磁盘的次数，提高了大数据量情况下的性能。
2. 平衡性：B树总是保持平衡，所有叶节点都在同一层，保证了搜索、插入、删除操作的时间复杂度为 \(O(\log n)\)。

B树的应用
B树广泛应用于数据库系统和文件系统中。例如：
- 数据库索引：B树用于实现数据库的索引结构，支持快速的查找、插入和删除操作。
- 文件系统：许多现代文件系统使用B树来管理磁盘块和文件目录，以提高存储和检索的效率。

B树的示例
假设有一棵阶为3的B树（即每个节点最多有2个键值和3个子节点），其插入和删除操作可以如下图所示（简化示意）：

初始状态：

[10]
/ \
[5] [15, 20]

插入25后：

[10]
/ \
[5] [15, 20, 25]

插入30并分裂：

[10, 20]
/ | \
[5] [15] [25, 30]

删除20后：

[10, 25]
/ | \
[5] [15] [30]

B树通过这种结构和操作，保证了数据的有序性和平衡性，从而提高了存储和检索的效率。