一、B-树基础知识1.B-树的由来B树的出现是为了解决传统二叉平衡搜索树如AVL树和红黑树在磁盘与内存交互时效率低下的问题。传统树结构每个节点只存储一个值导致树的高度较高增加了磁盘访问次数。B树通过让一个节点存储多个有效值显著降低了树的高度从而减少了磁盘与内存的交互次数提升了查找、插入和删除操作的效率。B树的一个节点可以存储多个有效值并且保持节点内数据的有序性这使得B树在数据库和文件系统中广泛应用。2.B-树的特性有序性节点内数据是有序的任意一个元素其左子树都小于他其右子树都大于他平衡性所有的叶子节点都在同一层多路性阶数向外伸出手的个数节点的有效元素个数向外伸出手的个数-1分支根节点最多可以有M个分支最少要有2个分支非根节点最多可以有M个分支最少得有[M/2]个分支M阶限制的是分支个数上限下限根节点M2非根节点MM/2元素根节点元素最少可以有1个值最多可以有M-1个值非根节点元素最少得有[M/2]-1个值最多可以有M-1个值M阶限制的似乎元素个数上限下限根节点M-11非根节点M-1[M/2]-1总结B-树是一种自平衡的搜索树能够保持数据有序这种特殊的结构可以让查找操作/插入操作/删除数据可以保持高效的效率OlognB-树可以让每一个节点都拥有两个及两个以上的子节点因此B-树也叫做多叉平衡搜索树3.B-树的有效节点定义以5阶B-树有效节点设计为例数据域 key_arr[M1]孩子指针域 ptr_arr[M1]有效元素个数key_num双亲指针parent代码体现#pragma once typedef int ElemType; #define M 5 //B树的有效节点结构体设计 typedef struct BTNode { int key_num;//1.当前节点的有效元素个数 ElemType key_arr[M 1];//2.数据域数组存储若干个有效元素值 struct BTNode* ptr_arr[M 1];//3.孩子指针域 数组 存储若干个孩子节点的地址 struct BTNode* parent;//4.双亲指针 //struct BTNode* recptr[M 1];//recptr用来存储每一个元素所对应的在磁盘中的记录的地址 }BTNode;B-树是一种用于存储和组织数据的树形结构常常用于数据库中的索引应用这里的recptr是把B-树节点中的元素和其对应的存储在磁盘上的数据记录相关联通过recptr可以快速的定位到磁盘等存储介质上从而实现高效的数据插入4.B-树的辅助节点定义//B树的辅助节点结构体设计 typedef struct BTree { BTNode* root; }BTree;5.初始化BTree.h头文件//1.初始化 void Init_BTree(BTree* pTree);在BTree.cpp文件中我们实现函数代码所需的头文件#define _CRT_SECURE_NO_WARNINGS #include stdio.h #include stdlib.h #include string.h #include assert.h #include memory.h #include BTree.h初始化函数实现//1.初始化 void Init_BTree(BTree* pTree) { assert(pTree); if (pTree NULL) return; pTree-root NULL; }6.查找BTree.h头文件//因为查找的时候 要返回的信息要包含找到的val值的节点以及在这个节点中的下标等等所以专门对返回值设计一个结构体 typedef struct Result { BTNode* pNode;//告诉在哪一个节点里面找到 int index;//告诉在当前节点的那一个位置找到 bool tag;//告诉我找到没 }Result; //描述如果tag为真 ——》找到了 且在pNode指向的节点肚子里面的肚子里面的第index下标上找到 // 如果tag为假——》没有找到但是如果准备插入这个值则插入位置就是pNode指向的节点肚子里面的肚子里面的第index下标 //元素默认从key_arr这个数组的1号下标开始存贮 //孩子默认从ptr_arr这个数组的0号下标开始存储 //注意如果当前元素的自身下标是i // 则其对应的左子树在ptr_arr中的下标就是i-1; // 则其对应的右子树在ptr_arr中的下标就是i//2.查找 Result*Search_BT(BTNode* root, ElemType val);查找思路首先模拟二叉搜索树的查找逻辑只不过区别在于B-树一个节点里面可能会有多个有效值所以需要依次对每一个有效值进行判断如果大于当前有效值则向后走如果小于或者等于当前有效值则停下判断如果是因为找到一个等于自己的有效值则直接结束查找返回即可如果是因为找到一个大于自己的有效值则走当前元素的左子树即可函数退出有两种可能性找到了return result指针向下走遇到了NULL return result查找函数实现//2.查找 Result* Search_BT(BTNode* root, ElemType val) { //1.申请一个指针p让其从根节点出发 BTNode* p root; BTNode* pp NULL; int i 1; //2.进入循环循环条件是当前p节点存在即可 while (p ! NULL) { //3.对其现有的有效值依次从左向右遍历(申请一个变量i) i 1; while (i p-key_num) { //4.对当前i下标指向的值和要找的val值进行比较 if (p-key_arr[i] val) i; else if (p-key_arr[i] val) break;//p p-ptr_arr[i - 1]; else { //购买result 扔出去 Result* pr (Result*)malloc(sizeof(Result)); if (pr NULL) exit(EXIT_FAILURE); pr-tag true; pr-pNode p; pr-index i; return pr; } } //5.当内部的while循环退出说明当前p指向节点的所有现有的有效元素都小于要找的val值 // 则i肯定跳出指向了越界位置 停下来让p跳到其当前i指向格子的左子树(换句话说就 // 是让p跳到了最后一个有效元素的右子树) pp p; p p-ptr_arr[i - 1];//p p-ptr_arr[p-key_num]; } //5.当外层的while退出则说明找不到 //购买result 扔出去 Result* pr (Result*)malloc(sizeof(Result)); if (pr NULL) exit(EXIT_FAILURE); pr-tag false; pr-pNode pp; pr-index i; return pr; }7.打印BTree.h头文件void InOrder_BT(BTNode* root);打印函数实现void InOrder_BT(BTNode* root) { if (root NULL) return; for (int i 0; i root-key_num; i) { InOrder_BT(root-ptr_arr[i]); printf(%d , root-key_arr[i 1]); } InOrder_BT(root-ptr_arr[root-key_num]); }void InOrder_BT2(BTNode* root) { if (root NULL) return; InOrder_BT(root-ptr_arr[0]); for (int i 1; i root-key_num; i) { printf(%d , root-key_arr[i]); InOrder_BT(root-ptr_arr[i]); } }8.B-树的插入逻辑找到插入位置该值不存在的话将待插入值插入确定是否突破上限/上溢出如果没有突破则无需调整有突破则需要“分裂”分裂操作购买新节点RightNode放到当前待分裂节点Node的右侧找出待分裂节点Node的中位数将中位数右侧的所有东西全部挪给右侧的RightNode接收在最后将待分裂节点Node的中位数上移给其父节点接收如果父节点存在的话如果待分裂节点Node的父节点不存在则说明当前Node节点是根节点则再额外申请一个新根节点newroot用来接收此时的中位数注意事项找到中中位数之后需将中位数右侧的所有元素及其连带的孩子挪动给RightNode中位数上移的时候父节点如果不存在则申请一个新的根节点newroot来接收此时没有接收的中位数即可中位数上移的时候父节点如果存在则父节点中可能有若干有效值是大于上移的中位数的所以中位数插入到父节点过程中时需要将大于中位数的有效值及其紧挨的右孩子同一右移一位目的是留出一个合适的指针域用来指向RightNode示例使用187510479312750917290374174666845这组值构建5阶B-树我们在进行节点定义的时候是申请了M1个格子但是我们在窜存储数据的时候只利用中间白色格子1插入第一个值18刚开始是一颗空树辅助节点的root为NULL2插入第二个值753插入第三个值104插入第四个值475插入第五个值96插入第六第七个值31 276插入第八个值507插入第九个值9110插入第十个值7211插入第十一个值9012插入第十二个值3713插入第十三个值4114插入第十四个值7415插入第十五个值6616插入第十六个值6817插入第十七个值45BTree.h头文件//4.购买一个新节点 BTNode* BuyNode_BT(); //B-树的插入 bool Insert_BT(BTree* pTree, ElemType key); //分裂函数B-树的插入的调整函数 void Insert_Adjust_Split(BTree* pTree, BTNode* Node);购买一个新节点的代码实现BTNode* BuyNode_BT() { BTNode* pnewnode (BTNode*)malloc(sizeof(BTNode)); if (pnewnode NULL) exit(EXIT_FAILURE); memset(pnewnode, 0, sizeof(BTNode)); }分裂函数的代码实现//分裂函数(B-树的插入的调整函数) void Insert_Adjust_Split(BTree* pTree, BTNode* Node) { //1.购买新节点RightNode购买好之后放到待分裂节点Node的右侧 BTNode* RightNode BuyNode_BT(); //2.找出当前待分裂节点Node的中位数所在位置 int mid M / 2 1; //3.将中位数右侧的所有东西全部挪动给右侧的RIghtNode节点来接收 for (int i mid 1; i M; i)//i是传递方 RightNode-key_arr[i-mid] Node-key_arr[i]; //3.5 注意事项1有可能此时的待分裂节点Node不是叶节点是有很多孩子的需 //要将右半边的所有孩子也交给RightNode来接收 for (int i 0; i M / 2; i)//i是接收方 { RightNode-ptr_arr[i] Node-ptr_arr[M / 2 1 i]; if (RightNode-ptr_arr[i] ! NULL)//****** RightNode-ptr_arr[i]-parent RightNode; } //3.6 修正RightNode的有效元素个数 RightNode-key_num M / 2; //4.再将待分裂节点的中位数上移给父节点来接收 BTNode* father Node-parent; //注意事项2父节点是有可能不存在的 if (father NULL) { BTNode* newroot BuyNode_BT(); newroot-key_arr[1] Node-key_arr[mid]; newroot-ptr_arr[0] Node; newroot-ptr_arr[1] RightNode; Node-parent RightNode-parent newroot; newroot-key_num; pTree-root newroot; Node-key_num M / 2;//****** return; } else { int i father-key_num; for (; i 1; i--) { if (father-key_arr[i] Node-key_arr[mid]) { //注意事项3父节点中大于中位数的值向后挪动的时候也连着其各自的右孩子也向 // 右挪动一位留出一个孩子指针域用来指向RightNode father-key_arr[i 1] father-key_arr[i]; father-ptr_arr[i 1] father-ptr_arr[i]; } else break;//父节点中确实找到了一个比中位数小的值 } father-key_arr[i1] Node-key_arr[mid]; father-ptr_arr[i1] RightNode; RightNode-parent father; } //5.再对更新之后的父节点的key_num做判断如果父节点没有出现连续的上溢出则直接结束 father-key_num; //5.5 也更新一下Node节点的有效元素个数 Node-key_num M / 2; //6.反之则说明父节点也出现了连续的上溢出则对其父节点再次分裂 if (father-key_num M) { Insert_Adjust_Split(pTree, father); } }插入函数的代码实现//B-树的插入 bool Insert_BT(BTree* pTree, ElemType key) { //0.assert //0.5 防止原本是一颗空树 if (pTree-root NULL) { BTNode* pnewnode BuyNode_BT(); pnewnode-key_arr[1] key; pnewnode-key_num; pTree-root pnewnode; return true; } //1.先去调用Search函数去查找key值是否存在(返回值是一个Result结构体变量) Result* pr Search_BT(pTree-root, key); //2.根据Search函数的返回值结果来先判断出key值如果真的存在则无序再插入了 if (pr-tag) return true; //3.反之如果Search函数的返回值结果该key值不存在则说明该key值里面是没有的但 // 是如果此时要想往里面插入则直接插入到pNode指向的节点里面的第index下标上 //4.插入完成再让key_num /*int i pr-pNode-key_num; for (; i 1; i--) { if (pr-pNode-key_arr[i] key) pr-pNode-key_arr[i 1] pr-pNode-key_arr[i]; else break; } pr-pNode-key_arr[i 1] key;*/ for (int i pr-pNode-key_num; i pr-index; i--) pr-pNode-key_arr[i 1] pr-pNode-key_arr[i]; pr-pNode-key_arr[pr-index] key; //5.key_num之后再去判断是否上溢出如果上溢出了则直接调用分裂函数反之无需 // 调整直接结束 pr-pNode-key_num; if (pr-pNode-key_num M) Insert_Adjust_Split(pTree, pr-pNode); return true; }9.B-树的删除删除操作查找待删除值是否存在如果不存在则直接返回如果存在则进一步判定是在叶子节点上还是非叶子节点上如果在非叶子节点上则直接用直接前驱或者直接后继元素来顶替他被删除如果在叶子节点上直接删让其直接后续的元素整体前移再让该节点的有效元素个数减1然后在判断该节点是否下溢出如果没有下溢出则无需调整如果有下溢出则执行调整操作调整操作1.先找其兄弟节点看是否能够借到借取操作口诀父下来兄上去1.1 如果有两个兄弟则自选其一1.2如果有一个兄弟够借则只能问该兄弟借1.3如果有零个兄弟够借则只能执行合并操作2.执行合并操作口诀父下左右靠左2.1如果两个兄弟都在则自选其一合并2.2如果只有一个兄弟存在则只能和该兄弟合并2.3如果有零个兄弟存在这种情况不存在3.如果可以执行借取操作则直接执行借取操作后就可以直接结束了但是如果执行合并操作则执行完合并操作后需要判断其父节点是否出现了连续的下溢出现象如果没有则直接结束如果其父节点真的出现了连续的下溢出则需要对其父节点接着调整注意事项借取操作中如果你和你借的兄弟不在叶子节点层则你兄弟替你还给父节点一个元素之后你兄弟肯定会有一个孩子没有人来管则你需要替你兄弟把这个孩子收养一下合并操作中如果你和你合并的兄弟不在叶子节点层则将相对偏左的节点吸收相对偏右的节点的时候不仅需要将其所有的元素吸收还需要将其所有的孩子吸收掉合并操作中会导致父节点永久的少一个元素所以有可能父节点出现连续的下溢出如果父节点是非根节点触发下溢出则对其父节点接着调整即可但是如果父节点是根节点触发的下溢出则需要将其父节点释放掉将刚才合并的节点当新的根节点来使用事例按顺序删除45 68 86 30 57 531删除第一个值45分析45存在是一个非叶子节点狸猫换太子找其直接前驱或者直接后继来顶替他这里采用直接后继的方法用47向前覆盖掉46,50也向前移动并且Key_num减将狸猫删除之后发现该有效节点也没有下溢出则无需调整直接结束2删除第二个值68分析68删除完之后发现该节点有效元素个数-1之后该节点下溢出了先去找直接的左兄弟或者有兄弟借从图上看左右兄弟都存在且都能够借在则自己选择其一即可这里采用的是和用兄弟借借取操作父下来兄上去父下来父节点中被你和你的右兄弟所夹的元素挪下来给你兄上去兄弟节点替你还给父节点一个3删除第三个值86分析86存在且是叶子节点直接删除但是发生了下溢出且其左右兄弟都存在但是都没有办法给你借取所以直接执行合并操作合并操作父下左右靠左父下左你和你的兄弟所夹的元素给到相对偏左的的人来接收例如你和你的左兄弟合并则你的左兄弟是更偏左的节点你和你的有兄弟合并则你自己是更偏左的节点右靠左相对偏右的节点的所有东西全部被相对偏左的节点吸收掉这里采用和左兄弟合并的方式合并操作会导致父节点永久的缺少一个元素则有一定的概率会造成父节点连续的下溢出此时图中没有造成连续的下溢出的4删除第四个值30分析30存在但是其是非叶子节点则直接用直接前驱去顶替此时绿色框这个节点造成了下溢出且左兄弟不存在右兄弟不够借则转头去执行合并操作只有一个右兄弟所以合并操作只能和右兄弟合并合并完成之后此时绿色框造成了下溢出此时对这个绿色框也就是父节点进行调整对其父节点先进行借取操作借不了再合并父节点只有右兄弟右兄弟够借借取操作时如果兄弟是非叶子节点则兄弟节点替你还给父节点一个元素之后肯定会导致有一个孩子没有人来管则借取的节点来收养合并操作可能会导致父节点出现连续的下溢出但是借取操作不会因为父节点根本就没有少元素5删除第五个值57分析57存在且是叶子节点删除完毕之后发现没有造成下溢出则无需调整6删除第六个值47分析47存在且是叶子节点则直接删除删除之后发现其下溢出了该节点造成下溢出且只有左兄弟且左兄弟还不够借则只能和左兄弟执行合并操作此时合并操作导致父节点触发了连续的下溢出父节点只有一个右兄弟且不够借则也只能执行合并操作如果节点合并的时候导致其父节点的有效节点的有效元素个数从1个变0个则说明原本的父节点是根节点则释放其原本的根节点转头让刚刚合并的节点作为新的根节点。函数代码实现借操作函数和左兄弟借//借操作函数 void Borrow_LeftBro(BTNode* node, BTNode* LeftBro, BTNode* father, int index)//和左兄弟借 { //口诀父下来兄上去 //1.将node节点现有的所有元素后移一位留出头部 for (int i node-key_num; i 1; i--)//挪node所有元素 node-key_arr[i1] node-key_arr[i]; //如果是非叶子则还需要将其所有孩子右移 if (node-ptr_arr[0] ! NULL) { for (int i node-key_num; i 0; i--)//挪node所有孩子 node-ptr_arr[i 1] node-ptr_arr[i]; } //2.将父节点下来的元素放置到node节点留出的头部位置 node-key_arr[1] father-key_arr[index]; //3.将左兄弟最大值还给父节点 father-key_arr[index] LeftBro-key_arr[LeftBro-key_num]; //4.接收一下左兄弟最右端的孩子(如果左兄弟是非叶节点的话) if (LeftBro-ptr_arr[0] ! NULL) { node-ptr_arr[0] LeftBro-ptr_arr[LeftBro-key_num]; node-ptr_arr[0]-parent node; } //5.修正一下各个节点的有效元素个数 node-key_num; //father; father一来一回没变 LeftBro-key_num--; }合并函数和右兄弟合并//合并操作右兄弟 BTNode* Merge_RightBro(BTNode* node, BTNode* RightBro, BTNode* father, int index) //和右兄弟合并 { //口诀父下左右靠左 //1.直接让相对偏左的node节点的屁股后面用来接收父节点下来的元素值 node-key_arr[node-key_num 1] father-key_arr[index]; //2.将右兄弟的所有的元素统一让相对偏左的node节点来吸收 for (int i 1; i RightBro-key_num; i) node-key_arr[node-key_num 1 i] RightBro-key_arr[i]; //3.将右兄弟的所有的孩子统一让相对偏左的node节点也来吸收(如果存在的话) if (RightBro-ptr_arr[0] ! NULL) { for (int i 0; i RightBro-key_num; i) node-ptr_arr[node-key_num 1 i] RightBro-ptr_arr[i]; } //4.让父节点下来的那个元素的后续的元素及其孩子前移 /*for (int i index 1; i father-key_num; i) father-key_arr[i-1] father-key_arr[i]; for (int i index 1; i father-key_num; i) father-ptr_arr[i-1] father-ptr_arr[i];*/ for (int i index 1; i father-key_num; i) { father-key_arr[i - 1] father-key_arr[i]; father-ptr_arr[i - 1] father-ptr_arr[i]; } //5.修正各个节点的有效元素个数 node-key_num M - 1; free(RightBro); RightBro NULL; father-key_num--; //6.直接将其父节点扔出去让外面去接收判断是否出现了连续的下溢出 return father; }