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 keys[j] = fullChild->keys[j + t];if (!fullChild->isLeaf) { for (int j = 0; j 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 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 children[idx], key);}
}
其中 fill() 函数负责处理子节点元素不足的问题，调用 borrowFromPrev()、borrowFromNext() 或 merge() 完成调整。
总结
B-树的插入与删除本质上是对多路平衡搜索树的动态维护。关键点包括：
插入时采用“向上分裂”策略，防止溢出。删除时采用“向下填充”机制，保证节点不欠元素。分裂与合并操作是核心辅助手段。
虽然实现较AVL或红黑树复杂，但B-树在大规模数据存储场景下具有显著优势——层数极低，访问效率高。
基本上就这些。掌握好分裂、合并、借元素三种技巧，就能完整实现B-树的增删逻辑。
以上就是C++如何实现一个B-树_C++数据结构之B-树的插入与删除操作图解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1489879.html
微信扫一扫 
支付宝扫一扫 
