B-树是一种自平衡多路搜索树，所有叶子节点位于同一层，每个节点最多有m-1个关键字、m个子节点，非根节点至少有⌈m/2⌉−1个关键字。插入时从根开始查找插入位置，节点满则分裂，确保不溢出；删除时若关键字在内部节点，用子树最值替换，遍历中保证节点关键字数大于t−1，不足时通过借元素或合并调整。核心操作为分裂与合并，维持树的平衡性，适用于文件系统和数据库等需高效磁盘I/O的场景。
实现B-树的关键在于理解其自平衡特性：每个节点可以包含多个关键字，并且保持所有叶子节点在同一层。B-树广泛用于文件系统和数据库中，因为它能有效减少磁盘I/O操作。下面以阶数为 m 的B-树为例（即每个节点最多有 m 个子节点，最多 m-1 个关键字），讲解C++中的插入与删除操作，并配以逻辑说明。
什么是B-树？
B-树满足以下性质：
- 根节点至少有一个关键字，非根内部节点至少有 ⌈m/2⌉−1 个关键字。
- 每个节点最多有 m−1 个关键字，最多 m 个子节点。
- 所有叶子节点位于同一层，代表查找失败的位置。
- 节点中的关键字按升序排列，子树的关键字范围由父节点分隔。
例如，一个 5 阶 B-树（m=5）的节点最多有 4 个关键字、5 个子节点，最少有 2 个关键字（非根节点）。
B-树节点结构设计
在C++中定义节点类型：
立即学习“C++免费学习笔记（深入）”；
struct BTreeNode {
bool isLeaf;
int n; // 当前关键字数量
std::vector keys;
std::vector children;
BTreeNode(int t, bool leaf) : isLeaf(leaf), n(0) {
keys.resize(2 * t - 1);
children.resize(2 * t, nullptr);
}};
其中 t 是最小度数（minimum degree），表示每个节点至少有 t−1 个关键字（非根节点）、t 个子节点。整个树的阶数 m = 2t。
插入操作图解与实现
插入过程从根开始，向下找到合适的叶子节点插入位置。若叶子节点已满（关键字数达到 2t−1），则需要分裂。
步骤分解：
- 若根节点满，则创建新根，原根作为子节点，并进行分裂。
- 递归查找插入路径，遇到满节点就提前分裂，确保后续插入不会溢出。
- 最终将关键字插入到某个叶子节点中。
分裂节点示例：
假设 t=2（即最多3个关键字），当前叶子节点已含 [10,20,30]，再插入40会导致溢出。此时将中间元素20上移至父节点，原节点拆分为 [10] 和 [30,40]，返回结果如下：
父节点
/ \
[10] [30,40]
C++代码片段：
void splitChild(BTreeNode* parent, int i, BTreeNode* fullChild) {
BTreeNode* newNode = new BTreeNode(fullChild->t, fullChild->isLeaf);
newNode->n = t - 1;
for (int j = 0; j < t - 1; j++)
newNode->keys[j] = fullChild->keys[j + t];
if (!fullChild->isLeaf) {
for (int j = 0; j < t; j++)
newNode->children[j] = fullChild->children[j + t];
}
for (int j = parent->n; j > i; j--)
parent->children[j + 1] = parent->children[j];
parent->children[i + 1] = newNode;
for (int j = parent->n - 1; j >= i; j--)
parent->keys[j + 1] = parent->keys[j];
parent->keys[i] = fullChild->keys[t - 1];
parent->n++;}
插入主函数需处理根节点是否满的情况：
void insertNonFull(BTreeNode* node, int key);
void insert(int key) {
if (root->n == 2*t - 1) {
BTreeNode* newRoot = new BTreeNode(t, false);
newRoot->children[0] = root;
splitChild(newRoot, 0, root);
root = newRoot;
}
insertNonFull(root, key);
}
删除操作图解与实现
删除更复杂，因为必须维持B-树的平衡性。核心思想是：在遍历时保证当前节点的关键字数大于 t−1，否则通过合并或借元素来调整。
主要情况分析：
-
被删关键字在叶子节点：直接删除；若导致节点关键字过少，则考虑从兄弟借或合并。
-
被删关键字在内部节点：
- 左子树高度足够：用左子树最大值替换该关键字。
- 右子树高度足够：用右子树最小值替换。
- 都不够：合并左右子树并下移关键字。
-
当前节点关键字太少（仅 t−1 个）：尝试从兄弟借一个关键字；若兄弟也少，则与其父关键字一起合并。
举例说明：
要删除关键字 K，所在节点只剩 t−1 个元素。检查任一兄弟是否有富余（> t−1）元素：
- 若有，将父节点的一个关键字下移，兄弟的一个关键字上提，实现“旋转”。
- 若无，则将父节点关键字与另一个兄弟合并成一个新节点。
这样可避免中途节点太小，影响后续操作。
伪代码流程：
void remove(BTreeNode* node, int key) {
int idx = findKey(node, key);
if (idx < node->n && node->keys[idx] == key) {
if (node->isLeaf)
removeFromLeaf(node, idx);
else
removeFromInternal(node, idx);
} else {
if (node->isLeaf) return; // 不存在
bool lastChild = (idx == node->n);
if (node->children[idx]->n < t)
fill(node, idx);
remove(node->children[idx], key);
}}
其中 fill() 函数负责处理子节点元素不足的问题，调用 borrowFromPrev()、borrowFromNext() 或 merge() 完成调整。
总结
B-树的插入与删除本质上是对多路平衡搜索树的动态维护。关键点包括：
- 插入时采用“向上分裂”策略，防止溢出。
- 删除时采用“向下填充”机制，保证节点不欠元素。
- 分裂与合并操作是核心辅助手段。
虽然实现较AVL或红黑树复杂，但B-树在大规模数据存储场景下具有显著优势——层数极低，访问效率高。
基本上就这些。掌握好分裂、合并、借元素三种技巧，就能完整实现B-树的增删逻辑。
