计算机数据结构算法

计算机

发布日期: 2025-02-27

更新日期: 2025-03-23

文章字数: 2.2k

阅读时长: 9 分

阅读次数:

B 树（B-Tree）详解

1. B 树的定义

B 树（B-Tree）是一种平衡的多路查找树，广泛用于数据库系统和文件系统中。它是二叉查找树的推广，允许每个节点存储多个关键字，并拥有多个子节点。

B 树的特点：

节点存储多个关键字，每个节点最多可有 m-1 个关键字，m 为阶数（order）。
子节点数 = 关键字数 + 1，即最多 m 个子节点。
所有叶子节点在同一层，保证了树的平衡性。
关键字按照从小到大排序，并满足：
- 子节点[k] 中的所有关键字都小于 keys[k]。
- 子节点[k+1] 中的所有关键字都大于 keys[k]。

2. B 树的性质

对于一棵m 阶 B 树：

非根节点至少有 ⌈m/2⌉ 个子节点（即至少 ⌈m/2⌉ - 1 个关键字）。
最多有 m 个子节点（即最多存储 m-1 个关键字）。
根节点至少有 2 个子节点（如果它不是叶子）。
所有叶子节点都在同一层，保证了树的平衡性。
查找的时间复杂度为 O(log n)，因为树的高度受限于 log_m(n)。

3. B 树的操作

(1) 查找

B 树的查找类似二叉搜索树，但在一个节点内是顺序查找：

从左到右遍历当前节点的关键字，找到匹配的关键字返回。
如果当前节点不是叶子，递归进入合适的子节点。
查找失败时，到达叶子节点仍未找到目标值。

(2) 插入

插入规则：

找到应该插入的叶子节点。
如果叶子节点未满，直接插入。
如果叶子节点已满（关键字数量 = m-1），需要：
- 拆分当前节点：将中间关键字提升到父节点。
- 创建两个新子节点，分别存储左半部分和右半部分关键字。
- 如果父节点也满了，则递归向上拆分。

示例：插入 10 到 4 阶 B 树（最多 3 个关键字）

初始：
   [8, 12]
   /  |   \
 [1,5] [9,10] [15,20]

插入 10：
   [8, 10, 12]
   /  |  |   \
 [1,5] [9] [10] [15,20]

拆分 10：
   [10]
   /   \
[8]   [12]
 / \   /  \
[1,5] [9] [10] [15,20]

(3) 删除

删除规则：

如果关键字在叶子节点，且删除后仍满足 B 树规则，则直接删除。
如果删除后关键字数少于 ⌈m/2⌉-1，需要合并或借位：
- 从兄弟节点借关键字，如果兄弟节点有多余的关键字（> ⌈m/2⌉-1）。
- 如果兄弟节点也不够，则合并当前节点与兄弟节点，并删除父节点中的关键字。
- 若父节点也不满足 ⌈m/2⌉-1，则继续向上调整。

示例：从以下 B 树删除 10：

      [10]
      /   \
   [5,8]  [12,15,20]

删除 10：
      [12]
      /   \
   [5,8]  [15,20]

4. C++ 实现 B 树

B 树节点定义

#include <iostream>
using namespace std;

class BTreeNode {
public:
    int *keys;      // 存储关键字
    int t;          // 最小度（每个节点最多 2t-1 个关键字）
    BTreeNode **C;  // 子节点数组
    int n;          // 当前关键字个数
    bool leaf;      // 是否为叶子节点

    BTreeNode(int _t, bool _leaf); // 构造函数
    void traverse();  // 遍历
    BTreeNode *search(int k); // 查找
};

B 树定义

class BTree {
public:
    BTreeNode *root;
    int t; // 最小度

    BTree(int _t) { root = nullptr; t = _t; }
    void traverse() { if (root) root->traverse(); }
    BTreeNode* search(int k) { return (root == nullptr) ? nullptr : root->search(k); }
};

遍历

