深入理解B+树（C++语言B+树实现方法详解）

什么是B+树？

B+树是一种自平衡的树数据结构，常用于数据库索引和文件系统。与普通B树不同，B+树的所有数据都存储在叶子节点中，内部节点仅用于索引。此外，叶子节点通过指针连接成链表，便于范围扫描。

B+树具有以下特点：

• 所有叶子节点位于同一层；
• 内部节点不存储实际数据，只存储键值用于导航；
• 叶子节点之间通过双向链表连接；
• 每个节点的关键字数量在 [⌈m/2⌉−1, m−1] 范围内（m为阶数）。

B+树的基本结构设计

我们先定义两个类：Node（节点）和 BPlusTree（B+树主类）。

1. 节点类型

节点分为内部节点（Internal Node）和叶子节点（Leaf Node）。为了简化，我们可以用一个布尔变量 is_leaf 来区分。

struct Node {    bool is_leaf;    std::vector<int> keys;    std::vector<Node*> children;   // 内部节点使用    std::vector<int> values;        // 叶子节点使用（可选）    Node* next;                     // 叶子节点链表指针    Node(bool leaf) : is_leaf(leaf), next(nullptr) {}};

2. B+树主类

class BPlusTree {private:    Node* root;    int order; // 阶数，即每个节点最多有 order 个子节点    void insert_internal(Node* node, int key, Node* child);    void split_leaf(Node* leaf);    void split_internal(Node* internal);    Node* find_leaf(int key);public:    BPlusTree(int ord) : order(ord), root(nullptr) {}    void insert(int key);    bool search(int key);    void print_tree();};

插入操作详解

B+树的插入流程如下：

1. 从根节点开始，找到合适的叶子节点；
2. 将键值插入该叶子节点；
3. 如果叶子节点溢出（关键字数量 ≥ order），则分裂；
4. 若分裂导致父节点溢出，则递归向上处理。

下面是一个简化的插入函数实现：

void BPlusTree::insert(int key) {    if (root == nullptr) {        root = new Node(true);        root->keys.push_back(key);        return;    }    Node* leaf = find_leaf(key);    // 插入到叶子节点（保持有序）    auto it = std::lower_bound(leaf->keys.begin(), leaf->keys.end(), key);    leaf->keys.insert(it, key);    // 检查是否需要分裂    if (leaf->keys.size() >= (size_t)order) {        split_leaf(leaf);    }}

分裂叶子节点时，我们将后一半的键值移到新节点，并将最小的新键值提升到父节点：

void BPlusTree::split_leaf(Node* leaf) {    Node* new_leaf = new Node(true);    int mid = order / 2;    // 将后一半 keys 移动到新叶子    new_leaf->keys.assign(leaf->keys.begin() + mid, leaf->keys.end());    leaf->keys.resize(mid);    // 维护链表    new_leaf->next = leaf->next;    leaf->next = new_leaf;    // 将新叶子的最小 key 插入父节点    int new_key = new_leaf->keys[0];    if (leaf == root) {        // 根节点分裂        Node* new_root = new Node(false);        new_root->keys.push_back(new_key);        new_root->children.push_back(leaf);        new_root->children.push_back(new_leaf);        root = new_root;    } else {        insert_internal(find_parent(root, leaf), new_key, new_leaf);    }}

为什么选择B+树？

在数据库系统中，如MySQL的InnoDB引擎就广泛使用B+树实现索引。原因包括：

• 磁盘I/O优化：B+树高度低，减少磁盘读取次数；
• 范围查询高效：叶子节点链表支持快速顺序遍历；
• 结构稳定：插入/删除不会频繁改变树高。

总结

通过本文，你已经掌握了用C++ B+树的基本实现思路。虽然完整实现涉及更多边界条件处理（如删除、合并节点等），但核心思想就是“保持平衡”和“分裂传播”。建议你在理解后动手编写完整代码，并测试插入、查找功能。

掌握B+树数据结构不仅能提升算法能力，还能帮助你深入理解数据库底层原理。如果你对B+树源码感兴趣，可以在GitHub上搜索开源项目进一步学习。

希望这篇教程对你有所帮助！欢迎继续探索更高级的数据结构。