B树（B-Tree）是一种自平衡的树数据结构，它维护着数据的有序性，并允许搜索、顺序访问、插入、删除等操作都在对数时间内完成。B树广泛用于数据库和操作系统的文件系统中。
B树的基本特性
- 根节点：根节点至少有两个子节点（除非它是叶子节点）。
- 内部节点：每个内部节点包含的关键字（或称“键”）数量m满足⌈m/2⌉ - 1 ≤ n ≤ m - 1，其中n是节点中关键字的数量，m是节点的最大容量（对于所有节点相同）。
- 叶子节点：所有叶子节点都在同一层上，并且不带信息（或带有指向数据记录的指针），也可以包含关键字信息。
- 分裂与合并：当节点中的关键字数量超过m-1时，该节点分裂成两个节点；当节点中的关键字数量少于⌈m/2⌉-1时，可能通过与其兄弟节点合并来避免这种情况。
- 关键字排序：节点内的关键字按升序排列，使得每个关键字都是其左子树所有值的最大值，也是其右子树所有值的最小值（对于非叶子节点）。
B树的C语言实现概述
这里我们不会完整地实现一个B树，但会展示一些关键部分，如节点结构定义、插入和分裂的简化逻辑。
节点结构定义
#include <stdio.h>
#include <stdlib.h> #define MAX_KEYS 4 // 假设每个节点的最大关键字数量为4 typedef struct BTreeNode { int keys[MAX_KEYS]; // 存储关键字 int numKeys; // 当前节点中关键字的数量 struct BTreeNode *children[MAX_KEYS + 1]; // 子节点指针数组，比关键字数多一个 struct BTreeNode *parent; // 父节点指针 int isLeaf; // 标记是否为叶子节点
} BTreeNode; // 初始化节点
BTreeNode* createNode(int isLeaf) { BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode)); node->numKeys = 0; node->parent = NULL; node->isLeaf = isLeaf; for (int i = 0; i <= MAX_KEYS; i++) { node->children[i] = NULL; } return node;
}
插入操作（简化版）
插入操作涉及在树中找到合适的位置插入新关键字，并在必要时分裂节点。这里只提供一个概念性的伪代码：
// 假设已有函数insertNonFull，用于向非满节点中插入关键字
void insert(BTreeNode* root, int key) { if (root == NULL) { // 创建新的根节点 root = createNode(1); // 假设根节点总是叶子 root->keys[0] = key; root->numKeys = 1; } else { // 找到插入的位置 BTreeNode* node = findLeaf(root, key); // 假设有findLeaf函数 // 插入到叶子节点 if (node->numKeys < MAX_KEYS) { insertNonFull(node, key); } else { // 节点已满，需要分裂 splitChild(node, findInsertPos(node->keys, node->numKeys, key)); // 递归向上调整父节点 // 可能需要再次分裂父节点 } }
}
注意：上述代码是高度简化的，并未实现findLeaf、insertNonFull、findInsertPos、splitChild等函数，这些函数是实现B树的关键。
结论
B树的实现涉及复杂的逻辑和多种情况的处理，特别是节点的分裂和合并。在实际应用中，你可能需要查阅更多的资料或使用现成的库来处理这些复杂的数据结构。上述代码和解释旨在提供一个关于B树基本概念和实现的起点。
