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、是否为叶子 isLeafBTree 类：持有一个根节点指针，封装 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 #include using namespace std;const int t = 2; // minimum degree
struct Node {vector keys;vector children;bool isLeaf;Node() : isLeaf(true) {}};
class BTree {public:Node* root;BTree() : root(nullptr) {}
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 keys.size() && k > x->keys[i]) ++i; if (i 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 <keys) cout << k << " "; cout <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 树的核心思想：分裂保平衡、多路降高度、局部有序支持高效检索。
以上就是c++++如何实现一个简单的B树_c++ B-Tree数据结构与数据库索引【源码】的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488555.html
微信扫一扫 
支付宝扫一扫 
