深入理解B树：C语言实现高效磁盘索引结构（从零开始掌握B树数据结构）

B树的关键特性

• 阶数（Order）：设为 m，则每个节点最多有 m 个子节点，最多包含 m-1 个键。
• 最小度数（t）：除根节点外，每个内部节点至少有 t 个子节点（即至少 t-1 个键）。
• 所有叶子节点位于同一层，保证了查找、插入、删除的时间复杂度均为 O(log n)。
• 数据有序存储，支持高效的范围查询。

为什么选择B树？

在磁盘读写场景中，每次I/O操作代价很高。B树通过高效磁盘索引结构的设计，使得一次磁盘读取可以加载一个完整节点（通常是一个磁盘页），从而大幅减少I/O次数。这也是为什么MySQL、PostgreSQL等数据库底层都采用B+树（B树的变种）作为索引结构。

C语言实现B树的核心步骤

下面我们用C语言实现一个简化版的B树（以最小度数 t=2 为例，即2-3-4树）。我们将实现插入操作，这是B树中最复杂的部分。

1. 定义B树节点结构

#define T 2  // 最小度数，T=2 表示每个节点至少1个键，最多3个键typedef struct BTreeNode {    int *keys;           // 键数组    struct BTreeNode **children; // 子节点指针数组    int key_count;       // 当前键的数量    bool is_leaf;        // 是否为叶子节点} BTreeNode;

2. 创建新节点

BTreeNode* create_node() {    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));    node->keys = (int*)malloc((2 * T - 1) * sizeof(int));    node->children = (BTreeNode**)malloc(2 * T * sizeof(BTreeNode*));    node->key_count = 0;    node->is_leaf = true;    return node;}

3. 分裂满节点（Split Child）

当一个节点已满（包含 2T-1 个键）时，需要分裂成两个节点，并将中间键提升到父节点。

void split_child(BTreeNode* parent, int index) {    BTreeNode* new_node = create_node();    BTreeNode* full_child = parent->children[index];    new_node->is_leaf = full_child->is_leaf;    new_node->key_count = T - 1;    // 将后半部分键复制到新节点    for (int i = 0; i < T - 1; i++) {        new_node->keys[i] = full_child->keys[i + T];    }    // 如果不是叶子，还要复制子节点指针    if (!full_child->is_leaf) {        for (int i = 0; i < T; i++) {            new_node->children[i] = full_child->children[i + T];        }    }    full_child->key_count = T - 1;    // 为新节点腾出空间    for (int i = parent->key_count; i >= index + 1; i--) {        parent->children[i + 1] = parent->children[i];    }    parent->children[index + 1] = new_node;    // 将中间键提升到父节点    for (int i = parent->key_count; i >= index; i--) {        parent->keys[i + 1] = parent->keys[i];    }    parent->keys[index] = full_child->keys[T - 1];    parent->key_count++;}

4. 插入键值

插入总是发生在叶子节点。如果根节点满了，先创建新根再分裂。

void insert_non_full(BTreeNode* node, int key);void btree_insert(BTreeNode** root, int key) {    BTreeNode* r = *root;    if (r->key_count == 2 * T - 1) {        BTreeNode* new_root = create_node();        new_root->is_leaf = false;        new_root->children[0] = r;        split_child(new_root, 0);        insert_non_full(new_root, key);        *root = new_root;    } else {        insert_non_full(r, key);    }}void insert_non_full(BTreeNode* node, int key) {    int i = node->key_count - 1;    if (node->is_leaf) {        while (i >= 0 && node->keys[i] > key) {            node->keys[i + 1] = node->keys[i];            i--;        }        node->keys[i + 1] = key;        node->key_count++;    } else {        while (i >= 0 && node->keys[i] > key) {            i--;        }        i++;        if (node->children[i]->key_count == 2 * T - 1) {            split_child(node, i);            if (node->keys[i] < key) i++;        }        insert_non_full(node->children[i], key);    }}

总结

通过本教程，你已经掌握了C语言平衡树中B树的基本原理和插入操作的实现。虽然代码看起来有些复杂，但只要理解“分裂”和“自底向上调整”的思想，就能逐步掌握。B树是数据库索引的基石，深入理解它对提升系统设计能力大有裨益。

后续你可以尝试实现查找、删除操作，或者将B树扩展为B+树（更适合范围查询）。记住，实践是最好的老师——动手写一遍代码，你会收获更多！