B 树（B - 树）全网最透彻精讲：原理 + 插入分裂 + 删除合并 + 完整工程级代码逐行解析

前言

B 树是为磁盘、文件系统、数据库索引而生的平衡多路查找树。

它解决了二叉树（AVL / 红黑树）树层高、IO 次数多、查询慢的问题。

• MySQL InnoDB 索引底层 =B+ 树
• 文件系统、NTFS、Ext4 =B 树 / B+ 树

一、什么是 B 树？（一句话定义）

B 树 = 多路平衡查找树

一个节点可以存多个关键字，拥有多个孩子，保证树极矮、磁盘 IO 极少。

二、5 阶 B 树核心规则（必须背）

M=5 阶 B 树，规则如下：

1. 每个节点关键字个数范围
   • 非根节点：⌈5/2⌉ - 1 = 2 ~ 4
   • 根节点：1 ~ 4
2. 关键字有序排列（左小右大）
3. 子节点数 = 关键字数 + 1
4. 所有叶子节点在同一层（绝对平衡）
5. 上溢出：关键字 = 5 →分裂
6. 下溢出：关键字 < 2 →借节点 / 合并

三、B 树结构体设计

#define M 5 // 5阶B树 // B树节点 typedef struct BTNode { int key_num; // 有效关键字个数 ELEMTYPE keys[M + 1]; // 关键字数组[1~4]可用，0和5做哨兵 struct BTNode* parent; // 双亲指针 struct BTNode* ptr[M + 1]; // 孩子指针数组 } BTNode; // B树管理结构 typedef struct { BTNode* root; } BTree; // 查找结果结构体 typedef struct Result { BTNode* pNode; int index; bool tag; // true=找到 false=没找到(返回插入位置) } Result;

头文件：

#pragma once #define M 5//阶数 typedef int ELEMTYPE; typedef struct {} Record; //B树的有效节点结构体定义 struct BTNode { int key_num;//元素的个数 ELEMTYPE keys[M + 1];//用来存储关键码/元素 //一共能用4个格子 但是申请了6个 最开始和最后的两个格子当成哨兵，实现代码更方便 struct BTNode* parent;//双亲指针 struct BTNode* ptr[M + 1];//用来存储孩子 //末尾的下标M格子当做哨兵 //Record* recptr[M + 1];//存储记录的指针 }; typedef struct BTNode BTNode; /* keys: 0 [1 2 3 4] 5 ptr: [0 1 2 3 4] 5 recptr: 0 [1 2 3 4] 5 */ //B树的辅助节点结构体定义： typedef struct { BTNode* root; // 树的根 //cursize; }BTree; //单独设计一个专门用于查找返回结构的结构体 typedef struct Result { BTNode* pNode;// int index; bool tag;// true=找到，false=没找到（返回插入位置） }Result; /* 若第三个参数 bool tag 为真： 此时pNode所代表的意思就是这个元素所在的节点位置 此时index所代表的意思就是这个元素是pNode这个节点的第几个有效值 若第三个参数 bool tag 为假： 此时pNode所代表的意思就是这个元素所应该插入的节点位置 此时index所代表的意思就是这个元素应该插入到pNode这个节点的第几个有效值 */ //实现的函数： //工具函数 //1.申请Result结构体变量，用于节点查找结构的返回 Result* Buy_ResultNode(); //2.购买新节点，用于分裂 BTNode* Buy_Node(); //3.插入的调整函数(可能不止一次的上溢出，所以分裂也可能不止一次) void Insert_Adjust(BTree* pTree, BTNode* node); //4.插入的单次分裂(上溢出了，需要一次分裂) BTNode* SplitNode(BTree* pTree, BTNode* node); //普通函数 //1.初始化 void Init_BTree(BTree* pTree); //2.查找 Result* Search_BTree(BTree* pTree, ELEMTYPE val); //3.插入 bool Insert_BTree(BTree* pTree, ELEMTYPE val); //5.打印(中序遍历) void Show_InOrder(BTNode* root);//递归 //4.删除 bool Delete_BTree(BTree* pTree, ELEMTYPE val); //5.删除的调整函数 void Delete_Adjust(BTree* pTree, BTNode* Node); //6.问兄弟借元素(通用的)//pp是，当前节点和借的兄弟节点的父节点 index：当前节点和借的兄弟节点夹住的父节点的元素下标 //7.从左兄弟借 void BorrowFrom_LeftBro(BTNode* pp, int index); //8.从右兄弟借 void BorrowFrom_RightBro(BTNode* pp, int index); //问兄弟借操作，父节点不会少元素，所以不需要进行连续的下溢出判断 //但是和兄弟合并操作，父节点会少一个元素，所以需要进行连续的下溢出判断 //9.和左兄弟合并 (把合并之后的节点返回出来) BTNode* Merge_LeftBro(BTNode* pp, int index); //10.和右兄弟合并 BTNode* Merge_RightBro(BTNode* pp, int index);

