一、什么是B树一B树的由来二叉搜索树BST在极端情况下会退化成链表查询复杂度从O(logn)变为O(n)AVL树、红黑树优化了平衡问题但每个节点最多2个子节点当数据量非常庞大时树的高度也会非常大计算机存储分为内存和磁盘内存读写快但容量小磁盘容量大但读写慢。而树的每一层节点访问磁盘和内存都需要交互一次这也就意味着若树的高度非常高那么在数据查找时磁盘和内存的交互次数也会很多这就大大的较低了数据查询的效率。B树的核心思想放弃二叉分支采用多路分支让单个节点存储更多关键字拥有更多子节点极大降低了树的高度在进行查找时磁盘与内存的交互次数也会极大减少效率自然也会大幅提升二B树的概念B树也叫做B-树是一种平衡的多路查找树。m 阶的B树表示B树中的每个节点最多拥有 m 个子节点也就是最多可以向外伸出m个分支对应最多存储 m-1 个元素常用标准m阶B树元素个数上限元素个数下限根节点m - 11非根节点m - 1[m / 2] - 1 (向上取整)在实际工作或学习中B树都是奇数阶为主所以一般我们记忆非根节点的下限直接用M/2三B树的特性所有叶子节点全部在同一层m阶B树中任意非根节点的元素数量满足[m / 2] - 1 (向上取整) 元素个数 m-1根节点最少可以只有1个元素树非空时根节点若不是叶子节点至少拥有2个子节点也就是至少向外伸出2个分支拥有k个元素的非叶子节点必然拥有k1个子节点也就是必然向外伸出k1个分支元素与子节点有序对应节点内所有元素从小到大有序排列左子树所有元素 当前元素 右子树所有元素二、B树相关操作及代码实现一B树的节点定义1.有效节点结构体设计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.双亲指针 // 5.recptr数组每个元素对应的磁盘记录地址 }BTNode;假设为5阶B树M5每个节点最多存储4个元素最多可以向外伸出5个分支在设计有效节点时通常将数据域数组key_arr和孩子指针域数组ptr_arr的大小设为M1key_arr01 2 3 45 元素从1号下标开始存储ptr_arr0 1 2 3 45孩子节点指针从0下标开始存储这样的话如果当前元素自身在 key_arr 中下标是i则其对应的左子树在 ptr_arr 中的下标就是i - 1则其对应的右子树在 ptr_arr 中的下标就是i2.辅助节点结构体设计// B树的辅助节点结构体设计 typedef struct BTree { BTNode* root; // 根节点指针域 }BTree;3.返回值结构体设计因为查找的时候要返回的信息比较多找没找到、在哪个节点、在节点的第几个位置所以专门对返回值设计一个返回值结构体// 返回值结构体设计 typedef struct Result { bool tag; // 1.找没找到 BTNode* pNode; // 2.在哪个节点里面找到 int index; // 3.在当前节点的哪一个位置找到 }Result;tag true找到了目标值在 pNode 节点的 key_arr[index] 位置tag false没找到但是如果要插入这个值就应该插到 pNode 节点的 key_arr[index] 这个位置指向的节点肚子里面的第index下标上二工具函数1.购买新节点// 购买新节点 BTNode* BuyNode_BT() { BTNode* pnewnode (BTNode*)malloc(sizeof(BTNode)); if (pnewnode NULL) exit(EXIT_FAILURE); // 内存申请失败直接退出程序 // 将节点整块内存置0元素数量、数组、指针全部清零 memset(pnewnode, 0, sizeof(BTNode)); return pnewnode; }三相关函数1.初始化// 初始化 void Init_BTree(BTree* pTree) { // 断言树结构体指针非空 assert(pTree); // 初始化根节点为空树 pTree-root NULL; }2.查找// 查找在以root为根的B树中查找元素val返回查找结果结构体指针 Result* Search_BT(BTNode* root, ElemType val) { BTNode* p root; // p遍历当前节点 BTNode* pp NULL; // pp保存上一层节点查找失败时记录待插入的父节点 // 进入循环循环条件当前访问节点不为空 int i 1; while (p ! NULL) { // 从下标1开始从左至右遍历当前节点内所有有效值 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; } else { // 找到目标值val申请Result结构体保存查找信息并返回 Result* pr (Result*)malloc(sizeof(Result)); if (pr NULL) exit(EXIT_FAILURE); pr-tag true; // 标记查找成功 pr-pNode p; // 记录目标值所在节点 pr-index i; // 记录目标值在key_arr中的下标从1开始 return pr; } } // 内层循环结束进入对应子节点继续查找 pp p; // 保存当前节点作为父节点 p p-ptr_arr[i - 1]; // 跳转到对应子树继续搜索 } // 外层循环结束pNULL查找失败 Result* pr (Result*)malloc(sizeof(Result)); if (pr NULL) exit(EXIT_FAILURE); pr-tag false; // 标记查找失败 pr-pNode pp; // 记录待插入位置的父节点 pr-index i; // 记录在父节点中应该插入的位置 return pr; }3.打印// 中序遍历递归版本 void InOrder_BT(BTNode* root) { if (root NULL) return; // 依次访问第i个元素的左子树 for (int i 1; i root-key_num; i) { InOrder_BT(root-ptr_arr[i - 1]); // 递归遍历第i个元素左子树 printf(%d , root-key_arr[i]); // 打印当前元素 } // 遍历最右侧子树最后一个元素的右子树 InOrder_BT(root-ptr_arr[root-key_num]); }// 中序遍历递归版本写法2逻辑是一样的 void InOrder_BT2(BTNode* root) { if (root NULL) return; InOrder_BT2(root-ptr_arr[0]); // 访问第一个关键字左侧子树 for (int i 1; i root-key_num; i) { printf(%d , root-key_arr[i]); // 输出当前关键字 InOrder_BT2(root-ptr_arr[i]); // 访问当前关键字右侧子树 } }4.插入插入流程先调用查找函数查找关键字若关键字存在直接返回若关键字不存在则在返回的父节点中将大于目标值的关键字后移腾出空位插入新 key节点计数自增检查是否突破节点的元素上限上溢出若没有突破则无需调整若有突破则需要“分裂”分裂操作购买新节点 RightNode 放到当前待分裂节点 Node 的右侧找到待分裂节点 Node 的中位数位置将中位数右侧的所有元素以及对应的孩子指针全部迁移到 RightNode同步修改孩子节点的 parent 双亲指针将待分裂节点 Node 的中位数上移让其父节点接收如果父节点不存在说明当前 Node 节点是根节点需要再新建一个根节点newroot用于接收此时的中位数原根节点Node与 RightNode 作为新根节点的左右两个孩子如果父节点存在父节点内大于中位数的元素连同孩子指针整体右移插入中位数并将 RightNode 节点挂载到父节点上1插入操作函数// B树的插入 bool Insert_BT(BTree* pTree, ElemType key) { assert(pTree ! NULL); // 0.5 处理空树场景直接新建根节点存放key if (pTree-root NULL) { BTNode* pnewnode BuyNode_BT(); pnewnode-key_arr[1] key; pnewnode-key_num; pTree-root pnewnode; return true; } // 1.调用查找函数判断key是否已经存在同时拿到待插入位置信息返回值是一个Result结构体变量 Result*pr Search_BT(pTree-root, key); // 2.tag为true代表key值已存在不需要重复插入 if (pr-tag) return true; // 3.反之key值不存在将key值插入到pNode节点的第index下标上 // 大于key的关键字也就是index下标及后面的元素统一后移一位腾出插入位置index 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; // 插入完成当前节点关键字计数1 pr-pNode-key_num; // 4.判断是否上溢出如果上溢出了则直接调用分裂函数反之则无需调整直接结束 if (pr-pNode-key_num M) { Insert_Adjust_Split(pTree, pr-pNode); } return true; }2工具函数分裂函数// 分裂函数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]; RightNode-key_num ; // 更新RightNode的有效元素个数 } //3.5 如果待分裂节点Node不是叶子节点中位数右侧元素对应的孩子指针也要迁移到RightNode for (int i 0; i M/2; i) { RightNode-ptr_arr[i] Node-ptr_arr[mid i]; // 迁移孩子节点时同步更新孩子节点的父指针 if(RightNode-ptr_arr[i] ! NULL) RightNode-ptr_arr[i]-parent RightNode; } // 4.将待分裂节点Node的中位数上移交给父节点来接收 BTNode* father Node-parent; // 4.1 父节点为空代表当前分裂的是根节点需要新建新根节点 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; newroot-key_num; Node-key_num M / 2; // 更新Node节点的有效元素个数 // 更新左右孩子的双亲指针parent Node-parent RightNode-parent newroot; pTree-root newroot; return; } else { // 4.2 父节点存在把中位数插入父节点中大于中位数的元素连同子指针一起后移 int i father-key_num; for (; i 1; i--) { if (father-key_arr[i] Node-key_arr[mid]) { father-key_arr[i 1] father-key_arr[i]; father-ptr_arr[i 1] father-ptr_arr[i]; } else break; // 找到插入位置停止前移 } // 将中位数放入父节点腾出的空位 father-key_arr[i 1] Node-key_arr[mid]; father-ptr_arr[i 1] RightNode; RightNode-parent father; } // 5.父节点关键字数量1同时修改原节点的有效关键字个数只保留中位数左边 father-key_num; // 5.5 更新Node节点的有效元素个数 Node-key_num M / 2; // 6.父节点插入中位数后若出现溢出递归向上继续分裂 if (father-key_num M) Insert_Adjust_Split(pTree, father); }5.删除删除逻辑调用查找函数查找待删除值如果找不到目标值直接返回删除失败。如果目标值存在判断待删除值所在节点类型叶子节点直接删除目标值将它后面所有元素整体向前移动一位更新节点有效元素个数非叶子节点找到待删除值的直接前驱/直接后继用直接前驱/直接后继覆盖待删除值再直接删除直接前驱/直接后继待删除值的直接前驱/直接后继一定是叶子节点“狸猫换太子”删除完成后检查当前节点是否发生下溢出。没有下溢删除结束发生下溢则进入调整函数。下溢调整逻辑当有效节点的元素个数低于元素下限时则出现了下溢出需要对树进行调整优先向兄弟节点借元素借不到则执行节点合并方案1向兄弟节点借元素口诀父下来兄上去借关键字不会减少父节点关键字总数调整一次即可结束不需要继续向上传递下溢。和左兄弟借左兄弟关键字充足大于节点元素个数下限借出一个元素后不会出现下溢出当前节点内部所有元素向后挪一位头部留出空位非叶子节点的孩子指针也要同步后移父节点中分隔当前节点和左兄弟的元素下移放到当前节点的头部空位左兄弟最右侧元素上移放到父节点刚才空出来的位置如果左兄弟是非叶子节点左兄弟最右侧的孩子节点过继给当前节点作为最左侧孩子节点并修改该孩子节点的双亲指针更新两个节点的有效元素个数当前节点 1左兄弟 - 1和右兄弟借右兄弟关键字充足大于节点元素个数下限借出一个元素后不会出现下溢出父节点中分隔当前节点和右兄弟的元素下移放到当前节点末尾右兄弟最左侧元素上移填补父节点空出的位置如果右兄弟是非叶子节点右兄弟最左侧的孩子节点过继给当前节点作为新的末尾孩子并修改该孩子节点的双亲指针右兄弟内部所有元素、孩子指针整体前移填补头部空位更新两个节点的有效元素个数当前节点 1右兄弟 - 1方案2节点合并口诀父下左右靠左当左右兄弟元素个数都刚好等于下限没有多余元素可以借出只能合并。 合并会拿走父节点里的一个元素父节点关键字数量减一有可能引发父节点下溢循环向上调整。和左兄弟合并当前节点在右边并入左边兄弟父节点分隔当前节点和左兄弟的元素下移追加到左兄弟末尾把当前节点的元素全部追加到左兄弟后面如果是非叶子节点当前节点所有孩子节点也全部移交左兄弟同步修改孩子节点的双亲指针父节点数组中下移元素之后的所有元素及其孩子指针整体前移一位填补空位更新左兄弟有效元素个数释放被合并的当前节点父节点有效元素个数 - 1把父节点作为新的待检查节点回到循环开头判断父节点是否下溢和右兄弟合并当前节点在左边吸收右侧兄弟父节点分隔当前节点和右兄弟的元素下移追加到当前节点末尾。把右兄弟的元素全部追加到当前节点后面。如果是非叶子节点右兄弟所有孩子节点也全部移交当前节点同步修改孩子节点的双亲指针父节点数组中下移元素之后的所有元素及其孩子指针整体前移一位填补空位更新当前节点有效元素个数释放被合并的右兄弟父节点有效元素个数 - 1把父节点作为新的待检查节点回到循环开头判断父节点是否下溢注意如果一路向上调整到父节点为空当前节点是根节点 根节点的元素个数下限是 1。 如果根节点元素被删到 0直接把根唯一的子孩子升级成新根释放旧根新根的双亲指针置空调整结束。1删除操作函数// B树删除操作 bool Delete_BT(BTree* pTree, ElemType key) { if (pTree NULL || pTree-root NULL) return false; // 查找目标 Result* res Search_BT(pTree-root, key); if (res NULL || res-tag false) { // 不存在释放res free(res); return false; } BTNode* p res-pNode; int pos res-index; free(res); // 情况1非叶子节点找前驱/后继顶替 if (p-ptr_arr[0] ! NULL) { // 取直接前驱左子树最右端节点 BTNode* pre p-ptr_arr[pos - 1]; while (pre-ptr_arr[pre-key_num] ! NULL) { pre pre-ptr_arr[pre-key_num]; } // 顶替 p-key_arr[pos] pre-key_arr[pre-key_num]; // 要删除的节点变成前驱叶子节点位置是最后一个关键字 p pre; pos pre-key_num; } // 情况2叶子节点直接删除后面元素前移 for (int i pos; i p-key_num - 1; i) { p-key_arr[i] p-key_arr[i 1]; } p-key_num--; // 删除完成判断是否下溢触发调整 Delete_Adjust_BorrowMerge(pTree, p); return true; }2工具函数调整函数// 删除后的调整入口循环处理下溢支持向上传递 void Delete_Adjust_BorrowMerge(BTree* pTree, BTNode* node) { // M5最小关键字数ceil(5/2)-1 2key_num 2 下溢 const int MIN_KEY (M 1) / 2 - 1; while (node ! NULL node-key_num MIN_KEY) { BTNode* father node-parent; // 根节点下溢根没有父节点根可以少于最小限制直接退出 if (father NULL) { // 根节点关键字为0把它的第一个孩子作为新根释放旧根 if (node-key_num 0) { pTree-root node-ptr_arr[0]; if (pTree-root ! NULL) pTree-root-parent NULL; free(node); } break; } // 找到node是父节点的第几个孩子 index int index 0; while (father-ptr_arr[index] ! node) { index; } BTNode* leftBro (index 0) ? father-ptr_arr[index - 1] : NULL; BTNode* rightBro (index father-key_num) ? father-ptr_arr[index 1] : NULL; // 优先尝试向兄弟借 if (leftBro ! NULL leftBro-key_num MIN_KEY) { Borrow_LeftBro(node, leftBro, father, index - 1); break; } if (rightBro ! NULL rightBro-key_num MIN_KEY) { Borrow_RightBro(node, rightBro, father, index); break; } // 借不到执行合并合并后父节点可能下溢继续循环node更新为father if (leftBro ! NULL) { node Merge_LeftBro(node, leftBro, father, index - 1); } else if (rightBro ! NULL) { node Merge_RightBro(node, rightBro, father, index); } } }3工具函数借操作函数// 借操作函数和左兄弟借 void Borrow_LeftBro(BTNode* node, BTNode* LeftBro, BTNode* father, int index) { // 口诀父下来兄上去 // 1.将node节点现有的所有元素后移一位留出头部 for (int i node-key_num; i 1; i--) { node-key_arr[i 1] node-key_arr[i]; } // 如果是非叶子则还需要将其所有孩子右移 if (node-ptr_arr[0] ! NULL) { for (int i node-key_num; i 0; i--) { 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一来一回没变 LeftBro-key_num--; } // 和右兄弟借 void Borrow_RightBro(BTNode* node, BTNode* RightBro, BTNode* father, int index) { // 口诀父下来兄上去 // 1.父节点对应位置元素下移到node尾部 node-key_arr[node-key_num 1] father-key_arr[index 1]; // 2.右兄弟最小元素上移给父节点 father-key_arr[index 1] RightBro-key_arr[1]; // 3.接收右兄弟最左端的孩子非叶子才需要 if (RightBro-ptr_arr[0] ! NULL) { node-ptr_arr[node-key_num 1] RightBro-ptr_arr[0]; node-ptr_arr[node-key_num 1]-parent node; // 右兄弟内部元素、孩子整体前移补上空出来的位置 for (int i 1; i RightBro-key_num; i) { RightBro-key_arr[i] RightBro-key_arr[i 1]; } for (int i 0; i RightBro-key_num; i) { RightBro-ptr_arr[i] RightBro-ptr_arr[i 1]; } } else { // 叶子节点只前移关键字 for (int i 1; i RightBro-key_num; i) { RightBro-key_arr[i] RightBro-key_arr[i 1]; } } // 4.更新计数 node-key_num; RightBro-key_num--; }4工具函数合并操作函数// 和左兄弟合并node在右侧并入左边LeftBro BTNode* Merge_LeftBro(BTNode* node, BTNode* LeftBro, BTNode* father, int index) { // 口诀父下左右靠左 // 1.父节点index位置元素下移到左兄弟尾部 LeftBro-key_arr[LeftBro-key_num 1] father-key_arr[index]; // 2.把node里面全部关键字追加给左兄弟 for (int i 1; i node-key_num; i) { LeftBro-key_arr[LeftBro-key_num 1 i] node-key_arr[i]; } // 3.把node里面全部孩子追加给左兄弟非叶子 if (node-ptr_arr[0] ! NULL) { for (int i 0; i node-key_num; i) { LeftBro-ptr_arr[LeftBro-key_num 1 i] node-ptr_arr[i]; LeftBro-ptr_arr[LeftBro-key_num 1 i]-parent LeftBro; } } // 4.父节点关键字、孩子数组整体前移删掉下移走的那个位置 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 LeftBro-key_num 1 node-key_num; free(node); node NULL; father-key_num--; // 返回父节点外层循环继续判断父节点是否下溢 return father; } // 和右兄弟合并node在左侧吸收右边RightBro 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]; node-ptr_arr[node-key_num 1 i]-parent node; } } // 4.让父节点下来的那个元素的后续的元素及其孩子前移 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 1 RightBro-key_num; free(RightBro); RightBro NULL; father-key_num--; // 6.直接将其父节点返回让外层去判断是否出现了连续的下溢出 return father; }三、B树简单介绍一B树的由来在B树结构中当进行中序时需要来回往返于每个节点之间这也就意味着要在硬盘的页面之间进行多次访问这就使得效率很低。为了能解决这一问题在原有的B树结构基础上加上了新的元素组织方式这就是B树。二B树的概念B树是应文件系统所需而出的一种B树的变形树。在B树中每一个元素在该树中只出现一次有可能在叶子节点上也有可能在分支节点上而在B树中出现在分支节点中的元素会在该分支节点位置的中序后继者叶子节点中再次列出并且每一个叶子节点都会保存指向后一叶子节点的指针。三B树与 B-树差异叶子节点串联成双向链表B 树所有叶子节点之间通过指针相连从最左侧叶子可以顺着链表一路访问到最右侧叶子这是 B - 树完全没有的结构。数据全部下沉到叶子节点B 树的所有真实有效元素、磁盘记录地址全部保存在叶子节点中上层非叶子节点仅仅是索引节点只存放索引关键字用来加速查找不存储完整的数据记录。关键字重复出现B - 树中任意一个关键字在整棵树里只会存在唯一一份 B 树里同一个关键字可以在索引层非叶子节点和叶子节点重复出现索引层的关键字只是 “路标”真正的数据副本在叶子节点层。B 树做范围查询、顺序遍历非常方便找到范围起点的叶子节点之后直接沿着叶子链表向右遍历不需要再递归回溯树四B树的节点设计1.有效节点结构体设计typedef int ElemType; #define M 5 //磁盘中的记录写一个泛型 //记录集结构体 typedef struct {} Record; typedef enum { LEAF, BRANCH }NodeType; //B树的有效节点结构体设计 typedef struct BPlusNode { int key_num; //1.当前节点有效元素个数 ElemType key_arr[M 1]; //2.一个存储若干个有效元素的数组 struct BPlusNode* ptr_arr[M 1];//3.一个存储若干个指向其孩子节点的指针的数组 struct BPlusNode* parent; //4.双亲指针 Record* recptr[M 1]; //5.存储每一个元素所对应的在磁盘上的记录的指针的数组 NodeType type; //标签标识当前节点是叶节点还是非叶结点 struct BPlusNode* prev; //前驱指针叶子双向链表 struct BPlusNode* next; //后继指针叶子双向链表 }BPlusNode;2.辅助节点结构体设计//B树的辅助节点结构体设计 typedef struct BPlusTree { BPlusNode* root; //指向根节点 BPlusNode* first; //指向最小的叶节点叶子链表头 }BPlusTree;3.返回值结构体设计//查找函数的返回值结构体设计 typedef struct Result { bool tag; BPlusNode* pNode; int index; }Result; 
长河君 · 2026/10/23 4:53:53 · 阅读 1.2k 数据结构——B树（B-树）与B+树
一、什么是B树一B树的由来二叉搜索树BST在极端情况下会退化成链表查询复杂度从O(logn)变为O(n)AVL树、红黑树优化了平衡问题但每个节点最多2个子节点当数据量非常庞大时树的高度也会非常大计算机存储分为内存和磁盘内存读写快但容量小磁盘容量大但读写慢。而树的每一层节点访问磁盘和内存都需要交互一次这也就意味着若树的高度非常高那么在数据查找时磁盘和内存的交互次数也会很多这就大大的较低了数据查询的效率。B树的核心思想放弃二叉分支采用多路分支让单个节点存储更多关键字拥有更多子节点极大降低了树的高度在进行查找时磁盘与内存的交互次数也会极大减少效率自然也会大幅提升二B树的概念B树也叫做B-树是一种平衡的多路查找树。m 阶的B树表示B树中的每个节点最多拥有 m 个子节点也就是最多可以向外伸出m个分支对应最多存储 m-1 个元素常用标准m阶B树元素个数上限元素个数下限根节点m - 11非根节点m - 1[m / 2] - 1 (向上取整)在实际工作或学习中B树都是奇数阶为主所以一般我们记忆非根节点的下限直接用M/2三B树的特性所有叶子节点全部在同一层m阶B树中任意非根节点的元素数量满足[m / 2] - 1 (向上取整) 元素个数 m-1根节点最少可以只有1个元素树非空时根节点若不是叶子节点至少拥有2个子节点也就是至少向外伸出2个分支拥有k个元素的非叶子节点必然拥有k1个子节点也就是必然向外伸出k1个分支元素与子节点有序对应节点内所有元素从小到大有序排列左子树所有元素 当前元素 右子树所有元素二、B树相关操作及代码实现一B树的节点定义1.有效节点结构体设计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.双亲指针 // 5.recptr数组每个元素对应的磁盘记录地址 }BTNode;假设为5阶B树M5每个节点最多存储4个元素最多可以向外伸出5个分支在设计有效节点时通常将数据域数组key_arr和孩子指针域数组ptr_arr的大小设为M1key_arr01 2 3 45 元素从1号下标开始存储ptr_arr0 1 2 3 45孩子节点指针从0下标开始存储这样的话如果当前元素自身在 key_arr 中下标是i则其对应的左子树在 ptr_arr 中的下标就是i - 1则其对应的右子树在 ptr_arr 中的下标就是i2.辅助节点结构体设计// B树的辅助节点结构体设计 typedef struct BTree { BTNode* root; // 根节点指针域 }BTree;3.返回值结构体设计因为查找的时候要返回的信息比较多找没找到、在哪个节点、在节点的第几个位置所以专门对返回值设计一个返回值结构体// 返回值结构体设计 typedef struct Result { bool tag; // 1.找没找到 BTNode* pNode; // 2.在哪个节点里面找到 int index; // 3.在当前节点的哪一个位置找到 }Result;tag true找到了目标值在 pNode 节点的 key_arr[index] 位置tag false没找到但是如果要插入这个值就应该插到 pNode 节点的 key_arr[index] 这个位置指向的节点肚子里面的第index下标上二工具函数1.购买新节点// 购买新节点 BTNode* BuyNode_BT() { BTNode* pnewnode (BTNode*)malloc(sizeof(BTNode)); if (pnewnode NULL) exit(EXIT_FAILURE); // 内存申请失败直接退出程序 // 将节点整块内存置0元素数量、数组、指针全部清零 memset(pnewnode, 0, sizeof(BTNode)); return pnewnode; }三相关函数1.初始化// 初始化 void Init_BTree(BTree* pTree) { // 断言树结构体指针非空 assert(pTree); // 初始化根节点为空树 pTree-root NULL; }2.查找// 查找在以root为根的B树中查找元素val返回查找结果结构体指针 Result* Search_BT(BTNode* root, ElemType val) { BTNode* p root; // p遍历当前节点 BTNode* pp NULL; // pp保存上一层节点查找失败时记录待插入的父节点 // 进入循环循环条件当前访问节点不为空 int i 1; while (p ! NULL) { // 从下标1开始从左至右遍历当前节点内所有有效值 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; } else { // 找到目标值val申请Result结构体保存查找信息并返回 Result* pr (Result*)malloc(sizeof(Result)); if (pr NULL) exit(EXIT_FAILURE); pr-tag true; // 标记查找成功 pr-pNode p; // 记录目标值所在节点 pr-index i; // 记录目标值在key_arr中的下标从1开始 return pr; } } // 内层循环结束进入对应子节点继续查找 pp p; // 保存当前节点作为父节点 p p-ptr_arr[i - 1]; // 跳转到对应子树继续搜索 } // 外层循环结束pNULL查找失败 Result* pr (Result*)malloc(sizeof(Result)); if (pr NULL) exit(EXIT_FAILURE); pr-tag false; // 标记查找失败 pr-pNode pp; // 记录待插入位置的父节点 pr-index i; // 记录在父节点中应该插入的位置 return pr; }3.打印// 中序遍历递归版本 void InOrder_BT(BTNode* root) { if (root NULL) return; // 依次访问第i个元素的左子树 for (int i 1; i root-key_num; i) { InOrder_BT(root-ptr_arr[i - 1]); // 递归遍历第i个元素左子树 printf(%d , root-key_arr[i]); // 打印当前元素 } // 遍历最右侧子树最后一个元素的右子树 InOrder_BT(root-ptr_arr[root-key_num]); }// 中序遍历递归版本写法2逻辑是一样的 void InOrder_BT2(BTNode* root) { if (root NULL) return; InOrder_BT2(root-ptr_arr[0]); // 访问第一个关键字左侧子树 for (int i 1; i root-key_num; i) { printf(%d , root-key_arr[i]); // 输出当前关键字 InOrder_BT2(root-ptr_arr[i]); // 访问当前关键字右侧子树 } }4.插入插入流程先调用查找函数查找关键字若关键字存在直接返回若关键字不存在则在返回的父节点中将大于目标值的关键字后移腾出空位插入新 key节点计数自增检查是否突破节点的元素上限上溢出若没有突破则无需调整若有突破则需要“分裂”分裂操作购买新节点 RightNode 放到当前待分裂节点 Node 的右侧找到待分裂节点 Node 的中位数位置将中位数右侧的所有元素以及对应的孩子指针全部迁移到 RightNode同步修改孩子节点的 parent 双亲指针将待分裂节点 Node 的中位数上移让其父节点接收如果父节点不存在说明当前 Node 节点是根节点需要再新建一个根节点newroot用于接收此时的中位数原根节点Node与 RightNode 作为新根节点的左右两个孩子如果父节点存在父节点内大于中位数的元素连同孩子指针整体右移插入中位数并将 RightNode 节点挂载到父节点上1插入操作函数// B树的插入 bool Insert_BT(BTree* pTree, ElemType key) { assert(pTree ! NULL); // 0.5 处理空树场景直接新建根节点存放key if (pTree-root NULL) { BTNode* pnewnode BuyNode_BT(); pnewnode-key_arr[1] key; pnewnode-key_num; pTree-root pnewnode; return true; } // 1.调用查找函数判断key是否已经存在同时拿到待插入位置信息返回值是一个Result结构体变量 Result*pr Search_BT(pTree-root, key); // 2.tag为true代表key值已存在不需要重复插入 if (pr-tag) return true; // 3.反之key值不存在将key值插入到pNode节点的第index下标上 // 大于key的关键字也就是index下标及后面的元素统一后移一位腾出插入位置index 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; // 插入完成当前节点关键字计数1 pr-pNode-key_num; // 4.判断是否上溢出如果上溢出了则直接调用分裂函数反之则无需调整直接结束 if (pr-pNode-key_num M) { Insert_Adjust_Split(pTree, pr-pNode); } return true; }2工具函数分裂函数// 分裂函数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]; RightNode-key_num ; // 更新RightNode的有效元素个数 } //3.5 如果待分裂节点Node不是叶子节点中位数右侧元素对应的孩子指针也要迁移到RightNode for (int i 0; i M/2; i) { RightNode-ptr_arr[i] Node-ptr_arr[mid i]; // 迁移孩子节点时同步更新孩子节点的父指针 if(RightNode-ptr_arr[i] ! NULL) RightNode-ptr_arr[i]-parent RightNode; } // 4.将待分裂节点Node的中位数上移交给父节点来接收 BTNode* father Node-parent; // 4.1 父节点为空代表当前分裂的是根节点需要新建新根节点 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; newroot-key_num; Node-key_num M / 2; // 更新Node节点的有效元素个数 // 更新左右孩子的双亲指针parent Node-parent RightNode-parent newroot; pTree-root newroot; return; } else { // 4.2 父节点存在把中位数插入父节点中大于中位数的元素连同子指针一起后移 int i father-key_num; for (; i 1; i--) { if (father-key_arr[i] Node-key_arr[mid]) { father-key_arr[i 1] father-key_arr[i]; father-ptr_arr[i 1] father-ptr_arr[i]; } else break; // 找到插入位置停止前移 } // 将中位数放入父节点腾出的空位 father-key_arr[i 1] Node-key_arr[mid]; father-ptr_arr[i 1] RightNode; RightNode-parent father; } // 5.父节点关键字数量1同时修改原节点的有效关键字个数只保留中位数左边 father-key_num; // 5.5 更新Node节点的有效元素个数 Node-key_num M / 2; // 6.父节点插入中位数后若出现溢出递归向上继续分裂 if (father-key_num M) Insert_Adjust_Split(pTree, father); }5.删除删除逻辑调用查找函数查找待删除值如果找不到目标值直接返回删除失败。如果目标值存在判断待删除值所在节点类型叶子节点直接删除目标值将它后面所有元素整体向前移动一位更新节点有效元素个数非叶子节点找到待删除值的直接前驱/直接后继用直接前驱/直接后继覆盖待删除值再直接删除直接前驱/直接后继待删除值的直接前驱/直接后继一定是叶子节点“狸猫换太子”删除完成后检查当前节点是否发生下溢出。没有下溢删除结束发生下溢则进入调整函数。下溢调整逻辑当有效节点的元素个数低于元素下限时则出现了下溢出需要对树进行调整优先向兄弟节点借元素借不到则执行节点合并方案1向兄弟节点借元素口诀父下来兄上去借关键字不会减少父节点关键字总数调整一次即可结束不需要继续向上传递下溢。和左兄弟借左兄弟关键字充足大于节点元素个数下限借出一个元素后不会出现下溢出当前节点内部所有元素向后挪一位头部留出空位非叶子节点的孩子指针也要同步后移父节点中分隔当前节点和左兄弟的元素下移放到当前节点的头部空位左兄弟最右侧元素上移放到父节点刚才空出来的位置如果左兄弟是非叶子节点左兄弟最右侧的孩子节点过继给当前节点作为最左侧孩子节点并修改该孩子节点的双亲指针更新两个节点的有效元素个数当前节点 1左兄弟 - 1和右兄弟借右兄弟关键字充足大于节点元素个数下限借出一个元素后不会出现下溢出父节点中分隔当前节点和右兄弟的元素下移放到当前节点末尾右兄弟最左侧元素上移填补父节点空出的位置如果右兄弟是非叶子节点右兄弟最左侧的孩子节点过继给当前节点作为新的末尾孩子并修改该孩子节点的双亲指针右兄弟内部所有元素、孩子指针整体前移填补头部空位更新两个节点的有效元素个数当前节点 1右兄弟 - 1方案2节点合并口诀父下左右靠左当左右兄弟元素个数都刚好等于下限没有多余元素可以借出只能合并。 合并会拿走父节点里的一个元素父节点关键字数量减一有可能引发父节点下溢循环向上调整。和左兄弟合并当前节点在右边并入左边兄弟父节点分隔当前节点和左兄弟的元素下移追加到左兄弟末尾把当前节点的元素全部追加到左兄弟后面如果是非叶子节点当前节点所有孩子节点也全部移交左兄弟同步修改孩子节点的双亲指针父节点数组中下移元素之后的所有元素及其孩子指针整体前移一位填补空位更新左兄弟有效元素个数释放被合并的当前节点父节点有效元素个数 - 1把父节点作为新的待检查节点回到循环开头判断父节点是否下溢和右兄弟合并当前节点在左边吸收右侧兄弟父节点分隔当前节点和右兄弟的元素下移追加到当前节点末尾。把右兄弟的元素全部追加到当前节点后面。如果是非叶子节点右兄弟所有孩子节点也全部移交当前节点同步修改孩子节点的双亲指针父节点数组中下移元素之后的所有元素及其孩子指针整体前移一位填补空位更新当前节点有效元素个数释放被合并的右兄弟父节点有效元素个数 - 1把父节点作为新的待检查节点回到循环开头判断父节点是否下溢注意如果一路向上调整到父节点为空当前节点是根节点 根节点的元素个数下限是 1。 如果根节点元素被删到 0直接把根唯一的子孩子升级成新根释放旧根新根的双亲指针置空调整结束。1删除操作函数// B树删除操作 bool Delete_BT(BTree* pTree, ElemType key) { if (pTree NULL || pTree-root NULL) return false; // 查找目标 Result* res Search_BT(pTree-root, key); if (res NULL || res-tag false) { // 不存在释放res free(res); return false; } BTNode* p res-pNode; int pos res-index; free(res); // 情况1非叶子节点找前驱/后继顶替 if (p-ptr_arr[0] ! NULL) { // 取直接前驱左子树最右端节点 BTNode* pre p-ptr_arr[pos - 1]; while (pre-ptr_arr[pre-key_num] ! NULL) { pre pre-ptr_arr[pre-key_num]; } // 顶替 p-key_arr[pos] pre-key_arr[pre-key_num]; // 要删除的节点变成前驱叶子节点位置是最后一个关键字 p pre; pos pre-key_num; } // 情况2叶子节点直接删除后面元素前移 for (int i pos; i p-key_num - 1; i) { p-key_arr[i] p-key_arr[i 1]; } p-key_num--; // 删除完成判断是否下溢触发调整 Delete_Adjust_BorrowMerge(pTree, p); return true; }2工具函数调整函数// 删除后的调整入口循环处理下溢支持向上传递 void Delete_Adjust_BorrowMerge(BTree* pTree, BTNode* node) { // M5最小关键字数ceil(5/2)-1 2key_num 2 下溢 const int MIN_KEY (M 1) / 2 - 1; while (node ! NULL node-key_num MIN_KEY) { BTNode* father node-parent; // 根节点下溢根没有父节点根可以少于最小限制直接退出 if (father NULL) { // 根节点关键字为0把它的第一个孩子作为新根释放旧根 if (node-key_num 0) { pTree-root node-ptr_arr[0]; if (pTree-root ! NULL) pTree-root-parent NULL; free(node); } break; } // 找到node是父节点的第几个孩子 index int index 0; while (father-ptr_arr[index] ! node) { index; } BTNode* leftBro (index 0) ? father-ptr_arr[index - 1] : NULL; BTNode* rightBro (index father-key_num) ? father-ptr_arr[index 1] : NULL; // 优先尝试向兄弟借 if (leftBro ! NULL leftBro-key_num MIN_KEY) { Borrow_LeftBro(node, leftBro, father, index - 1); break; } if (rightBro ! NULL rightBro-key_num MIN_KEY) { Borrow_RightBro(node, rightBro, father, index); break; } // 借不到执行合并合并后父节点可能下溢继续循环node更新为father if (leftBro ! NULL) { node Merge_LeftBro(node, leftBro, father, index - 1); } else if (rightBro ! NULL) { node Merge_RightBro(node, rightBro, father, index); } } }3工具函数借操作函数// 借操作函数和左兄弟借 void Borrow_LeftBro(BTNode* node, BTNode* LeftBro, BTNode* father, int index) { // 口诀父下来兄上去 // 1.将node节点现有的所有元素后移一位留出头部 for (int i node-key_num; i 1; i--) { node-key_arr[i 1] node-key_arr[i]; } // 如果是非叶子则还需要将其所有孩子右移 if (node-ptr_arr[0] ! NULL) { for (int i node-key_num; i 0; i--) { 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一来一回没变 LeftBro-key_num--; } // 和右兄弟借 void Borrow_RightBro(BTNode* node, BTNode* RightBro, BTNode* father, int index) { // 口诀父下来兄上去 // 1.父节点对应位置元素下移到node尾部 node-key_arr[node-key_num 1] father-key_arr[index 1]; // 2.右兄弟最小元素上移给父节点 father-key_arr[index 1] RightBro-key_arr[1]; // 3.接收右兄弟最左端的孩子非叶子才需要 if (RightBro-ptr_arr[0] ! NULL) { node-ptr_arr[node-key_num 1] RightBro-ptr_arr[0]; node-ptr_arr[node-key_num 1]-parent node; // 右兄弟内部元素、孩子整体前移补上空出来的位置 for (int i 1; i RightBro-key_num; i) { RightBro-key_arr[i] RightBro-key_arr[i 1]; } for (int i 0; i RightBro-key_num; i) { RightBro-ptr_arr[i] RightBro-ptr_arr[i 1]; } } else { // 叶子节点只前移关键字 for (int i 1; i RightBro-key_num; i) { RightBro-key_arr[i] RightBro-key_arr[i 1]; } } // 4.更新计数 node-key_num; RightBro-key_num--; }4工具函数合并操作函数// 和左兄弟合并node在右侧并入左边LeftBro BTNode* Merge_LeftBro(BTNode* node, BTNode* LeftBro, BTNode* father, int index) { // 口诀父下左右靠左 // 1.父节点index位置元素下移到左兄弟尾部 LeftBro-key_arr[LeftBro-key_num 1] father-key_arr[index]; // 2.把node里面全部关键字追加给左兄弟 for (int i 1; i node-key_num; i) { LeftBro-key_arr[LeftBro-key_num 1 i] node-key_arr[i]; } // 3.把node里面全部孩子追加给左兄弟非叶子 if (node-ptr_arr[0] ! NULL) { for (int i 0; i node-key_num; i) { LeftBro-ptr_arr[LeftBro-key_num 1 i] node-ptr_arr[i]; LeftBro-ptr_arr[LeftBro-key_num 1 i]-parent LeftBro; } } // 4.父节点关键字、孩子数组整体前移删掉下移走的那个位置 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 LeftBro-key_num 1 node-key_num; free(node); node NULL; father-key_num--; // 返回父节点外层循环继续判断父节点是否下溢 return father; } // 和右兄弟合并node在左侧吸收右边RightBro 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]; node-ptr_arr[node-key_num 1 i]-parent node; } } // 4.让父节点下来的那个元素的后续的元素及其孩子前移 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 1 RightBro-key_num; free(RightBro); RightBro NULL; father-key_num--; // 6.直接将其父节点返回让外层去判断是否出现了连续的下溢出 return father; }三、B树简单介绍一B树的由来在B树结构中当进行中序时需要来回往返于每个节点之间这也就意味着要在硬盘的页面之间进行多次访问这就使得效率很低。为了能解决这一问题在原有的B树结构基础上加上了新的元素组织方式这就是B树。二B树的概念B树是应文件系统所需而出的一种B树的变形树。在B树中每一个元素在该树中只出现一次有可能在叶子节点上也有可能在分支节点上而在B树中出现在分支节点中的元素会在该分支节点位置的中序后继者叶子节点中再次列出并且每一个叶子节点都会保存指向后一叶子节点的指针。三B树与 B-树差异叶子节点串联成双向链表B 树所有叶子节点之间通过指针相连从最左侧叶子可以顺着链表一路访问到最右侧叶子这是 B - 树完全没有的结构。数据全部下沉到叶子节点B 树的所有真实有效元素、磁盘记录地址全部保存在叶子节点中上层非叶子节点仅仅是索引节点只存放索引关键字用来加速查找不存储完整的数据记录。关键字重复出现B - 树中任意一个关键字在整棵树里只会存在唯一一份 B 树里同一个关键字可以在索引层非叶子节点和叶子节点重复出现索引层的关键字只是 “路标”真正的数据副本在叶子节点层。B 树做范围查询、顺序遍历非常方便找到范围起点的叶子节点之后直接沿着叶子链表向右遍历不需要再递归回溯树四B树的节点设计1.有效节点结构体设计typedef int ElemType; #define M 5 //磁盘中的记录写一个泛型 //记录集结构体 typedef struct {} Record; typedef enum { LEAF, BRANCH }NodeType; //B树的有效节点结构体设计 typedef struct BPlusNode { int key_num; //1.当前节点有效元素个数 ElemType key_arr[M 1]; //2.一个存储若干个有效元素的数组 struct BPlusNode* ptr_arr[M 1];//3.一个存储若干个指向其孩子节点的指针的数组 struct BPlusNode* parent; //4.双亲指针 Record* recptr[M 1]; //5.存储每一个元素所对应的在磁盘上的记录的指针的数组 NodeType type; //标签标识当前节点是叶节点还是非叶结点 struct BPlusNode* prev; //前驱指针叶子双向链表 struct BPlusNode* next; //后继指针叶子双向链表 }BPlusNode;2.辅助节点结构体设计//B树的辅助节点结构体设计 typedef struct BPlusTree { BPlusNode* root; //指向根节点 BPlusNode* first; //指向最小的叶节点叶子链表头 }BPlusTree;3.返回值结构体设计//查找函数的返回值结构体设计 typedef struct Result { bool tag; BPlusNode* pNode; int index; }Result;