B树通过多路平衡降低高度以减少磁盘IO，其核心在于节点分裂与合并。在C++中，需定义含关键字数组、子节点指针、最小度数t的节点结构，实现插入时若节点满则分裂，中间键上移，保证树始终平衡，适用于数据库和文件系统索引。
实现一个简单的B树，关键在于理解其自平衡的多路搜索树特性。B树允许节点包含多个键，能有效减少树的高度，常用于文件系统和数据库索引。在C++中，我们可以通过类和递归操作来实现插入、查找和分裂等核心功能。
定义B树节点结构
B树的每个节点包含多个键和对应的子树指针。节点还应记录当前键的数量，并设置最小度数 t，决定节点最少和最多可容纳的键数。
最小度数 t 表示每个节点（除根节点）至少有 t-1 个键，最多有 2t-1 个键。例如 t=2 时，节点最多3个键，即我们常说的 2-3-4 树。以下是一个基本的节点结构定义：
struct BTreeNode {
bool leaf; // 是否为叶子节点
int n; // 当前键的数量
int *keys; // 键数组
BTreeNode **children; // 子节点指针数组
int t; // 最小度数
BTreeNode(int _t, bool _leaf);
void traverse(); // 中序遍历
BTreeNode* search(int k); // 查找键k
void insertNonFull(int k); // 在非满节点插入
void splitChild(int i, BTreeNode *y); // 分裂子节点
};
初始化与构造函数
构造函数负责分配内存并初始化节点属性。每个节点根据最小度数 t 预分配最大空间（2t-1 个键，2t 个子指针）。
立即学习“C++免费学习笔记（深入）”；
BTreeNode::BTreeNode(int _t, bool _leaf) {
t = _t;
leaf = _leaf;
keys = new int[2*t - 1];
children = new BTreeNode*[2*t];
n = 0;
}
根节点初始为空，随着插入操作逐步构建整棵树。
插入操作与节点分裂
插入从根开始。若根满（键数达 2t-1），需创建新根，原根变为子节点，然后调用 insertNonFull。
insertNonFull 的逻辑如下：
- 若当前节点是叶子，直接插入键并保持有序。
- 否则，找到对应子节点，递归插入。
- 若子节点已满，在递归前先分裂（splitChild）。
splitChild 将满节点 y 拆分为两个，中间键上移到父节点：
void BTreeNode::splitChild(int i, BTreeNode *y) {
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t-1; j++)
z->keys[j] = y->keys[j + t];
if (!y->leaf) {
for (int j = 0; j < t; j++)
z->children[j] = y->children[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
children[j + 1] = children[j];
children[i + 1] = z;
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n++;
}
查找与遍历
查找类似于二叉搜索树，但在多键节点中需线性或二分查找定位区间。
BTreeNode* BTreeNode::search(int k) {
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf)
return nullptr;
return children[i]->search(k);
}
遍历则按“左-中-右”顺序递归输出所有键，适合验证树结构。
基本上就这些。实现B树的核心是控制节点容量、递归插入与适时分裂。只要理清分裂时父子节点的数据转移逻辑，就能写出稳定可用的B树结构。不复杂但容易忽略细节，比如内存释放和边界判断。