四、B 树核心工具函数

1. 申请新节点

//2.购买新节点，用于分裂 BTNode* Buy_Node() { BTNode* pnewnode = (BTNode*)malloc(sizeof(BTNode)); if (pnewnode == NULL) exit(EXIT_FAILURE); memset(pnewnode, 0, sizeof(BTNode)); return pnewnode; }

2. 节点分裂（插入上溢出）

分裂规则：中间关键字上浮，左右拆分

• 右半部分拷贝给新节点
• 孩子指针同步迁移并更新双亲
• 中间值插入父节点
• 父节点可能继续溢出

//4.插入的单次分裂(上溢出了，需要一次分裂) BTNode* SplitNode(BTree* pTree, BTNode* node) { //1.购买一个新的分裂节点 RightNode BTNode* RightNode = Buy_Node(); //2.拷贝节点node的中间靠右一侧的元素值，到RightNode里面去 //将node节点后面的M/2个有效元素，挪动到RightNode里面去 for (int i = 1; i <= M / 2; i++)//i指向右侧RightNode的插入下标 { RightNode->keys[i] = node->keys[i + M / 2 + 1]; } //3.拷贝节点node的中间靠右一侧的孩子指针，到RightNode里面去 for (int i = 0; i <= M / 2; i++) { RightNode->ptr[i] = node->ptr[i + M / 2 + 1]; //****容易出现bug //分裂的若不是叶子结点，则其孩子指针指向的节点有可能存在，存在的话，就得更新这些存在的孩子节点的双亲 if (RightNode->ptr[i] != NULL) { RightNode->ptr[i]->parent = RightNode; } } //4.更新/修正node节点和RightNode节点里面的一些参数 //4.1 更新他俩的key_num node->key_num = M / 2; RightNode->key_num = M / 2; //5.申请一个临时变量father 指向分裂后，中间元素向上挪动的那个节点 BTNode* father = node->parent;//有可能为NULL //6.再申请一个临时变量tmp，用来保存分裂后中间的元素值 ELEMTYPE tmp = node->keys[M / 2 + 1]; //7.father 若不存在，怎么处理 if (father == NULL) { BTNode* newroot = Buy_Node(); //修正新根的元素值 newroot->keys[1] = tmp; //修正新根的元素值个数 newroot->key_num = 1; //修正新根的孩子指针 newroot->ptr[0] = node; newroot->ptr[1] = RightNode; //修正新根的双亲指针 newroot->parent = NULL; //修正node和RightNode的双亲指针 node->parent = newroot; RightNode->parent = newroot; return newroot; } //8.father 若存在，怎么处理 //对于父节点，从后向前依次和tmp值进行比较，若大于tmp，则向后挪动 //目的：给tmp把合适的插入位置让出来 int k = father->key_num;//让k一开始指向父节点最后一个有效元素的下标 for (; k >= 1; k--) { if (father->keys[k] > tmp) { father->keys[k + 1] = father->keys[k]; father->ptr[k + 1] = father->ptr[k]; } else { break;//停下来，插入值 } } //9.此时将tmp已经插入到father节点里面了，这时还需要将分裂出来的RightNode节点挂载到father里面的ptr[]里面 father->keys[k + 1] = tmp; father->ptr[k + 1] = RightNode; //10.修正father，node，RightNode这三个节点里面的一些参数 father->key_num += 1; RightNode->parent = father; //11.结束，返回father return father; }

3. 插入调整（循环分裂）

//3.插入的调整函数(可能不止一次的上溢出，所以分裂也可能不止一次) void Insert_Adjust(BTree* pTree, BTNode* node) { while (node->key_num >= M) { node = SplitNode(pTree, node); } //根节点有可能也上溢出，导致我们需要创建一个新根，让出来让node接收 //此时node有可能指向的是新根节点 也有可能指向的是老根节点 if (node->key_num == 1)//新根的有效元素个数肯定等于1 { pTree->root = node; } }

五、B 树插入（最常考）

