C++如何实现一个B+树_C++数据库索引中常用的高效磁盘查找数据结构

B+树通过将数据存储在叶子节点并用内部节点导航，实现高效磁盘查找与范围查询。其特点包括所有叶子同层、叶节点链式连接、高扇出减少树高，插入时分裂节点并向上调整以维持平衡，适用于数据库索引如InnoDB和SQLite。

在C++中实现一个B+树，核心目标是构建一种适合磁盘存储和高效查找的数据结构，尤其适用于数据库索引。B+树通过减少树的高度、提高分支因子，使每次查找涉及的磁盘I/O尽可能少，从而提升性能。

理解B+树的关键特性

B+树是一种多路平衡搜索树，与B树相比，它将所有数据记录存储在叶子节点中，内部节点仅用于导航。这一设计让查找更稳定，且支持范围查询。关键特点包括：

• 所有叶子节点在同一层：保证查找时间一致。
• 叶子节点通过指针连接成链表：方便范围扫描（如 SELECT * FROM t WHERE id BETWEEN 10 AND 20）。
• 节点满时分裂，空时合并：维持树的平衡。
• 高扇出（high fan-out）：每个节点可包含多个键值，减少树的高度。

定义节点结构与基本类框架

先定义节点类型。区分内部节点和叶子节点，因为它们的功能不同。

// 基本类型定义 const int ORDER = 4; // B+树的阶数，即最大子节点数

struct Record { int key; // 可以是行偏移、文件地址或其他数据指针 long data_ptr; };

// 节点基类 class Node { public: bool is_leaf; int num_keys; int parent; std::vector keys;

Node(bool leaf) : is_leaf(leaf), num_keys(0), parent(-1) {}
virtual ~Node() = default;

};

立即学习“C++免费学习笔记（深入）”；

class LeafNode : public Node { public: std::vector records; int next_leaf; // 指向下一个叶子节点，形成链表

LeafNode() : Node(true), next_leaf(-1) {
    records.reserve(ORDER);
    keys.reserve(ORDER);
}

};

立即学习“C++免费学习笔记（深入）”；

class InternalNode : public Node { public: std::vector children; // 子节点在磁盘或内存池中的索引

InternalNode() : Node(false) {
    children.reserve(ORDER + 1);
    keys.reserve(ORDER);
}

};

实际系统中，这些节点可能需要序列化到磁盘，因此常使用固定大小的块（如4KB），并用缓冲区管理器加载。

实现查找操作

从根节点开始，递归向下查找直到叶子节点。

艺映AI

艺映AI - 免费AI视频创作工具

下载

LeafNode BPlusTree::find_leaf(int key) { int node_idx = root; while (true) { auto node = pool.get(node_idx); if (node->is_leaf) { return static_cast>(node); }

    auto internal = static_cast(node);
    int child_idx = 0;
    for (; child_idx < internal->num_keys; ++child_idx) {
        if (key < internal->keys[child_idx]) break;
    }
    node_idx = internal->children[child_idx];
}

}

Record BPlusTree::search(int key) { LeafNode leaf = find_leaf(key); for (auto& rec : leaf->records) { if (rec.key == key) return &rec; } return nullptr; // 未找到 }

这个过程类似于二分查找，但每一步访问一个磁盘块，在数据库中通常由缓冲池缓存热点节点。

插入与分裂机制

插入需保持B+树的平衡。若节点满了，则进行分裂。

void BPlusTree::insert(int key, long data_ptr) { LeafNode* leaf = find_leaf(key);

// 插入有序位置
int pos = 0;
while (pos < leaf->num_keys && leaf->keys[pos] < key) pos++;

leaf->keys.insert(leaf->keys.begin() + pos, key);
leaf->records.insert(leaf->records.begin() + pos, Record{key, data_ptr});
leaf->num_keys++;

if (leaf->num_keys >= ORDER) {
    split_leaf(leaf);
}

}

void BPlusTree::split_leaf(LeafNode leaf) { int mid = ORDER / 2; LeafNode new_leaf = new LeafNode(); new_leaf->next_leaf = leaf->next_leaf; leaf->next_leaf = pool.add(new_leaf); // 加入节点池

// 拆分后半部分
for (int i = mid; i < ORDER; ++i) {
    new_leaf->keys.push_back(leaf->keys[i]);
    new_leaf->records.push_back(leaf->records[i]);
    new_leaf->num_keys++;
}

leaf->keys.resize(mid);
leaf->records.resize(mid);
leaf->num_keys = mid;

// 更新父节点
update_parent(leaf, new_leaf, new_leaf->keys[0]);

}

内部节点的分裂逻辑类似，只是处理的是子指针和分隔键。分裂后需向上调整父节点，必要时创建新的根节点。

优化与工程考虑

真实数据库中的B+树实现远比上述复杂，需考虑以下几点：

• 缓冲池管理：不是直接操作内存对象，而是通过页号访问磁盘页，由缓冲区决定是否加载。
• 锁机制：并发插入/删除时需要加锁（如latch coupling）防止竞争。
• 日志与持久化：确保崩溃恢复时不丢数据。
• 键值可变长支持：实际中key可能是字符串或复合字段。
• 压缩与空间回收：删除后标记空闲空间供复用。

像SQLite、MySQL的InnoDB都基于B+树实现主键索引。InnoDB使用聚集索引，数据行就存在叶子节点中；二级索引则存主键值。

基本上就这些。实现一个基础B+树不复杂，但要做成生产级数据库组件，需要大量细节打磨。掌握其原理对理解数据库底层至关重要。