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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-12-09

浏览次数：次

返回列表

B树是一种自平衡多路搜索树，满足最小度数t≥2、所有叶子同层等性质，适合磁盘I/O优化；其核心操作包括满则分裂的插入、多路比较的搜索及递归遍历。

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

用 C++ 实现一个简单的 B 树，核心在于理解 B 树的定义：它是一种自平衡的多路搜索树，每个节点可含多个键和子节点，满足最小度数 t（t ≥ 2），所有叶子在同一层，适合磁盘 I/O 优化——这正是数据库索引（如 MySQL 的 InnoDB）底层常用结构的原因。

B 树的基本结构设计

我们以最小度数 t = 2（即每个非根节点至少有 1 个键、最多 3 个键，最多 4 个子节点）为例，定义节点结构：

Node 类：包含键数组 keys[]、子节点指针数组 children[]、键数量 n、是否为叶子 isLeaf
BTree 类：持有一个根节点指针，封装 insert、search、splitChild、insertNonFull 等方法
注意：B 树不直接支持重复键；如需支持，可在 value 中存链表或计数器

插入逻辑的关键步骤

插入必须维持 B 树性质，核心是「满则分裂」：

从根开始向下查找插入位置；若当前节点已满（n == 2*t - 1 == 3），先调用 splitChild 将其分裂为两个 t−1 键的节点，并将中位键上推到父节点
递归进入未满的子树；到达叶子后直接插入排序位置
若根满，插入前先分裂根，树高 +1（这是 B 树保持平衡的关键）

搜索与简单遍历实现

搜索是标准的多路 BST 查找：

在当前节点线性比较键，找到第一个 ≥ key 的位置 i
若 keys[i] == key，返回成功；否则沿 children[i] 继续递归（注意：i 从 0 开始，叶子无子节点需提前判断）
中序遍历可用递归实现：左子树 → 输出键 → 右子树（对每个键间隔做一次）

可运行的极简源码（C++11，无模板，便于理解）

以下为完整可编译的简化版（仅含 insert / search / print）：

Clips AI

自动将长视频或音频内容转换为社交媒体短片

255 查看详情 Clips AI

#include <iostream>
#include <vector>
using namespace std;
<p>const int t = 2; // minimum degree</p><p>struct Node {
vector<int> keys;
vector<Node*> children;
bool isLeaf;
Node() : isLeaf(true) {}
};</p><p>class BTree {
public:
Node* root;
BTree() : root(nullptr) {}</p><pre class="brush:php;toolbar:false;">void insert(int k) {
    if (!root) {
        root = new Node();
        root->keys.push_back(k);
        return;
    }
    if (root->keys.size() == 2*t-1) {
        Node* s = new Node();
        s->children.push_back(root);
        splitChild(s, 0);
        root = s;
    }
    insertNonFull(root, k);
}

void insertNonFull(Node* x, int k) {
    int i = x->keys.size() - 1;
    if (x->isLeaf) {
        x->keys.push_back(0); // placeholder
        while (i >= 0 && x->keys[i] > k) {
            x->keys[i+1] = x->keys[i];
            --i;
        }
        x->keys[i+1] = k;
    } else {
        while (i >= 0 && x->keys[i] > k) --i;
        ++i;
        if (x->children[i]->keys.size() == 2*t-1) {
            splitChild(x, i);
            if (k > x->keys[i]) ++i;
        }
        insertNonFull(x->children[i], k);
    }
}

void splitChild(Node* x, int i) {
    Node* y = x->children[i];
    Node* z = new Node();
    z->isLeaf = y->isLeaf;
    z->keys.assign(y->keys.begin()+t, y->keys.end());
    if (!y->isLeaf)
        z->children.assign(y->children.begin()+t, y->children.end());
    y->keys.resize(t-1);
    if (!y->isLeaf)
        y->children.resize(t);
    x->children.insert(x->children.begin()+i+1, z);
    x->keys.insert(x->keys.begin()+i, y->keys[t-1]);
    y->keys.pop_back();
}

bool search(Node* x, int k) {
    if (!x) return false;
    int i = 0;
    while (i < x->keys.size() && k > x->keys[i]) ++i;
    if (i < x->keys.size() && x->keys[i] == k) return true;
    if (x->isLeaf) return false;
    return search(x->children[i], k);
}

void print(Node* x, int level = 0) {
    if (!x) return;
    cout << "Level " << level << ": ";
    for (int k : x->keys) cout << k << " ";
    cout << "\n";
    if (!x->isLeaf)
        for (Node* c : x->children) print(c, level+1);
}