插入流程：

1. 查找 → 没找到则插入叶子节点
2. 插入后判断是否上溢出（key_num == 5）
3. 溢出 → 调用Insert_Adjust分裂
4. 分裂可能向上传递，直到根节点

//3.插入 bool Insert_BTree(BTree* pTree, ELEMTYPE val) { //0.先去判断是否是一颗空B树 if (pTree->root == NULL) { BTNode* pnewnode = Buy_Node(); pnewnode->keys[1] = val; pnewnode->key_num++; pTree->root = pnewnode; return true; } Result* p = Search_BTree(pTree, val); if (p->tag == true) { return true; } //不是一颗空树，还找不到，该插入了 //并且此时 p->pNode==刚好是插入的节点 // p->index==刚好是节点的插入元素下标 //将index后边的元素统一向后挪动，给val值留下空闲格子 for (int i = p->pNode->key_num; i >= p->index; i--) p->pNode->keys[i + 1] = p->pNode->keys[i]; //将值插入 p->pNode->keys[p->index] = val; //修正p->pNode成员 p->pNode->key_num++; //插入后，看是否上溢出 if (p->pNode->key_num == M) { Insert_Adjust(pTree, p->pNode); } return true; }

插入是 B 树最简单的操作，只分裂、不合并！

六、B 树查找（非递归）

//2.查找 Result* Search_BTree(BTree* pTree, ELEMTYPE val)//非递归 { //0.assert //1.申请两个指针p和pp p用来从根节点开始向下去遍历 pp用来指向当val值不存在的合适的插入节点 BTNode* p = pTree->root; BTNode* pp = NULL; //2.提前先购买好 查找返回结构结构体变量 Result* pr = Buy_ResultNode(); //3.再申请一个临时变量i i用来对于每一个节点里面的元素从左至右的比较 int i = 1; //4.进入到while循环，循环的条件是p指向的节点存在即可 while (p != NULL) { //5.每一个新节点，都需要将i重新置为1 i = 1; //6.通过内层while循环，去找一个大于或者等于val值的元素 while (i <= p->key_num && p->keys[i] < val) i++; //7.当内层while结束 有两个可能性：可能1：i越界了 可能2：i没越界，确实找到了一个大于或者等于val的元素 //7.1 对应的是 可能2里面的：i没越界，确实找到了一个等于val的元素，找到了，直接返回 if (p->keys[i] == val)//找到了 { //此时购买一个result结构体变量，扔出去 break; } //7.2 对应的是 可能2里面的：i没越界，确实找到了一个大于val的元素，找到了，直接返回 //7.3 对应的是 可能1里面的i越界(和7.2对应 处理方式代码一样，则只留一份) pp = p; p = p->ptr[i - 1]; } //8.当外层while循环结束，肯定没找大 直接返回result结构体变量 //8.1 修正pr->tag //8.2 修正pr->pNode if (p == NULL)//没找到 { pr->tag = false; pr->pNode = pp; } else//找到了 { pr->tag = true; pr->pNode = p; } //8.3 修正pr->idnex pr->index = i; return pr; }

• 非递归高效
• 返回节点、下标、是否找到
• 直接给插入位置，完美支持插入

七、B 树删除（数据结构最难之一）

删除流程：

1. 查找，不存在直接返回
2. 非叶子节点→ 用后继替换，转为删叶子
3. 删除叶子节点
4. 判断是否下溢出（key_num < 2）
5. 下溢出处理：
   • 先看左兄弟够借
   • 再看右兄弟够借
   • 都不够 → 与兄弟合并
6. 合并会导致父节点减少 → 可能继续下溢

4 大核心删除函数：

