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)，插入后判断是否需再分裂
立即学习“C++免费学习笔记（深入）”；
如何验证和进阶
写完后别急着扔掉，用几个小测试确认行为正确：
- 插入 1~10，检查树高是否为2，叶子是否链成 1→2→…→10
- 删除中间键（如删5），观察是否合并或借位（简单版可暂不实现删除，先保插入+查找）
- 执行 range_query(3, 7)，输出应为 (3,v3)(4,v4)(5,v5)(6,v6)(7,v7)
后续可扩展：加 std::shared_ptr 管理节点生命周期、支持自定义比较器、模拟磁盘块（用 vector
基本上就这些。不复杂但容易忽略的是：叶子链表必须严格有序且双向可遍历（单向够用），以及分裂时“上提键”永远来自原节点，不是新构造——这是保持B+树语义的关键。
