B树和B+树是两种重要的多路平衡搜索树结构，广泛应用于数据库和文件系统领域。下面我们将从C语言实现的角度深入解析它们的原理和实现细节。
一、B树解析
1. 结构定义
#define M 4 // B树的阶数（每个节点最多有M-1个键）typedef struct BTreeNode {int keys[M-1]; // 关键字数组struct BTreeNode* children[M]; // 子节点指针数组int key_num; // 当前节点关键字数量bool is_leaf; // 是否为叶子节点
} BTree;2. 核心特性
- 每个节点最多包含M-1个键，至少⌈M/2⌉-1个键（根节点除外）
- 所有叶子节点位于同一层次
- 插入删除操作通过分裂和合并保持平衡
3. 插入操作流程
void BTreeInsert(BTree** root, int key) {BTree* node = *root;// 根节点已满时进行分裂if (node->key_num == M-1) {BTree* new_root = createNode();new_root->children[0] = node;splitChild(new_root, 0);*root = new_root;}insertNonFull(*root, key);
}4. 节点分裂示例
void splitChild(BTree* parent, int index) {BTree* child = parent->children[index];BTree* new_node = createNode();// 新节点获取后半部分键for (int i = 0; i < M/2-1; i++) {new_node->keys[i] = child->keys[i + M/2];}// 中间键提升到父节点parent->keys[index] = child->keys[M/2-1];// 调整父子关系parent->children[index+1] = new_node;parent->key_num++;
}5. 查找算法
BTree* BTreeSearch(BTree* node, int key) {int i = 0;while (i < node->key_num && key > node->keys[i])i++;if (i < node->key_num && key == node->keys[i])return node;if (node->is_leaf)return NULL;return BTreeSearch(node->children[i], key);
}二、B+树解析
1. 结构定义
#define M 4 // 阶数typedef struct BPlusTreeNode {int keys[M-1];union {struct BPlusTreeNode* children[M]; // 内部节点使用struct {void** data[M]; // 叶子节点数据指针struct BPlusTreeNode* next; // 叶子节点链表};};int key_num;bool is_leaf;
} BPlusTree;2. 核心特性
- 所有数据存储在叶子节点，内部节点仅作索引
- 叶子节点形成有序双向链表
- 内部节点的键值等于右子树的最小值
3. 与B树的对比
| 特征 | B树 | B+树 |
|---|---|---|
| 数据存储位置 | 所有节点 | 仅叶子节点 |
| 叶子节点链接 | 无 | 双向链表 |
| 查询稳定性 | 不稳定 | 稳定 |
| 范围查询效率 | 较低 | 极高 |
| 空间利用率 | 较低 | 较高 |
4. 插入算法特点
void BPlusTreeInsert(BPlusTree** root, int key, void* data) {// 查找插入位置BPlusTree* leaf = findLeaf(*root, key);// 叶子节点分裂逻辑if (leaf->key_num == M-1) {BPlusTree* new_leaf = splitLeaf(leaf);insertIntoParent(root, leaf, new_leaf->keys[0], new_leaf);}// 插入数据到叶子节点insertIntoLeaf(leaf, key, data);
}5. 范围查询优势
void rangeQuery(BPlusTree* root, int start, int end) {BPlusTree* leaf = findLeaf(root, start);while (leaf != NULL) {for (int i = 0; i < leaf->key_num; i++) {if (leaf->keys[i] >= start && leaf->keys[i] <= end) {// 处理数据processData(leaf->data[i]);}if (leaf->keys[i] > end) return;}leaf = leaf->next;}
}三、性能对比分析
-
查询效率
- B树：最好情况O(1)（在根节点命中）
- B+树：稳定O(log N)，必须到达叶子节点
-
空间利用
- B+树的内部节点更紧凑，相同内存可存储更多索引
-
适用场景
- B树：随机访问较多，查询深度不敏感的场景
- B+树：范围查询频繁，需要稳定查询性能的系统
四、实现注意事项
-
节点设计优化
// 内存对齐优化 typedef struct {int keys[M-1];void* pointers[M];unsigned char key_num;bool is_leaf;uint16_t flags; // 用于扩展标记 } __attribute__((aligned(64))) CacheOptimizedNode; -
并发控制
// 使用读写锁保护节点 typedef struct {pthread_rwlock_t lock;BPlusTreeNode* node; } ConcurrentNode; -
持久化存储
// 序列化节点结构 #pragma pack(push, 1) typedef struct {uint32_t magic_number;uint16_t key_count;uint8_t node_type;int keys[M-1];uint64_t children[M]; } DiskNode; #pragma pack(pop)