//4.删除 bool Delete_BTree(BTree* pTree, ELEMTYPE val) { //0.assert 安全性处理 assert(pTree != NULL); //1.判断val值是否在B-树中存在，若不存在，直接结束，返回true Result* pr = Search_BTree(pTree, val); if (!pr->tag) { return true; } //2.若val值存在，则应该删除，首先去判断该值是否在叶子结点上还是在非叶子结点上 //3.如果在非叶子节点上，则需要狸猫换太子(用前驱或者后继将其替换掉 if (pr->pNode->ptr[0] != NULL) { BTNode* cat = pr->pNode->ptr[pr->index]; while (cat->ptr[0] != NULL) cat = cat->ptr[0]; pr->pNode->keys[pr->index] = cat->keys[1]; //此时，修改pr里的值，让pr保存待删除元素所在的节点位置和元素下标位置 pr->pNode = cat; pr->index = 1; } //4.这次，所有的情况全部就会转化为删除叶子结点上的元素了 //5.待删除元素在叶子结点上 --> 则直接删除，但是别忘了，需要判断是否下溢出 BTNode* p = pr->pNode; //index位置后的所有元素统一前移一个格子 for (int i = pr->index + 1; i <= p->key_num; i++) { p->keys[i - 1] = p->keys[i]; } p->key_num--; //此时有4种情况 // 第一种情况：根节点--溢出 --> 直接释放+结束 // 第二种情况：根节点--没有溢出 --> 无调整 // 第三种情况：非根节点----没有溢出 --> 无调整 // 第四种情况：非根节点----溢出 --> 需要调整(执行调整函数) //6.如果该节点没有下溢出 --> 则无需调整，直接结束 if ((p->parent == NULL && p->key_num >= 1) || (p->parent != NULL && p->key_num >= M / 2)) { //无需调整 return true; } if (p->parent == NULL && p->key_num == 0) { free(p); free(pr); pTree->root = NULL; return true; } Delete_Adjust(pTree, p); return true; } //5.删除的调整函数 void Delete_Adjust(BTree* pTree, BTNode* Node) { //0.assert //1.申请一个指针，用来指向Node的父节点 BTNode* father = Node->parent; //2.方法1：通过Node地址的比较，判断出，当前Node在父节点中第几个下标上 // 方法2：通过Node的元素比较，判断出，当前Node在父节点中第几个下标上 //用2：思路就是父节点里面找第一个大于我当前Node节点里的第一个元素的值 int i = 1; for (; i <= father->key_num; i++) { if (father->keys[i] > Node->keys[1])//找到了第一个大于我当前Node节点里的元素的值 { break; } } //3.再申请两个指针，用来指向Node的左右兄弟 //注意：左右兄弟是有可能不存在的 BTNode* LeftBro = i - 2 >= 0 ? father->ptr[i - 2] : NULL; BTNode* RightBro = i <= father->key_num ? father->ptr[i] : NULL; //如果真的下溢出了，观察其左右兄弟是否存在且够借，如果够借，则问兄弟借，直接结束(口诀：父下来，兄上去) //4.尽量先看左兄弟是否存在且够借，如果存在且够借，则直接先问左兄弟借 if (LeftBro != NULL && LeftBro->key_num > M / 2) { BorrowFrom_LeftBro(father, i - 1); return; } //5.再问右兄弟借(如果右兄弟存在且够借的情况下) else if (RightBro != NULL && RightBro->key_num > M / 2) { BorrowFrom_RightBro(father, i); return; } //6.执行到这里，就说明左右兄弟要么不存在，要么存在但是不够给我借元素 else { //7.只能和左右兄弟进行合并了(口诀：父下左，右靠左) //7.5 准备工作：申请一个指针ptr，用来接收合并操作返回的合并的节点 BTNode* ptr = NULL; //8.1 只有左兄弟存在-->只能和左兄弟合并 //8.2 左右兄弟都存在-->和左兄弟合并 if (LeftBro != NULL) { ptr = Merge_LeftBro(father, i - 1); } //8.3 只有右兄弟存在-- > 只能和右兄弟合并 else { ptr = Merge_RightBro(father, i); } //注意：非根节点，不会存在左右兄弟都不存在的情况，至少得有一个兄弟存在 //9.合并操作是会导致父节点缺少一个元素，所以可能会导致父节点出现连续的 // 下溢出，则小心判断父节点，看是否需要继续处理 //9.1 father是根节点 -> 溢出 -> 调整处理 //10.特殊情况：如果合并操作导致根节点空了，没有元素了，则需要释放此时的根节点，让刚刚合并的节点看做新的根节点即可 if (father->parent == NULL && father->key_num < 1) { free(father); pTree->root = ptr; ptr->parent = NULL; } //9.2 father是非根节点 -> 溢出 -> 调整处理 else if (father->parent != NULL && father->key_num < M / 2) { Delete_Adjust(pTree, father); } //9.3 father是根节点 -> 没有溢出 -> 不需要调整处理 //9.4 father是非根节点 -> 没有溢出 -> 不需要调整处理 else { return; } } } //7.从左兄弟借 void BorrowFrom_LeftBro(BTNode* pp, int index) { assert(index >= 1 && index <= pp->key_num); //1.先通过pp和index找到自己和左兄弟节点 BTNode* child = pp->ptr[index]; BTNode* leftBro = pp->ptr[index - 1]; //2.将父节点的值拉下来(口诀：父下来) for (int i = child->key_num; i >= 1; i--) child->keys[i + 1] = child->keys[i]; child->keys[1] = pp->keys[index]; //如果兄弟不是叶子结点(换句话说，兄弟有子树) if (leftBro->ptr[0] != NULL) { for (int i = child->key_num; i >= 0; i--) child->ptr[i + 1] = child->ptr[i]; child->ptr[0] = leftBro->ptr[leftBro->key_num]; } //3.将兄弟节点的值，挪上去到父节点 pp->keys[index] = leftBro->keys[leftBro->key_num]; //更新各个节点的有效元素个数 child->key_num += 1; leftBro->key_num -= 1; } //8.从右兄弟借 void BorrowFrom_RightBro(BTNode* pp, int index) { assert(index >= 1 && index <= pp->key_num); //1.先通过pp和index找到自己和右兄弟节点 BTNode* child = pp->ptr[index - 1]; BTNode* rightBro = pp->ptr[index]; //2.将父节点的值拉下来(口诀：父下来) child->keys[child->key_num + 1] = pp->keys[index]; //3.将兄弟节点的值，挪上去到父节点 pp->keys[index] = rightBro->keys[1]; //4.若如果兄弟不是叶子结点(换句话说，兄弟有子树) //则把右兄弟的第一个孩子指针域，挪动到自己的最后一个指针域位置 if (rightBro->ptr[0] != NULL) { child->ptr[child->key_num + 1] = rightBro->ptr[0]; } //5.修正右兄弟节点的元素值和孩子指针域 for (int i = 2; i <= rightBro->key_num; i++) rightBro->keys[i - 1] = rightBro->keys[i]; for (int i = 1; i <= rightBro->key_num; i++) rightBro->ptr[i - 1] = rightBro->ptr[i]; //6.修正更新各个节点的有效元素个数 child->key_num += 1; rightBro->key_num -= 1; } //问兄弟借操作，父节点不会少元素，所以不需要进行连续的下溢出判断 //但是和兄弟合并操作，父节点会少一个元素，所以需要进行连续的下溢出判断 //9.和左兄弟合并 (把合并之后的节点返回出来) BTNode* Merge_LeftBro(BTNode* pp, int index) { //0.assert assert(pp != NULL); // 口诀：父下左，右靠左 //1.申请两个指针Node和LeftNode用来指向自己和需要和自己合并的左兄弟 BTNode* LeftNode = pp->ptr[index - 1]; BTNode* Node = pp->ptr[index]; //2.将Node和LeftNode在父节点中夹着的那个元素，挪下来，挪到左侧的LeftNode节点的屁股后边(父下左) LeftNode->keys[LeftNode->key_num + 1] = pp->keys[index]; //3.更新一下LeftNode节点的元素个数，因为一会后边要用到LeftNode.key_num这个参数 LeftNode->key_num++; //4.再将右侧的Node的全部有效元素给到左侧的LeftNode for (int i = 1; i <= Node->key_num; i++)//i指向的合并的右侧节点Node的元素下标 { LeftNode->keys[LeftNode->key_num + i] = Node->keys[i]; } //5.再将右侧的Node的全部孩子指针域给到左侧的LeftNode自己(特别注意：如果右侧节点的 // 孩子指针不为NULL，也就是说其孩子指针指向的是确确实实存在的节点，那么你需要考虑 // 把它这下孩子的双亲指针也修正一下) for (int i = 0; i <= Node->key_num; i++)//i指向的合并的右侧节点Node的孩子指针域下标 { if (Node->ptr[i] != NULL) { LeftNode->ptr[LeftNode->key_num + i] = Node->ptr[i]; Node->ptr[i]->parent = LeftNode; } } //6.修正父节点现有的元素及其的剩余的孩子指针域统一向前挪动一下 for (int i = index + 1; i <= pp->key_num; i++) { pp->keys[i - 1] = pp->keys[i]; pp->ptr[i - 1] = pp->ptr[i]; } //7.修正各个其他节点的有效元素个数 LeftNode->key_num += Node->key_num; pp->key_num -= 1; //8.释放右侧的Node节点 free(Node); //9.将合并之后的节点返回出去(返回的是左侧的LeftNode) return LeftNode; } //10.和右兄弟合并 BTNode* Merge_RightBro(BTNode* pp, int index) { //0.assert assert(pp != NULL); // 口诀：父下左，右靠左 //1.申请两个指针Node和RightNode用来指向自己和需要和自己合并的右兄弟 BTNode* Node = pp->ptr[index - 1]; BTNode* RightNode = pp->ptr[index]; //2.将Node和RightNode在父节点中夹着的那个元素，挪下来，挪到左侧的Node节点的屁股后边(父下左) Node->keys[Node->key_num + 1] = pp->keys[index]; //3.更新一下Node节点的元素个数，因为一会后边要用到Node.key_num这个参数 Node->key_num++;//这一步非常重要 一定在这里修正好 //4.再将右侧的RightNode的全部有效元素给到左侧的Node自己 for (int i = 1; i <= RightNode->key_num; i++) { Node->keys[Node->key_num + i] = RightNode->keys[i]; } //5.再将右侧的RightNode的全部孩子指针域给到左侧的Node自己(特别注意：如果右侧节点的 // 孩子指针不为NULL，也就是说其孩子指针指向的是确确实实存在的节点，那么你需要考虑 // 把它这下孩子的双亲指针也修正一下) for (int i = 0; i <= RightNode->key_num; i++) { if (RightNode->ptr[i] != NULL) { RightNode->ptr[i]->parent = Node; Node->ptr[Node->key_num + i] = RightNode->ptr[i]; } } //6.修正父节点现在的元素及其的剩余的孩子指针域统一向前挪动一下 for (int i = index + 1; i <= pp->key_num; i++) { pp->keys[i - 1] = pp->keys[i];//挪动剩余元素 pp->ptr[i - 1] = pp->ptr[i];//挪动剩余孩子指针域 } //7.修正各个其他节点的有效元素个数 Node->key_num = Node->key_num + RightNode->key_num; pp->key_num -= 1; //8.释放右侧的RightNode节点 free(RightNode); //9.将合并之后的节点返回出去(左侧的Node) return Node; }