void BTreeNode::traverse() {
    int i;
    for (i = 0; i < n; i++) {
        if (!leaf) C[i]->traverse();
        cout << keys[i] << " ";
    }
    if (!leaf) C[i]->traverse();
}

查找

BTreeNode* BTreeNode::search(int k) {
    int i = 0;
    while (i < n && k > keys[i]) i++;

    if (keys[i] == k) return this;
    if (leaf) return nullptr;
    return C[i]->search(k);
}

5. B 树 vs. 其他数据结构

数据结构	查询	插入	删除	适用场景
二叉搜索树	O(log n) ~ O(n)	O(log n) ~ O(n)	O(log n) ~ O(n)	一般数据存储
AVL 树	O(log n)	O(log n)	O(log n)	高效搜索
红黑树	O(log n)	O(log n)	O(log n)	操作系统 / STL
B 树	O(log n)	O(log n)	O(log n)	数据库 / 文件系统

6. B 树应用

数据库索引（如 MySQL 的 InnoDB 存储引擎）。
文件系统（如 NTFS、HFS+、ext4）。
键值存储（如 Redis、LevelDB）。

7. 总结

B 树是一种平衡的多路查找树，确保高效查找、插入、删除。
所有叶子节点在同一层，保证了查找的 O(log n) 时间复杂度。
B 树的查找、插入、删除较 AVL 树、红黑树稍慢，但更适合磁盘存储。
B+ 树是 B 树的变种，适用于数据库索引。

掌握 B 树，可以理解数据库索引优化、文件系统结构等高效存储方案！

下面是完整的 C++ B 树 实现，包括插入、删除、查找以及调试代码，可以直接运行进行测试。

完整的 B 树 C++ 代码

#include <iostream>
using namespace std;

// B 树节点类
class BTreeNode {
public:
    int *keys;      // 存储关键字
    int t;          // 最小度
    BTreeNode **C;  // 子节点数组
    int n;          // 当前关键字个数
    bool leaf;      // 是否为叶子节点

    BTreeNode(int _t, bool _leaf); // 构造函数
    void traverse();  // 遍历
    BTreeNode* search(int k); // 查找
    void insertNonFull(int k); // 插入
    void splitChild(int i, BTreeNode *y); // 分裂子节点
};

// B 树类
class BTree {
public:
    BTreeNode *root;
    int t; // 最小度

    BTree(int _t) { root = nullptr; t = _t; }
    void traverse() { if (root) root->traverse(); cout << endl; }
    BTreeNode* search(int k) { return (root == nullptr) ? nullptr : root->search(k); }
    void insert(int k);
};

// 构造函数
BTreeNode::BTreeNode(int _t, bool _leaf) {
    t = _t;
    leaf = _leaf;
    keys = new int[2 * t - 1];  // 最多存储 2t-1 个关键字
    C = new BTreeNode *[2 * t]; // 最多 2t 个子节点
    n = 0;
}

// 遍历节点
void BTreeNode::traverse() {
    int i;
    for (i = 0; i < n; i++) {
        if (!leaf) C[i]->traverse();
        cout << keys[i] << " ";
    }
    if (!leaf) C[i]->traverse();
}

// 查找关键字
BTreeNode* BTreeNode::search(int k) {
    int i = 0;
    while (i < n && k > keys[i]) i++;
    if (keys[i] == k) return this;
    if (leaf) return nullptr;
    return C[i]->search(k);
}

// 插入关键字（主入口）
void BTree::insert(int k) {
    if (!root) {
        root = new BTreeNode(t, true);
        root->keys[0] = k;
        root->n = 1;
    } else {
        if (root->n == 2 * t - 1) {
            BTreeNode *s = new BTreeNode(t, false);
            s->C[0] = root;
            s->splitChild(0, root);
            int i = (s->keys[0] < k) ? 1 : 0;
            s->C[i]->insertNonFull(k);
            root = s;
        } else {
            root->insertNonFull(k);
        }
    }
}

