B树详解：从零构建平衡多路搜索树

keyipatience:个人主页作者简介C/C后端开发学习者专栏传送门《c》《linux》《c高阶数据结构》《c数据结构与算法》⭐️patience is key in life初识B树简单来说B树其实就是一颗平衡多插树对比我们前面学习的平衡二叉树多了几个分支下面以5阶B树为例先判断这棵树是5 阶 B 树m5m 阶 B 树最多m个分支m-1个关键字。 看结点23,35,47,55里面有最多有4 个关键字 → 4 个关键字对应 5 个分支所以 m5。m:阶数k分支n:关键字,nk-1;任意一颗B数都满足[m/2] ≤ k ≤ m,[m/2]-1nm-1在这里即3k5,2n4;B树性质平衡所有叶结点都在同一层定义B 树永远平衡全部叶子结点处于同一高度不会出现有的叶子很深、有的很浅。看例子根17第 0 层中间层6 13和23 35 47 55第 1 层叶子层1 4、8 11、14 16、19 22、27 34、38 45、49 53、65 74 79全部都在第 2 层所有叶子都在最下面同一层满足 B 树平衡特性。对比二叉搜索树二叉树最坏会退化成链表叶子高度参差不齐B 树强制叶子同层所以查询稳定。有序结点内有序关键字划分左右子树区间两点 ① 同一个结点内部的关键字从小到大排好序 ② 任意关键字左子树全部 该关键字右子树全部 该关键字看例子结点23,35,47,55内部23354755有序23 左子树19,22 2323~35 子树27,342327,343535~47 子树38,453538,454747~55 子树49,534749,535555 右子树65,74,7955查找逻辑比如找 38从根 17 → 大于 17 走右子树23,35,47,5538 大于 35小于 47进入 35 和 47 之间的子树找到38,45。多路m 阶 B 树结点分支数有上下限对于 m 阶 B 树的结点1.上限所有结点通用根、普通结点一样最多m 个分支,m-1个 个关键字元素关键字数量永远 分支数量 − 12.下限重点根结点和其他结点分开根结点最少2 个分支1 个关键字特殊情况如果整棵树只有根一个节点没有孩子根可以0 个分支1 个关键字其他所有非根结点最少[m/2]个分支,[m/2]-1个关键字以m5这棵树为例上限全部结点最多 5 分支4 关键字 例子第二层结点23,35,47,554 个关键字5 个分支刚好顶到上限。下限根结点最少 2 分支、1 关键字。图里根17正好1 个关键字、2 个分支普通非根结点最少 3 分支、2 关键字。 看叶子结点1 42 个关键字满足≥2 中间结点6 132 个关键字满足≥2。一步步实现B树的构造插入和中序遍历1.BTreeNode 结点结构体template class K,int M struct BTreeNode { //多给一个空间就可以先插入了再分裂 // 存放关键字最多M个 K _keys[M]; // 子节点指针最多M个关键字所以开M1空间 BTreeNodeK, M* _subs[M1]; //实际存储多少个关键字 int _n; // 父节点指针分裂的时候向上找父节点 BTreeNodeK, M* _parent; //初始化 BTreeNode() :_parent(nullptr) ,_n(0) { for (int i 0; i M; i) { _keys[i] K(); _subs[i] nullptr; } _subs[M] nullptr; } };M 阶 B 树最多只能放 M-1 个关键字_key[M]和_subs[M1]多预留一个位置是为了插入临时填满之后再分裂2.BTree 类 内部 typedeftypedef BTreeNodeK, MNode; private: Node* _root nullptr;3. Find 函数查找 key返回 pair 结点指针下标pairNode*, intFind(const K key) { Node* parent nullptr; Node* cur _root; int i 0; while (cur) { // 在当前结点内部顺序查找关键字 while (i cur-_n) { if (key cur-_keys[i]) { break; // 目标落在第i个子树 } else if (key cur-_keys[i]) { i; // 继续往后找 } else { return make_pair(cur, i); // 找到返回结点下标 } } // 进入子树继续查找 parent cur; cur cur-_subs[i];// 去subs[i]子树 } // cur为空说明没找到parent是要插入的叶子结点 return make_pair(parent,-1); }4.InsertKey把 key 插入 node 结点同时带上 child 子节点功能向 node 结点插入关键字 key并且把 child 子树挂在 key 的右侧这个函数不做分裂只管插入插入之后外面判断结点满不满。// node待插入节点key关键字child这个key右侧的子节点指针 void InsertKey(Node* node, const K key, Node* child) { // end从当前已有最后一个关键字下标开始向前找 int end node-_n - 1; while (end 0) { // 如果当前关键字比key大 → 向后挪腾位置 if (key node-_keys[end]) { node-_keys[end 1] node-_keys[end]; // 子指针同步后移 node-_subs[end 2] node-_subs[end1]; --end; } else { break; // 找到位置退出循环 } } // 把key放到空位 end1 node-_keys[end 1] key; // key的右侧子节点child放到 subs[end2] node-_subs[end 2] child; node-_n; // 如果child不为空设置它的父节点为当前node更新 child 的父指针。 if (child)child-_parent node; }5.Insert 核心插入函数bool Insert(const K key) { // 情况1树是空直接新建根放key if (_root nullptr) { _root new Node; _root-_keys[0] key; _root-_n; return true; } // 查找key是否已经存在存在直接返回false pairNode*, intret Find(key); if (ret.second 0)return false; // ret.first找到的叶子节点就是要插入的起点 Node* parent ret.first; K newKey key; Node* child nullptr; // 循环向上处理分裂你的版本是while循环不是递归重点 while (1) { // 调用InsertKey把newKey插入parent节点child是newKey右边子树 InsertKey(parent, newKey,child); // 插入之后节点关键字数量 M没有满直接结束 if (parent-_n M) { return true; } else { // 插入之后节点满了触发分裂 int mid M / 2; // 新建兄弟节点分裂出来的右半部分 Node* brother new Node; int j 0; int i mid 1; // 把parent[mid1 ... M-1]的关键字、子指针拷贝到brother for (; i M - 1; i) { brother-_keys[j] parent-_keys[i]; brother-_subs[j] parent-_subs[i]; // 拷贝过去的子节点父指针改成brother if (parent-_subs[i]) { parent-_subs[i]-_parent brother; } j; // 清空原节点已经拷贝走的数据 parent-_keys[i] K(); parent-_subs[i] nullptr; } // 单独处理最后一个子指针 subs[M] brother-_subs[j] parent-_subs[i]; if (parent-_subs[i]) { parent-_subs[i]-_parent brother; } parent-_subs[i] nullptr; brother-_n j; // 新右节点关键字个数 // 原节点保留mid个关键字减去brother的数量中间midKey parent-_n - (brother-_n 1); // 判断分裂的是不是根 if (parent-_parent nullptr) { // 分裂根节点新建全局根把中间关键字提上去 _root new Node; _root-_keys[0] parent-_keys[mid]; parent-_keys[mid] K(); // 原节点清空中间关键字 // 新根的两个孩子分裂后的左节点parent、右节点brother _root-_subs[0] parent; _root-_subs[1] brother; _root-_n 1; parent-_parent _root; brother-_parent _root; break; } else { // 不是根中间关键字要向上插入到【parent的父节点】 newKey parent-_keys[mid]; // 待向上提交的中间key parent-_keys[mid] K(); // 原节点清空中间key child brother; // 这个中间key的右孩子就是brother parent parent-_parent; // 向上走到父节点下一轮循环继续InsertKey } } } return true; }Find 找到叶子准备插入进入 while 循环调用InsertKey(parent, newKey, child)插入后如果节点没满直接 return true如果满了分裂把 mid1 后面所有 key 子指针拷贝给 brother新右节点原节点parent砍掉后半部分保留前 mid 个 key中间关键字parent-_keys[mid]要往上提交如果当前是根新建根树高度 1退出循环如果不是根newKey 中间关键字child brother中间 key 的右子树就是新分裂出来的 brotherparent parent-_parent回到 while 循环再次调用 InsertKey向上插入实例例子 1插入 50不触发分裂Find(50)落到叶子49,53ret.second-1不存在parent 叶子(49,53)newKey50childnullptr进入 while 循环执行InsertKey(parent,50,nullptr)end 初始 1keys[49,53]505353 后移end0key5049breakkeys[end1]keys[1]50subs[2]nullptr_n变成 3判断parent-_n 5→ 35满足return true 结束叶子变成49,50,53例子 2继续插入 52叶子变成49,50,52,53_n4还没满继续插入 54Find 落到叶子49,50,52,53_n4while 循环InsertKey(parent,54,nullptr)插入完成_n5等于 M5节点满进入分裂分支mid M/2 2parent 现在 keys[49,50,52,53,54]i 从 mid13 开始拷贝到 M-14i3key53subs [3] 拷贝给 brotheri4key54subs [4] 拷贝给 brotherbrother 的_n2保存 53、54parent-_n - (21)→ 5-32原节点保留前 2 个 key49,50midKey parent-_keys[2] 52parent 不是根所以newKey 52; child brother; parent parent-_parent; // 走到父节点23,35,47,55回到 while 循环再次执行InsertKey(parent, newKey52, childbrother)重点这次 InsertKey 的 child 不再是 nullptrchild 是刚分裂出来的 brother 节点 含义在父节点插入 5252 右边的子树就是 brother插入 52 之后父节点23,35,47,52,55_n5 M再次触发分裂继续向上循环处理。_InOrder 中序遍历void _InOrder(Node* cur) { if (cur nullptr)return; int i 0; for (; i cur-_n; i) { _InOrder(cur-_subs[i]);//先遍历第i个子树 cout cur-_keys[i] ;//输出当前关键字 } _InOrder(cur-_subs[i]);//最后一个子树 } void InOrder() { _InOrder(_root); }完整代码#includeiostream using namespace std; template class K,int M struct BTreeNode { K _keys[M]; BTreeNodeK, M* _subs[M1]; //多给一个空间插入了再分裂 int _n;//实际存储多少个关键字 BTreeNodeK, M* _parent; BTreeNode() :_parent(nullptr) ,_n(0) { for (int i 0; i M; i) { _keys[i] K(); _subs[i] nullptr; } _subs[M] nullptr; } }; template class K, int M class BTree { typedef BTreeNodeK, MNode; public: pairNode*, intFind(const K key) { Node* parent nullptr;//记录父亲方便后面插入时能找到叶子节点 Node* cur _root; int i 0; while (cur) { //在单独一个节点找 while (i cur-_n) { if (key cur-_keys[i]) { break; } else if (key cur-_keys[i]) { i; } else { return make_pair(cur, i); } } //去下一个分支 parent cur; cur cur-_subs[i]; } //找不到把叶子节点parent带回去 return make_pair(parent,-1); } void InsertKey(Node* node, const K key, Node* child) { int end node-_n - 1; while (end 0) { if (key node-_keys[end]) { node-_keys[end 1] node-_keys[end]; node-_subs[end 2] node-_subs[end1]; --end; } else { break; } } node-_keys[end 1] key;//比所有小到-1正常情况 node-_subs[end 2] child; node-_n; if (child)child-_parent node; } bool Insert(const K key) { if (_root nullptr) { _root new Node; _root-_keys[0] key; _root-_n; return true; } //key已经存在就不插入 pairNode*, intret Find(key); if (ret.second 0)return false; Node* parent ret.first; K newKey key; Node* child nullptr; //检查满没有,满了就分裂没有就结束 while (1) { InsertKey(parent, newKey,child); if (parent-_n M) { return true; } else { int mid M / 2; Node* brother new Node; int j 0; int i mid 1; for (; i M - 1; i) { brother-_keys[j] parent-_keys[i]; brother-_subs[j] parent-_subs[i]; if (parent-_subs[i]) { parent-_subs[i]-_parent brother; } j; //清楚拷贝走了的 parent-_keys[i] K(); parent-_subs[i] nullptr; } //最后剩一个右孩子,iM brother-_subs[j] parent-_subs[i]; if (parent-_subs[i]) { parent-_subs[i]-_parent brother; } parent-_subs[i] nullptr; brother-_n j; parent-_n - (brother-_n 1);//3-21,还有一个中间节点 //说明刚刚分裂的是根节点 if (parent-_parent nullptr) { //产生新的root _root new Node; _root-_keys[0] parent-_keys[mid]; parent-_keys[mid] K(); _root-_subs[0] parent; _root-_subs[1] brother;//新建的rootparent和brother都还没有维护 _root-_n 1; parent-_parent _root; brother-_parent _root; break; } else { //转换往parent-_parent插入中间节点和添加brother的分支parent不需要再添加 newKey parent-_keys[mid]; parent-_keys[mid] K(); child brother; parent parent-_parent; } } } return true; } void _InOrder(Node* cur) { if (cur nullptr)return; int i 0; for (; i cur-_n; i) { _InOrder(cur-_subs[i]);//左子树 cout cur-_keys[i] ;//根 } _InOrder(cur-_subs[i]);//最后右子树 } void InOrder() { _InOrder(_root); } private: Node* _root nullptr; }; void TestBTree() { int a[] { 53,139,75,49,145,36,101 }; BTreeint, 3t; for (auto e : a) { t.Insert(e); } t.InOrder(); } int main() { TestBTree(); return 0; }测试例子void TestBTree() { int a[] { 53,139,75,49,145,36,101 }; BTreeint, 3t; for (auto e : a) { t.Insert(e); } t.InOrder(); }运行结果