B 树

                     

贡献者: addis

  • 本文处于草稿阶段。
  • 本文含人工智能辅助创作,已审核。
预备知识 二叉树

   B-树(B-tree),是一种常见的自平衡树数据结构,它允许进行高效的插入、删除和搜索操作。它常用于数据库和文件系统,因是因为 B-树可以最小化数据的读写操作。

   B-树与二叉搜索树的不同之处在于,它每个节点可以有两个以上的子节点,并针对读取和写入大块数据的系统进行了优化。“平衡” 一词指的是所有叶节点都在同一深度的特性,这确保了低高度,从而能快速执行操作。

  

未完成:画图

B-树结构

   一个阶数(degree 或 order)为 $m$ 的 B-树具有以下特性:

代码 1:Btree.h
// ========= 代码未经测试 =====
BTREE_ORDER = 3;

struct Node {
    int n; // 子节点数
    bool leaf; // 是否是叶节点
    int key[BTREE_ORDER*2-1]; // 键值
    Node *child[BTREE_ORDER*2]; // 子节点指针
    
    Node() {
        n = 0;
        leaf = false;
        for (int i = 0; i < 2*BTREE_ORDER; i++)
            child[i] = nullptr;
    }
};

// 在子树 x 中搜索键值 k
Node* BtreeSearch(Node* x, int k) {
    for (int i = 0; i < x->n && x->key[i] <= k; ++i)
        ; // 当阶数较高可以用二分法来优化这一步
    if (i < x->n && k == x->key[i])
        return x; // 已找到
    if (x->leaf)
        return nullptr; // 未找到
    return BtreeSearch(x->child[i], k);
}

// 遍历子树 x (按键值从小到大)
void traverse(Node* x)
{
    for (int i = 0; i < x->n; ++i) {
        if (leaf == false)
            traverse(x[i]);
        cout << " " << keys[i];
    }
    traverse(node->child[x->n]);
}

// ========= 以下未经审核 =====

// 插入键 k
void insert(int k, Node *r) {
    if (r->n == 2*BTREE_ORDER - 1) {
        Node *s = new Node();
        root = s;
        s->child[0] = r;
        splitChild(s, 0);
        insertNonFull(s, k);
    } else {
        insertNonFull(r, k);
    }
}

void splitChild(Node *x, int i) {
    Node *t = x->child[i];
    Node *y = new Node();
    y->leaf = t->leaf;
    y->n = BTREE_ORDER - 1;

    for (int j = 0; j < BTREE_ORDER - 1; j++)
        y->key[j] = t->key[j + BTREE_ORDER];

    if (!t->leaf) {
        for (int j = 0; j < BTREE_ORDER; j++)
            y->child[j] = t->child[j + BTREE_ORDER];
    }

    t->n = BTREE_ORDER - 1;

    for (int j = x->n; j >= i + 1; j--)
        x->child[j + 1] = x->child[j];

    x->child[i + 1] = y;

    for (int j = x->n - 1; j >= i; j--)
        x->key[j + 1] = x->key[j];

    x->key[i] = y->key[0];
    x->n = x->n + 1;
}

void insertNonFull(Node *x, int k) {
    int i = x->n - 1;
    if (x->leaf) {
        x->key[i + 1] = k;
        x->n = x->n + 1;

        // Sorting the keys
        while (i >= 0 && k < x->key[i]) {
            x->key[i + 1] = x->key[i];
            i--;
        }
        x->key[i + 1] = k;
    } else {
        while (i >= 0 && k < x->key[i])
            i--;
        i++;
        if (x->child[i]->n == 2*BTREE_ORDER - 1) {
            splitChild(x, i);
            if (k > x->key[i])
                i++;
        }
        insertNonFull(x->child[i], k);
    }
}

   ========= 以下为草稿 ============

   2. 插入 插入的开始与搜索类似。然而,如果键应该插入的节点已满,我们必须分裂节点。

   分裂涉及到:

   将节点中的中间键上移至其父节点。 将剩余的键分裂成两个新的节点,并将它们作为新移动键的子节点链接。 如果父节点已满并且发生了分裂,那么这个过程会继续向上,直到找到一个非满父节点或者创建一个新的根节点。

   3. 删除 在 B-树中,删除是最复杂的操作。目标是移除一个键并仍然保持 B-树的属性。

   B-树操作示例 为了简化,我们将使用阶数为 m=3 的 B-树(也称为 2-3 树),其中每个节点最多可以有 3 个子节点。

   插入 让我们按顺序插入键 1, 2, 3, 4, 和 5。

   插入 1:树为空,所以 1 成为根。

   插入 2:根没有满,所以 2 被添加进去。

   Copy code 1 2 插入 3:根已满,所以我们必须分裂它。

   markdown Copy code 2 / \ 1 3 插入 4:从根开始,转到右子节点(3),这个节点没有满,所以 4 被添加进去。

   markdown Copy code 2 / \ 1 3 4 插入 5:从根开始,转到右子节点(3 4),这个节点已满,所以必须分裂它。父节点没有满,所以可以接受另一个键。

   markdown Copy code 2 4 / | \ 1 3 5 删除 我们删除 2:

   找到 2:从根开始,这包含 2。

   如果 2 有子节点,我们需要用后继或前驱键替换它,但在这种情况下,它没有。所以,2 可以简单地被删除:

   markdown Copy code 4 / \ 1 3 5 这就是如何在 B-树中插入和删除键!

   B-树有变体,如 B+树和 B*树,它们有自己的特定用途和优化。

                     

© 小时科技 保留一切权利