C++如何实现一个B-树_C++数据结构之B-树的插入与删除操作图解

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<int> keys;
    std::vector<BTreeNode*> children;
<pre class="brush:php;toolbar:false;">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;
<pre class="brush:php;toolbar:false;">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++;

登录后复制

}

插入主函数需处理根节点是否满的情况：

标签： node c++ 排列