c++如何实现一个简单的B+树_c++数据库索引原理与实现【数据结构】-C++-PHP中文网

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

尼克

发布： 2025-12-21 15:24:07

原创

337人浏览过

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

c++如何实现一个简单的b+树_c++数据库索引原理与实现【数据结构】

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

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

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

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

节点抽象：定义基类 Node，派生 LeafNode 和 InnerNode；LeafNode 存 vector<pair v>></pair> 和指向下一个叶子的 LeafNode*；InnerNode 存 vector<k></k> 和 vector<node></node>
阶数与分裂规则：设最小度数 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<pair<int, int>> 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});
    }
};
<p>pair<int, LeafNode<em>> LeafNode::split() {
int mid = kv_pairs.size() / 2;
int pivot_key = kv_pairs[mid].first;
LeafNode</em> 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};
}</p><p>// InnerNode::insert_and_split 接收 (pivot_key, new_child)，插入后判断是否需再分裂</p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/6e7abc4abb9f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">C++免费学习笔记（深入）</a>”；</p>
                    <div class="aritcle_card">
                        <a class="aritcle_card_img" href="/ai/1548">
                            <img src="https://img.php.cn/upload/ai_manual/000/000/000/175680242019387.jpg" alt="Block Survey">
                        </a>
                        <div class="aritcle_card_info">
                            <a href="/ai/1548">Block Survey</a>
                            <p>BlockSurvey是一个保护隐私和数据安全调查工具，可以让你使用AI来创建调查表单。</p>
                            <div class="">
                                <img src="/static/images/card_xiazai.png" alt="Block Survey">
                                <span>71</span>
                            </div>
                        </div>
                        <a href="/ai/1548" class="aritcle_card_btn">
                            <span>查看详情</span>
                            <img src="/static/images/cardxiayige-3.png" alt="Block Survey">
                        </a>
                    </div>

登录后复制