c++如何实现一个简单的B+树_c++数据库索引原理与实现【数据结构】_技术教程

B+树是一种所有数据仅存于叶子节点且叶子节点通过指针构成有序链表的平衡多路搜索树；它因减少树高以降低磁盘I/O、支持高效范围查询和顺序遍历，被数据库广泛用作索引结构。

什么是B+树，为什么数据库用它做索引

数据库索引不是随便选的结构，B+树被广泛采用，核心是因为它在磁盘I/O和查询效率之间取得了很好平衡。相比二叉搜索树或红黑树，B+树所有数据都存放在叶子节点，且叶子节点用指针连成有序链表；非叶子节点只存键和子节点指针——这带来两个关键好处：减少树高（降低磁盘读取次数）、支持高效范围查询和顺序遍历。实际中，一个1000万条记录的表，B+树通常只有3~4层，一次查询最多读3~4次磁盘。

简化版B+树设计要点（适合C++初学者实现）

不追求工业级完整（如并发控制、崩溃恢复），先实现一个内存版、单线程、固定阶数（比如阶数m=4）的B+树，聚焦核心逻辑：

节点抽象：定义基类 Node，派生 LeafNode 和 InnerNode；LeafNode 存 vector> 和指向下一个叶子的 LeafNode*；InnerNode 存 vector 和 vector
阶数与分裂规则：设最小度数 t（例如 t=2），则每个节点最多含 2t−1 个键，最少（根除外）含 t−1 个键；插入导致超限时，按中间键分裂，中间键上提至父节点
插入流程：递归查到叶子 → 插入键值对 → 若叶子满（size == 2t），分裂并返回上提键和新右节点 → 父节点递归处理，必要时向上分裂，直到根；若根分裂，新建根，树高+1
查找与范围查询：查找走树到叶子；范围查询 [L, R] 先 find_first ≥ L 的叶子位置，再沿叶子链表向后遍历直到 > R

关键代码片段（C++风格，带注释）

以下为插入核心逻辑示意（省略内存管理与异常处理）：

// 假设 Key=int, Value=int，t=2（即每个节点最多3个键）
struct LeafNode : Node {
    vector> kv_pairs;
    LeafNode* next = nullptr;
    bool is_full() const { return kv_pairs.size() >= 3; }
    void insert_sorted(int k, int v) {
        auto it = lower_bound(kv_pairs.begin(), kv_pairs.end(), make_pair(k, 0));
        kv_pairs.insert(it, {k, v});
    }
};
pair> LeafNode::split() {
int mid = kv_pairs.size() / 2;
int pivot_key = kv_pairs[mid].first;
LeafNode new_right = new LeafNode();
new_right->kv_pairs.assign(kv_pairs.begin() + mid + 1, kv_pairs.end());
kv_pairs.resize(mid);
new_right->next = next;
next = new_right;
return {pivot_key, new_right};
}
// InnerNode::insert_and_split 接收 (pivot_key, new_child)，插入后判断是否需再分裂