B树通过多路平衡搜索树结构实现高效插入、查找与遍历，适用于内外存数据管理。其核心在于节点分裂与递归插入，保持所有叶子节点同层，确保操作时间复杂度为O(log N)。
实现一个B树的关键在于理解它的结构特点：多路搜索树，每个节点可以有多个子节点，且保持数据有序。B树天然平衡，适用于磁盘等外部存储场景，但也能在内存中高效使用。下面介绍C++中B树的基本实现过程。
1. B树的定义与性质
B树满足以下性质：
每个节点最多有
M-1
个关键字（M是阶数）
除根节点外，每个节点至少有
⌈M/2⌉ - 1
个关键字
根节点至少有一个关键字（如果非空）
所有叶子节点在同一层
节点中的关键字从左到右递增
排列
，子树的关键字落在对应区间内
通常选择M为偶数，比如4或5，便于分裂操作处理。
2. 节点结构设计
每个节点包含关键字数组、子节点指针数组以及当前关键字数量。以下是基本结构定义：
立即学习
“
C++免费学习笔记（深入）
”；
```cpp
template
struct BTreeNode {
bool isLeaf; // 是否为叶子节点
int n; // 当前关键字数量
T keys[M - 1]; // 关键字数组
BTreeNode* children[M]; // 子节点指针};C函数速查手册（CHM版）C函数速查手册（CHM版）下载4. 插入操作实现插入时要保证节点不满。若满，则先分裂再插入。核心是分裂和递归插入逻辑：```cpp
templatevoid BTree::splitChild(BTreeNode* parent, int idx) {
auto fullNode = parent->children[idx];
auto newNode = new BTreeNode();
newNode->isLeaf = fullNode->isLeaf;
newNode->n = (M - 1) / 2;}template
void BTree::insertNonFull(BTreeNode*node, const T& key) {
int i = node->n - 1;
if (node->isLeaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
--i;
}
node->keys[i + 1] = key;
node->n++;
} else {
while (i >= 0 && key < node->keys[i]) --i;
++i;
if (node->children[i]->n == M - 1) {
splitChild(node, i);
if (key > node->keys[i]) ++i;
}
insertNonFull(node->children[i], key);
}
}template
void BTree::insert(const T& key) {
if (root == nullptr) {
root = new BTreeNode();
root->keys[0] = key;
root->n = 1;
return;
}}6. 使用示例测试代码：```cpp
int main() {
BTreebtree; // 阶数为3的B树（2-3树）}
BTreeNode() : isLeaf(true), n(0) {
for (int i = 0; i < M; ++i) {
children[i] = nullptr;
}
}
3. B树类框架
封装插入、查找、分裂等操作：
```cpp
template
class BTree {
private:
BTreeNode* root;
void splitChild(BTreeNode* parent, int idx);
void insertNonFull(BTreeNode* node, const T& key);
void traverseNode(BTreeNode* node);
BTreeNode* search(BTreeNode* node, const T& key);
public:
BTree();
void insert(const T& key);
void traverse();
BTreeNode* search(const T& key);
}; // 拷贝后半部分关键字
for (int i = 0; i < newNode->n; ++i) {
newNode->keys[i] = fullNode->keys[(M + 1) / 2 + i];
}
if (!fullNode->isLeaf) {
for (int i = 0; i <= newNode->n; ++i) {
newNode->children[i] = fullNode->children[(M + 1) / 2 + i];
}
}
// 中间关键字上移
for (int i = parent->n; i > idx; --i) {
parent->children[i + 1] = parent->children[i];
}
parent->children[idx + 1] = newNode;
for (int i = parent->n - 1; i >= idx; --i) {
parent->keys[i + 1] = parent->keys[i];
}
parent->keys[idx] = fullNode->keys[(M - 1) / 2];
parent->n++;
fullNode->n = (M - 1) / 2;if (root->n == M - 1) {
auto newRoot = new BTreeNode();
newRoot->isLeaf = false;
newRoot->children[0] = root;
splitChild(newRoot, 0);
root = newRoot;
}
insertNonFull(root, key);
5. 遍历与查找
中序遍历输出所有元素，查找类似二叉搜索树：
```cpp
template
void BTree::traverseNode(BTreeNode* node) {
if (node) {
int i = 0;
for (; i < node->n; ++i) {
if (!node->isLeaf) {
traverseNode(node->children[i]);
}
std::cout << node->keys[i] << " ";
}
if (!node->isLeaf) {
traverseNode(node->children[i]);
}
}
}
template
void BTree::traverse() {
traverseNode(root);
std::cout << std::endl;
}
template
BTreeNode* BTree::search(BTreeNode* node, const T& key) {
int i = 0;
while (i < node->n && key > node->keys[i]) ++i;
if (i < node->n && key == node->keys[i]) return node;
if (node->isLeaf) return nullptr;
return search(node->children[i], key);
}
template
BTreeNode* BTree::search(const T& key) {
return root ? search(root, key) : nullptr;
} btree.insert(10);
btree.insert(20);
btree.insert(5);
btree.insert(6);
btree.insert(12);
btree.insert(30);
std::cout << "Traverse: ";
btree.traverse(); // 输出: 5 6 10 12 20 30
auto node = btree.search(12);
if (node) {
std::cout << "Found 12\n";
}
return 0;
基本上就这些。B树通过分裂维持平衡，插入复杂度为O(log N)，适合大规模有序数据管理。实现时注意边界条件和指针管理，避免内存泄漏。