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

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

穿越時空

发布： 2025-11-29 16:38:02

原创

929人浏览过

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等）。

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

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. 分裂子节点

Android创建和使用数据库详细指南中文WORD版

每个应用程序都要使用数据，Android应用程序也不例外，Android使用开源的、与操作系统无关的SQL数据库--SQLite，本文介绍的就是如何为你的Android应用程序创建和操作SQLite数据库。数据库支持每个应用程序无论大小的生命线，除非你的应用程序只处理简单的数据，那么就需要一个数据库系统存储你的结构化数据，Android使用SQLite数据库，它是一个开源的、支持多操作系统的SQL数据库，在许多领域广泛使用，如Mozilla FireFox就是使用SQLite来存储配置数据的，iPhon

查看详情

当节点满时（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);
}

登录后复制

}