深入理解B树与B+树（C语言实现及数据库索引结构对比详解）

一、什么是B树？

B树是一种自平衡的多路搜索树，由Rudolf Bayer和Ed McCreight于1972年提出。它的主要特点包括：

• 每个节点可以包含多个关键字（key）和多个子节点；
• 所有叶子节点位于同一层；
• 关键字在节点内有序排列；
• 非叶子节点既存储关键字也存储数据（或指针）。

例如，一个阶数为3的B树（即每个节点最多有3个子节点），其结构如下：

// B树节点结构（简化版）typedef struct BTreeNode {    int *keys;          // 关键字数组    void **data;        // 数据指针（可选）    struct BTreeNode **children; // 子节点指针    int keyCount;       // 当前关键字数量    bool isLeaf;        // 是否为叶子节点} BTreeNode;

二、什么是B+树？

B+树是B树的一种变体，由B树演化而来，主要用于数据库和文件系统的索引。它的核心特点是：

• 所有数据只存储在叶子节点中；
• 非叶子节点仅作为索引，不存储实际数据；
• 叶子节点通过指针连接成一个有序链表，便于范围查询。

B+树的这种设计使其在范围查询和顺序访问方面表现更优。

// B+树节点结构（简化版）typedef struct BPlusNode {    int *keys;                     // 关键字数组    union {        struct BPlusNode **children; // 非叶子节点：子节点指针        void **data;               // 叶子节点：实际数据指针    } ptr;    struct BPlusNode *next;        // 叶子节点的下一个节点（用于链表）    int keyCount;    bool isLeaf;} BPlusNode;

三、B树 vs B+树：关键区别

四、为什么数据库偏爱B+树？

现代关系型数据库（如MySQL、PostgreSQL）普遍采用B+树作为索引结构，原因如下：

1. 更高的扇出（Fan-out）：由于非叶子节点不存数据，可以容纳更多关键字，从而减少树的高度，降低磁盘I/O次数。
2. 高效的范围查询：叶子节点链表结构使得 BETWEEN、ORDER BY 等操作非常高效。
3. 稳定的查询性能：所有查询最终都落到叶子节点，路径长度一致，性能可预测。

五、总结

通过本文，我们了解了B树和B+树的基本结构、C语言实现思路以及它们在数据库索引结构中的应用差异。虽然两者都是高效的多路搜索树，但B+树凭借其对范围查询和磁盘I/O的优化，成为现代数据库系统的首选。

如果你正在学习数据库原理或准备面试，掌握B树与B+树的区别是必不可少的。希望这篇教程能帮助你打下坚实基础！

关键词回顾：B树、B+树、C语言实现、数据库索引结构。