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

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

穿越時空

发布： 2025-12-19 11:17:25

原创

779人浏览过

B-树是一种自平衡多路搜索树，所有叶子节点位于同一层，每个节点最多有m-1个关键字、m个子节点，非根节点至少有⌈m/2⌉−1个关键字。插入时从根开始查找插入位置，节点满则分裂，确保不溢出；删除时若关键字在内部节点，用子树最值替换，遍历中保证节点关键字数大于t−1，不足时通过借元素或合并调整。核心操作为分裂与合并，维持树的平衡性，适用于文件系统和数据库等需高效磁盘I/O的场景。

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

实现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++;

登录后复制

}

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

Tellers AI

Tellers是一款自动视频编辑工具，可以将文本、文章或故事转换为视频。

136

查看详情

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);
<pre class="brush:php;toolbar:false;">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() 完成调整。