八、删除最核心口诀（背会就懂）

借节点（父下来，兄上去）

• 父节点关键字下移到当前节点
• 兄弟节点关键字上移到父节点

合并（父下左，右靠左）

• 父节点关键字下移到左节点
• 右节点全部合并进左节点
• 释放右节点
• 父节点 key_num - 1

九、辅助函数（申请Result结构体变量+初始化+打印）

//1.申请Result结构体变量，用于节点查找结构的返回 Result* Buy_ResultNode() { Result* pr = (Result*)malloc(sizeof(Result)); if (pr == NULL) exit(EXIT_FAILURE); pr->index = 0; pr->pNode = NULL; pr->tag = false; return pr; } //1.初始化 void Init_BTree(BTree* pTree) { assert(pTree != NULL); pTree->root = NULL; } //5.打印(中序遍历) void Show_InOrder(BTNode* root)//递归 { if (root == NULL) return; //此时，当前root指向是一个真实存在的节点 int i = 0; for (; i < root->key_num; i++) { if (root->ptr[i] != NULL) { Show_InOrder(root->ptr[i]); } printf("%d ", root->keys[i + 1]); } Show_InOrder(root->ptr[root->key_num]);//==Show_InOrder(root->ptr[i]); }

十、B 树高频 12 问（背会直接拿分）

1. B 树是什么？多路平衡查找树，为磁盘 IO 优化。
2. 5 阶 B 树一个节点最多存多少关键字？4 个。
3. 最少多少？非根最少 2 个。
4. 什么是上溢出？怎么解决？关键字满了 →分裂。
5. 什么是下溢出？怎么解决？关键字太少 →借节点 / 合并。
6. B 树和二叉平衡树区别？B 树更矮、IO 更少、适合磁盘。
7. B 树所有叶子都在同一层吗？是的，绝对平衡。
8. 非叶子节点删除怎么处理？用前驱 / 后继替换，转为删叶子。
9. 分裂时中间关键字去哪里？上浮到父节点。
10. 合并会影响父节点吗？会，父节点关键字 - 1，可能继续下溢。
11. B 树时间复杂度？O (log n)，非常稳定。
12. B 树应用场景？文件系统、数据库索引底层。

十一、总结（最核心口诀）

B 树五阶，二到四关键字。

插入满了就分裂，中间上浮。

删除少了先借兄弟，借不到就合并。

父下左，右靠左，合并完了向上调。

叶子同层绝对稳，数据库索引离不了！