深入理解B树（C++语言B树数据结构实现详解）

B树具有以下特性：

• 所有叶子节点位于同一层；
• 每个内部节点最多有 m 个子节点（m 称为阶数）；
• 除根节点外，每个内部节点至少有 ⌈m/2⌉ 个子节点；
• 根节点至少有两个子节点（除非它是叶子）；
• 键值按升序排列，子树介于相邻键之间。

B树的基本结构设计（C++）

我们先定义B树的节点结构。假设我们实现的是5阶B树（即每个节点最多4个键、5个子节点）。

#include <iostream>#include <vector>const int T = 3; // 最小度数，5阶B树：最多2*T-1=5个键class BTreeNode {public:    std::vector<int> keys;          // 存储键值    std::vector<BTreeNode*> children; // 子节点指针    bool isLeaf;                   // 是否为叶子节点    BTreeNode(bool leaf) : isLeaf(leaf) {}};class BTree {private:    BTreeNode* root;    void splitChild(BTreeNode* x, int i);    void insertNonFull(BTreeNode* x, int k);    void traverse(BTreeNode* x);    BTreeNode* search(BTreeNode* x, int k);public:    BTree() : root(nullptr) {}    void insert(int k);    void traverse();    bool search(int k);};

插入操作详解

B树的插入总是发生在叶子节点。如果叶子节点已满（即包含 2T-1 个键），我们需要先分裂该节点，再插入新键。

void BTree::insert(int k) {    if (root == nullptr) {        root = new BTreeNode(true);        root->keys.push_back(k);        return;    }    if (root->keys.size() == 2 * T - 1) {        BTreeNode* newRoot = new BTreeNode(false);        newRoot->children.push_back(root);        splitChild(newRoot, 0);        root = newRoot;    }    insertNonFull(root, k);}void BTree::splitChild(BTreeNode* x, int i) {    BTreeNode* y = x->children[i];    BTreeNode* z = new BTreeNode(y->isLeaf);    // 将y的后半部分移到z    for (int j = T; j < 2 * T - 1; ++j) {        z->keys.push_back(y->keys[j]);    }    y->keys.resize(T - 1);    if (!y->isLeaf) {        for (int j = T; j <= 2 * T - 1; ++j) {            z->children.push_back(y->children[j]);        }        y->children.resize(T);    }    x->children.insert(x->children.begin() + i + 1, z);    x->keys.insert(x->keys.begin() + i, y->keys[T - 1]);}void BTree::insertNonFull(BTreeNode* x, int k) {    int i = x->keys.size() - 1;    if (x->isLeaf) {        x->keys.push_back(0); // 占位        while (i >= 0 && x->keys[i] > k) {            x->keys[i + 1] = x->keys[i];            i--;        }        x->keys[i + 1] = k;    } else {        while (i >= 0 && x->keys[i] > k) i--;        i++;        if (x->children[i]->keys.size() == 2 * T - 1) {            splitChild(x, i);            if (x->keys[i] < k) i++;        }        insertNonFull(x->children[i], k);    }}

查找与遍历

查找操作类似于二叉搜索树，但需在多个子区间中判断。

bool BTree::search(int k) {    return search(root, k) != nullptr;}BTreeNode* BTree::search(BTreeNode* x, int k) {    int i = 0;    while (i < x->keys.size() && k > x->keys[i]) i++;    if (i < x->keys.size() && k == x->keys[i])        return x;    if (x->isLeaf)        return nullptr;    return search(x->children[i], k);}void BTree::traverse() {    if (root != nullptr)        traverse(root);    std::cout << std::endl;}void BTree::traverse(BTreeNode* x) {    int i;    for (i = 0; i < x->keys.size(); i++) {        if (!x->isLeaf)            traverse(x->children[i]);        std::cout << x->keys[i] << " ";    }    if (!x->isLeaf)        traverse(x->children[i]);}

使用示例

int main() {    BTree tree;    tree.insert(10);    tree.insert(20);    tree.insert(5);    tree.insert(6);    tree.insert(12);    tree.insert(30);    std::cout << "中序遍历结果: ";    tree.traverse(); // 输出应为有序序列    std::cout << "查找20: " << (tree.search(20) ? "找到" : "未找到") << std::endl;    std::cout << "查找25: " << (tree.search(25) ? "找到" : "未找到") << std::endl;    return 0;}

总结

通过本教程，你已经掌握了如何用C++实现一个基本的B树，包括插入、查找和遍历操作。虽然删除操作较为复杂（涉及合并与借键），但掌握了插入逻辑后，删除也可逐步实现。B树是许多高级系统（如MySQL的InnoDB引擎）的核心组件，深入理解B树插入删除机制对提升系统设计能力大有裨益。

希望这篇B树教程能帮助你打下坚实的数据结构基础！如果你有任何问题，欢迎在评论区交流。