c++如何实现一个简单的B树_c++数据库与文件系统核心数据结构

新闻中心 NEWS CENTER

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

c++如何实现一个简单的B树_c++数据库与文件系统核心数据结构

2025-11-29

浏览次数：次

返回列表

B树是一种自平衡多路搜索树，用于数据库和文件系统中高效管理磁盘I/O。1. 每个节点可含多个关键字和子节点指针，根节点至少两子节点（非叶子），所有叶子同层。2. 节点关键字数在t-1到2t-1之间，内部节点最多2t子节点，t为最小度数。3. 使用模板类实现节点结构，固定数组模拟磁盘块，支持泛型键值。4. 插入时通过splitChild分裂满节点，保证路径上节点不满，维持平衡性。5. 查找采用二分变体定位，递归下降至叶子。6. B树低高度减少磁盘访问，适用于MySQL索引、NTFS/ext4文件系统等场景，节点大小常匹配4KB扇区以优化性能。

c++如何实现一个简单的b树_c++数据库与文件系统核心数据结构

在C++中实现一个简单的B树，可以作为数据库或文件系统中核心数据结构的基础。B树因其高效的磁盘读写性能被广泛用于数据库索引和文件系统的组织。下面介绍如何用C++构建一个基本的、可运行的B树，并说明其关键设计点。

什么是B树

B树是一种自平衡的多路搜索树，每个节点可以包含多个关键字和多个子节点指针。它满足以下性质：

根节点至少有两个子节点（除非是叶子）
所有叶子节点在同一层
除根节点外，每个节点的关键字数量在 t-1 到 2t-1 之间（t 是最小度数）
内部节点最多有 2t 个子节点

这种结构减少了树的高度，适合磁盘I/O频繁的场景，比如数据库中的索引管理。

定义B树节点结构

先定义一个B树节点类模板，支持泛型键值类型（如int, string等）。

template <typename T, int t>
class BTreeNode {
public:
    bool isLeaf;
    int n; // 当前关键字数量
    T keys[2 * t - 1]; // 存储关键字
    BTreeNode* children[2 * t]; // 子节点指针
<pre class='brush:php;toolbar:false;'>BTreeNode() : isLeaf(true), n(0) {
    for (int i = 0; i < 2 * t; ++i) {
        children[i] = nullptr;
    }
}

};

这里使用固定大小数组模拟磁盘块限制，符合实际存储系统的设计思路。t 是最小度数，控制节点的分裂与合并阈值。

实现B树的基本操作

B树的核心操作包括插入、查找、分裂节点等。我们以插入为例展示流程。

1. 查找

标准二分搜索变体，在节点内找到合适位置继续向下遍历。

bool search(T key, BTreeNode<T, t>* node) {
    if (!node) return false;
<pre class='brush:php;toolbar:false;'>int i = 0;
while (i < node->n && key > node->keys[i])
    ++i;

if (i < node->n && key == node->keys[i])
    return true;

if (node->isLeaf)
    return false;

return search(key, node->children[i]);

}

2. 分裂子节点

黄城网络办公系统

具有功能全面实用、安全性稳定性高、易操作、管理维护简单的特点，采用独创的智能型技术，web服务器、数据库和应用程序全部自动傻瓜安装配置，用户可在一分钟内自行安装完毕，无需专业人员即可自行维护，B/S结构，适用于Intranet/Internet应用，客户端只需浏览器便可连接办公系统，无论出差旅行，还是居家办公，工作都能得心应手，实现无地域限制的全球办公，具有邮件管理、业务管理、网络硬盘、智能工作流

0 查看详情黄城网络办公系统

当节点满时（n == 2t-1），需要将其中一半元素移到新节点。

void splitChild(BTreeNode<T, t>* parent, int i) {
    BTreeNode<T, t>* fullNode = parent->children[i];
    BTreeNode<T, t>* newNode = new BTreeNode<T, t>;
    newNode->isLeaf = fullNode->isLeaf;
    newNode->n = t - 1;
<pre class='brush:php;toolbar:false;'>// 拷贝后半部分关键字
for (int j = 0; j < t - 1; ++j)
    newNode->keys[j] = fullNode->keys[j + t];

if (!fullNode->isLeaf) {
    // 如果不是叶子，复制子指针
    for (int j = 0; j < t; ++j)
        newNode->children[j] = fullNode->children[j + t];
}

fullNode->n = t - 1;

// 将父节点中i之后的子节点后移
for (int j = parent->n; j >= i + 1; --j)
    parent->children[j + 1] = parent->children[j];

parent->children[i + 1] = newNode;

for (int j = parent->n; j >= i + 1; --j)
    parent->keys[j] = parent->keys[j - 1];

parent->keys[i] = fullNode->keys[t - 1];
parent->n++;

}

3. 插入非满节点

递归下降过程中确保路径上的节点不满。

void insertNonFull(BTreeNode<T, t>* node, T key) {
    int i = node->n - 1;
    if (node->isLeaf) {
        // 叶子节点，直接插入并排序
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            --i;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {
        // 找到应插入的子树
        while (i >= 0 && key < node->keys[i])
            --i;
        i++;
<pre class='brush:php;toolbar:false;'>    if (node->children[i]->n == 2 * t - 1) {
        splitChild(node, i);
        if (key > node->keys[i])
            ++i;
    }
    insertNonFull(node->children[i], key);
}

}

4. 主插入接口

void insert(T key) {
    if (!root) {
        root = new BTreeNode<T, t>;
        root->keys[0] = key;
        root->n = 1;
        return;
    }
<pre class='brush:php;toolbar:false;'>if (root->n == 2 * t - 1) {
    BTreeNode<T, t>* newRoot = new BTreeNode<T, t>;
    newRoot->isLeaf = false;
    newRoot->children[0] = root;
    splitChild(newRoot, 0);
    insertNonFull(newRoot, key);
    root = newRoot;
} else {
    insertNonFull(root, key);
}

}