B树是一种自平衡多路搜索树，满足最小度数t≥2、所有叶子同层等性质，适合磁盘I/O优化；其核心操作包括满则分裂的插入、多路比较的搜索及递归遍历。
用 c++ 实现一个简单的 B 树，核心在于理解 B 树的定义：它是一种自平衡的多路搜索树，每个节点可含多个键和子节点，满足最小度数 t（t ≥ 2），所有叶子在同一层，适合磁盘 I/O 优化——这正是数据库索引（如 mysql 的 InnoDB）底层常用结构的原因。
B 树的基本结构设计
我们以最小度数 t = 2（即每个非根节点至少有 1 个键、最多 3 个键，最多 4 个子节点）为例，定义节点结构：
- node 类：包含键数组
keys[]、子节点指针数组children[]、键数量n、是否为叶子isLeaf - BTree 类：持有一个根节点指针，封装
insert、search、splitChild、insertNonFull等方法 - 注意：B 树不直接支持重复键；如需支持，可在 value 中存链表或计数器
插入逻辑的关键步骤
插入必须维持 B 树性质，核心是「满则分裂」：
- 从根开始向下查找插入位置；若当前节点已满（
n == 2*t - 1 == 3），先调用splitChild将其分裂为两个 t−1 键的节点，并将中位键上推到父节点 - 递归进入未满的子树；到达叶子后直接插入排序位置
- 若根满，插入前先分裂根，树高 +1（这是 B 树保持平衡的关键）
搜索与简单遍历实现
搜索是标准的多路 BST 查找：
立即学习“C++免费学习笔记（深入）”；
- 在当前节点线性比较键，找到第一个 ≥ key 的位置 i
- 若
keys[i] == key，返回成功；否则沿children[i]继续递归（注意：i 从 0 开始，叶子无子节点需提前判断） - 中序遍历可用递归实现：左子树 → 输出键 → 右子树（对每个键间隔做一次）
可运行的极简源码（C++11，无模板，便于理解）
以下为完整可编译的简化版（仅含 insert / search / print）：
#include <iostream> #include <vector> using namespace std; <p>const int t = 2; // minimum degree</p><p>struct Node { vector<int> keys; vector<Node*> children; bool isLeaf; Node() : isLeaf(true) {} };</p><p>class BTree { public: Node* root; BTree() : root(nullptr) {}</p><pre class="brush:php;toolbar:false;">void insert(int k) { if (!root) { root = new Node(); root->keys.push_back(k); return; } if (root->keys.size() == 2*t-1) { Node* s = new Node(); s->children.push_back(root); splitChild(s, 0); root = s; } insertNonFull(root, k); } void insertNonFull(Node* x, int k) { int i = x->keys.size() - 1; if (x->isLeaf) { x->keys.push_back(0); // placeholder while (i >= 0 && x->keys[i] > k) { x->keys[i+1] = x->keys[i]; --i; } x->keys[i+1] = k; } else { while (i >= 0 && x->keys[i] > k) --i; ++i; if (x->children[i]->keys.size() == 2*t-1) { splitChild(x, i); if (k > x->keys[i]) ++i; } insertNonFull(x->children[i], k); } } void splitChild(Node* x, int i) { Node* y = x->children[i]; Node* z = new Node(); z->isLeaf = y->isLeaf; z->keys.assign(y->keys.begin()+t, y->keys.end()); if (!y->isLeaf) z->children.assign(y->children.begin()+t, y->children.end()); y->keys.resize(t-1); if (!y->isLeaf) y->children.resize(t); x->children.insert(x->children.begin()+i+1, z); x->keys.insert(x->keys.begin()+i, y->keys[t-1]); y->keys.pop_back(); } bool search(Node* x, int k) { if (!x) return false; int i = 0; while (i < x->keys.size() && k > x->keys[i]) ++i; if (i < x->keys.size() && x->keys[i] == k) return true; if (x->isLeaf) return false; return search(x->children[i], k); } void print(Node* x, int level = 0) { if (!x) return; cout << "Level " << level << ": "; for (int k : x->keys) cout << k << " "; cout << "n"; if (!x->isLeaf) for (Node* c : x->children) print(c, level+1); }};
// 示例用法 int main() { BTree t; for (int v : {10,20,5,6,12,30,7,17}) t.insert(v); t.print(t.root); cout
基本上就这些。实际数据库索引会扩展为支持范围查询、并发控制、持久化、键值对存储（而不仅是 int）、以及更复杂的合并/重平衡策略。但这个版本已体现 B 树的核心思想：分裂保平衡、多路降高度、局部有序支持高效检索。