1. 概述
本文将介绍一种自平衡的树结构 —— B-树（B-tree）。这是一种广泛用于数据库和文件系统中的数据结构，尤其适合处理大规模数据的高效检索。
我们将详细讲解 B-树的结构特性、基本操作（查找、插入、删除）及其时间复杂度，并结合图示帮助理解。
2. 简介
B-树是一种多路平衡查找树，属于自平衡树结构。它与二叉搜索树（BST）类似，但每个节点可以拥有多个子节点和多个键值，从而降低树的高度，提升查找效率。
与 BST 的主要区别：
- BST 每个节点最多有两个子节点；
- B-树每个节点可以有多个子节点（由树的阶数决定）；
- B-树支持每个节点存储多个键，适合磁盘等 I/O 操作频繁的场景。
下面是一个典型的 B-树示例：
3. B-树的性质
B-树具备以下关键特性：
✅ 每个节点最多有 N 个子节点（N 为阶数）
✅ 每个节点最多包含 N - 1 个键
✅ 每个节点（除根节点）至少包含 ⌈N/2⌉ - 1 个键
✅ 所有叶子节点位于同一层
✅ 根节点至少有两个子节点（除非它是叶子节点）
举个例子，若 B-树的阶数为 6：
- 每个节点最多可有 6 个子节点
- 每个节点最多可包含 5 个键
- 每个节点（非根）至少包含 2 个键
4. B-树操作详解
B-树的基本操作包括：查找、插入、删除。它们的时间复杂度均为 **O(log n)**。
4.1 查找
查找操作从根节点开始，逐层向下比较键值，决定进入哪个子节点，直到找到目标键或到达叶子节点。
时间复杂度： O(log n)
4.2 插入
插入操作始终发生在叶子节点。插入时需注意以下几点：
- 插入前必须确保节点未满
- 若节点已满，则需进行分裂（split）操作
- 分裂时将中间键上移到父节点，其余键均分到两个新节点中
插入示例：
我们从空树开始，插入 1 到 10，阶数设为 3：
- 插入 1、2、3 时，节点满，需分裂，将中间值 2 上移
- 插入 4、5、6 时，再次分裂，4 上移
- 最终形成一个结构合理的 B-树
插入过程如下图所示：
最终结构如下：
时间复杂度： O(log n)
4.3 删除
删除操作相对复杂，分为以下几种情况：
- 删除的键在叶子节点中，且删除后节点仍满足最小键数要求 → 直接删除
- 删除后节点键数不足 → 从兄弟节点借键（左或右）
- 若兄弟节点键数也刚好满足下限 → 合并当前节点与某兄弟节点，并将父节点的一个键下移
删除示例：
我们以一个阶数为 5 的 B-树为例：
- 删除 23：其所在节点键数足够，直接删除即可
- 删除 72：删除后节点键数不足，需从右兄弟借键
- 删除 65：左右兄弟键数不足，需合并节点
- 删除 70（内部节点）：可用前驱或后继替代，再递归删除替代节点
部分删除过程如下图所示：
最终结构如下：
时间复杂度： O(log n)
5. 总结
B-树是一种高效的自平衡多路查找树，适用于需要频繁进行磁盘读写或大规模数据存储的场景（如数据库索引、文件系统目录管理）。
它通过节点分裂与合并机制，保证了树的高度较低，从而提升查找、插入、删除效率。
关键点回顾：
- 每个节点可有多个键和多个子节点
- 所有叶子节点在同一层
- 插入时可能分裂，删除时可能合并或借键
- 时间复杂度为
O(log n)
掌握 B-树的结构与操作逻辑，有助于深入理解数据库索引、文件系统等底层机制，是系统设计中非常重要的基础之一。