B树是一种平衡的多分树，每个节点可以包含多个关键字和多个子节点，所有叶子节点位于同一层，能够保持数据有序且查询效率稳定。它的最大特点是通过增大节点的关键字数量，降低树的高度，从而减少磁盘访问次数，因此被广泛应用在数据库索引、文件系统索引等场景中。下面我们用C++实现一个支持插入和查找操作的B树。
B树的核心特性
实现B树前需要先明确它的核心约束，假设B树的阶数为m，即每个节点最多包含m-1个关键字和m个子节点，那么需要满足以下规则：
- 根节点至少包含1个关键字，除非根节点是叶子节点
- 非根节点至少包含ceil(m/2)-1个关键字
- 所有叶子节点位于同一层，且不包含子节点
- 节点内的关键字按升序排列，子节点的关键字范围在相邻两个父节点关键字之间
节点结构设计
我们首先定义B树的节点结构，每个节点需要存储关键字数组、子节点指针数组、当前关键字数量以及是否为叶子节点的标识：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// B树节点模板类，T为关键字类型，默认支持int
template <typename T = int>
class BTreeNode {
public:
// 关键字数组，最多存储m-1个
vector<T> keys;
// 子节点指针数组，最多存储m个
vector<BTreeNode*> children;
// 当前节点的关键字数量
int keyNum;
// 是否为叶子节点
bool isLeaf;
// B树的阶数
int m;
BTreeNode(int order, bool leaf) {
m = order;
isLeaf = leaf;
keyNum = 0;
// 预分配空间，避免频繁扩容
keys.reserve(m);
children.reserve(m + 1);
}
// 在节点中查找关键字的位置，返回第一个大于等于key的索引
int findKey(const T& key) {
int idx = 0;
while (idx < keyNum && keys[idx] < key) {
idx++;
}
return idx;
}
};
B树类的整体定义
接下来定义B树的主体类，包含根节点、阶数，以及插入、查找、分裂等核心方法：
template <typename T = int>
class BTree {
private:
// B树的根节点
BTreeNode<T>* root;
// B树的阶数
int m;
public:
BTree(int order) {
m = order;
root = nullptr;
}
// 析构函数，释放所有节点内存
~BTree() {
destroyTree(root);
}
// 插入关键字
void insert(const T& key);
// 查找关键字，返回是否找到
bool search(const T& key);
// 打印B树结构，用于调试
void printTree();
private:
// 分裂满子节点
void splitChild(BTreeNode<T>* parent, int childIdx);
// 向非满节点插入关键字
void insertNonFull(BTreeNode<T>* node, const T& key);
// 递归查找关键字
bool searchRecursive(BTreeNode<T>* node, const T& key);
// 递归打印树结构
void printRecursive(BTreeNode<T>* node, int level);
// 递归释放节点内存
void destroyTree(BTreeNode<T>* node);
};
核心方法实现
查找操作实现
查找操作从根节点开始，在当前节点的关键字数组中查找目标值，如果找到则返回true；如果当前节点是叶子节点且未找到则返回false；否则根据关键字大小进入对应的子节点继续查找：
template <typename T>
bool BTree<T>::searchRecursive(BTreeNode<T>* node, const T& key) {
if (node == nullptr) {
return false;
}
// 找到第一个大于等于key的关键字索引
int idx = node->findKey(key);
// 如果刚好等于key，说明找到
if (idx < node->keyNum && node->keys[idx] == key) {
return true;
}
// 如果是叶子节点，说明没找到
if (node->isLeaf) {
return false;
}
// 否则进入对应的子节点继续查找
return searchRecursive(node->children[idx], key);
}
template <typename T>
bool BTree<T>::search(const T& key) {
return searchRecursive(root, key);
}
节点分裂操作
当插入关键字导致节点关键字数量达到m-1时，需要对该节点进行分裂。分裂时取中间的关键字提升到父节点，原节点拆分为两个子节点：
template <typename T>
void BTree<T>::splitChild(BTreeNode<T>* parent, int childIdx) {
BTreeNode<T>* child = parent->children[childIdx];
// 创建新的右子节点
BTreeNode<T>* newChild = new BTreeNode<T>(m, child->isLeaf);
// 中间关键字的索引，提升到父节点
int mid = (m - 1) / 2;
T midKey = child->keys[mid];
// 将原节点的后半部分关键字移动到新节点
for (int i = mid + 1; i < child->keyNum; i++) {
newChild->keys.push_back(child->keys[i]);
newChild->keyNum++;
}
// 如果不是叶子节点，将原节点的后半部分子节点移动到新节点
if (!child->isLeaf) {
for (int i = mid + 1; i <= child->keyNum; i++) {
newChild->children.push_back(child->children[i]);
}
}
// 原节点保留前半部分关键字，更新关键字数量
child->keyNum = mid;
child->keys.resize(mid);
if (!child->isLeaf) {
child->children.resize(mid + 1);
}
// 将中间关键字插入父节点
parent->keys.insert(parent->keys.begin() + childIdx, midKey);
parent->keyNum++;
// 将新子节点插入父节点的子节点数组
parent->children.insert(parent->children.begin() + childIdx + 1, newChild);
}
插入操作实现
插入操作首先判断根节点是否为空，为空则创建根节点；如果根节点已满，先分裂根节点再插入；否则调用非满节点插入方法：
template <typename T>
void BTree<T>::insertNonFull(BTreeNode<T>* node, const T& key) {
int idx = node->findKey(key);
// 如果是叶子节点，直接插入关键字
if (node->isLeaf) {
node->keys.insert(node->keys.begin() + idx, key);
node->keyNum++;
} else {
// 如果子节点已满，先分裂
if (node->children[idx]->keyNum == m - 1) {
splitChild(node, idx);
// 分裂后需要判断插入到哪个子节点
if (key > node->keys[idx]) {
idx++;
}
}
insertNonFull(node->children[idx], key);
}
}
template <typename T>
void BTree<T>::insert(const T& key) {
// 根节点为空，直接创建根节点
if (root == nullptr) {
root = new BTreeNode<T>(m, true);
root->keys.push_back(key);
root->keyNum = 1;
return;
}
// 根节点已满，先分裂根节点
if (root->keyNum == m - 1) {
BTreeNode<T>* newRoot = new BTreeNode<T>(m, false);
newRoot->children.push_back(root);
splitChild(newRoot, 0);
// 新的根节点有两个子节点，判断插入到哪个子节点
int i = 0;
if (newRoot->keys[0] < key) {
i++;
}
insertNonFull(newRoot->children[i], key);
root = newRoot;
} else {
insertNonFull(root, key);
}
}
辅助方法实现
打印和内存释放的辅助方法实现如下：
template <typename T>
void BTree<T>::printRecursive(BTreeNode<T>* node, int level) {
if (node == nullptr) {
return;
}
cout << "Level " << level << ": ";
for (int i = 0; i < node->keyNum; i++) {
cout << node->keys[i] << " ";
}
cout << endl;
if (!node->isLeaf) {
for (int i = 0; i <= node->keyNum; i++) {
printRecursive(node->children[i], level + 1);
}
}
}
template <typename T>
void BTree<T>::printTree() {
printRecursive(root, 0);
}
template <typename T>
void BTree<T>::destroyTree(BTreeNode<T>* node) {
if (node == nullptr) {
return;
}
if (!node->isLeaf) {
for (int i = 0; i <= node->keyNum; i++) {
destroyTree(node->children[i]);
}
}
delete node;
}
测试示例
我们可以通过以下代码测试B树的基本功能：
int main() {
// 创建阶数为3的B树
BTree<int> btree(3);
// 插入测试数据
vector<int> testData = {10, 20, 5, 6, 12, 30, 7, 17};
for (int num : testData) {
btree.insert(num);
cout << "插入 " << num << " 后，B树结构：" << endl;
btree.printTree();
cout << "------------------------" << endl;
}
// 测试查找功能
cout << "查找 6: " << (btree.search(6) ? "找到" : "未找到") << endl;
cout << "查找 25: " << (btree.search(25) ? "找到" : "未找到") << endl;
return 0;
}
注意事项
上述实现是基础版本的B树，仅支持插入和查找操作，实际生产环境中还需要实现删除操作，删除操作的逻辑比插入更复杂，需要处理节点关键字数量不足时的合并或借调操作。另外，代码中的关键字类型默认是int，可以通过模板支持其他可比较的类型，使用时只需要保证类型支持小于、大于等比较操作即可。