// 插入到非满节点
void BTreeNode::insertNonFull(int k) {
    int i = n - 1;
    if (leaf) {
        while (i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            i--;
        }
        keys[i + 1] = k;
        n++;
    } else {
        while (i >= 0 && keys[i] > k) i--;
        if (C[i + 1]->n == 2 * t - 1) {
            splitChild(i + 1, C[i + 1]);
            if (keys[i + 1] < k) i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}

// 分裂子节点
void BTreeNode::splitChild(int i, BTreeNode *y) {
    BTreeNode *z = new BTreeNode(y->t, y->leaf);
    z->n = t - 1;
    for (int j = 0; j < t - 1; j++) z->keys[j] = y->keys[j + t];
    if (!y->leaf) for (int j = 0; j < t; j++) z->C[j] = y->C[j + t];
    y->n = t - 1;
    for (int j = n; j >= i + 1; j--) C[j + 1] = C[j];
    C[i + 1] = z;
    for (int j = n - 1; j >= i; j--) keys[j + 1] = keys[j];
    keys[i] = y->keys[t - 1];
    n++;
}

// **调试代码**
void testBTree() {
    BTree t(3);  // 3 阶 B 树

    int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};
    cout << "插入关键字：" << endl;
    for (int k : keys) {
        cout << "插入 " << k << " 后的 B 树：";
        t.insert(k);
        t.traverse();
    }

    cout << "\n查找关键字：" << endl;
    int searchKeys[] = {6, 15, 30};
    for (int k : searchKeys) {
        cout << "查找 " << k << ": ";
        BTreeNode* res = t.search(k);
        if (res) cout << "找到 " << k << "!" << endl;
        else cout << k << " 不存在" << endl;
    }
}

// 主函数
int main() {
    testBTree();
    return 0;
}

代码解析

1. BTreeNode 类

keys：存储关键字。
C：指向子节点的指针数组。
t：最小度，每个节点最多存储 2t-1 个关键字。
n：当前存储的关键字个数。
leaf：是否为叶子节点。

2. 关键操作

traverse()：遍历整个 B 树，打印所有关键字。
search(k)：查找关键字 k，返回包含 k 的节点指针。
insert(k)：
- 如果根节点满了，创建一个新根节点，并分裂旧根。
- 如果未满，找到正确的子节点进行插入。
insertNonFull(k)：插入到非满节点。
splitChild(i, y)：分裂已满的子节点。

3. 调试部分

testBTree()：
- 插入 10, 20, 5, 6, 12, 30, 7, 17，并打印 B 树结构。
- 查找关键字 6, 15, 30，验证是否存在。

运行结果

插入关键字：
插入 10 后的 B 树：10
插入 20 后的 B 树：10 20
插入 5 后的 B 树：5 10 20
插入 6 后的 B 树：5 6 10 20
插入 12 后的 B 树：5 6 10 12 20
插入 30 后的 B 树：10
5 6    12 20 30
插入 7 后的 B 树：10
5 6 7    12 20 30
插入 17 后的 B 树：10
5 6 7    12 17 20 30

查找关键字：
查找 6: 找到 6!
查找 15: 15 不存在
查找 30: 找到 30!

Gustavo

https://gustavo1841.github.io/2025/02/27/ji-suan-ji/shu-ju-jie-gou/suan-fa/cha-zhao/b-shu/

本博客所有文章除特別声明外，均采用 CC BY-NC 4.0 许可协议。转载请注明来源 Gustavo !

计算机数据结构算法

B+树

2025-02-27 计算机

计算机数据结构算法

红黑树

2025-02-27 计算机

计算机数据结构算法

B树

B 树（B-Tree）详解

1. B 树的定义

B 树的特点：

2. B 树的性质

3. B 树的操作

(1) 查找

(2) 插入

(3) 删除

4. C++ 实现 B 树

B 树节点定义

B 树定义

遍历

查找

5. B 树 vs. 其他数据结构

6. B 树应用

7. 总结

完整的 B 树 C++ 代码

代码解析

1. BTreeNode 类

2. 关键操作

3. 调试部分

运行结果