深入理解B+树（C语言从零实现B+树数据结构完整教程）

为什么选择C语言实现B+树？

C语言提供了对内存的精细控制，非常适合实现底层数据结构。通过手动管理内存，我们可以更清晰地理解B+树的内部机制。此外，C语言实现的B+树可被集成到高性能系统（如数据库引擎）中。

B+树的基本定义

我们首先定义B+树的阶数（order）。假设阶数为 m，则：

• 根节点至少有2个子节点（除非是叶子）；
• 其他内部节点至少有 ⌈m/2⌉ 个子节点；
• 每个节点最多有 m 个子节点；
• 叶子节点包含实际数据，并按顺序链接。

C语言结构体定义

我们先定义两个结构体：一个用于内部节点，一个用于叶子节点。

#define ORDER 4  // B+树的阶数// 叶子节点结构typedef struct LeafNode {    int *keys;                // 关键字数组    void **pointers;          // 数据指针数组    struct LeafNode *next;    // 指向下一个叶子节点    int num_keys;             // 当前关键字数量    bool is_leaf;             // 标记是否为叶子} LeafNode;// 内部节点结构（也可统一用一个结构，这里为了清晰分开）typedef struct InternalNode {    int *keys;                     // 关键字数组    void **pointers;               // 子节点指针数组    int num_keys;                  // 当前关键字数量    bool is_leaf;                  // false} InternalNode;// 统一节点类型（实际工程中常用）typedef struct Node {    int *keys;    void **pointers;    struct Node *parent;    bool is_leaf;    int num_keys;    struct Node *next;  // 仅叶子节点使用} Node;

创建新节点

下面是一个创建新节点的函数：

Node* make_node() {    Node* new_node = (Node*)malloc(sizeof(Node));    if (new_node == NULL) {        fprintf(stderr, "内存分配失败\n");        exit(EXIT_FAILURE);    }    new_node->keys = (int*)calloc(ORDER - 1, sizeof(int));    new_node->pointers = (void**)calloc(ORDER, sizeof(void*));    new_node->is_leaf = false;    new_node->num_keys = 0;    new_node->parent = NULL;    new_node->next = NULL;    return new_node;}Node* make_leaf() {    Node* leaf = make_node();    leaf->is_leaf = true;    return leaf;}

插入操作的核心逻辑

B+树插入的关键在于节点分裂。当一个节点的关键字数量超过上限（ORDER - 1）时，需要将其分裂为两个节点，并将中间关键字上推到父节点。

以下是插入主函数的简化框架：

void insert(Node** root, int key, void* value) {    Node* leaf = find_leaf(*root, key);    if (leaf != NULL && contains_key(leaf, key)) {        // 处理重复键（根据需求决定是否覆盖）        return;    }    insert_into_leaf(leaf, key, value);    if (leaf->num_keys >= ORDER) {        leaf = split_and_insert_leaf(root, leaf);    }}// 辅助函数：在叶子中插入void insert_into_leaf(Node* leaf, int key, void* value) {    int i, insertion_point = 0;    while (insertion_point < leaf->num_keys &&           leaf->keys[insertion_point] < key)        insertion_point++;    for (i = leaf->num_keys; i > insertion_point; i--) {        leaf->keys[i] = leaf->keys[i - 1];        leaf->pointers[i] = leaf->pointers[i - 1];    }    leaf->keys[insertion_point] = key;    leaf->pointers[insertion_point] = value;    leaf->num_keys++;}

测试与验证

完成基本结构后，你可以编写一个简单的测试程序，插入一系列整数并遍历叶子链表，验证B+树是否正确构建。

总结

通过本教程，你已经掌握了如何用C语言实现B+树的基本框架。虽然完整的B+树还涉及删除、查找优化、磁盘I/O模拟等高级功能，但理解插入和分裂机制是关键的第一步。

希望这篇B+树教程能帮助你深入理解这一经典数据结构。继续练习，尝试扩展功能，比如支持字符串键或持久化到文件！

记住，掌握B+树数据结构不仅是面试加分项，更是构建高性能系统的基础。