B-树的建立、插入和删除结点的过程

多路平衡查找树

目标：多叉 有序 平衡

两个叉一个关键字的叫二叉树

m个叉m-1个关键字的树就是m叉树

顺序仍然是左小右大

$$根节点至少有两个分支$$ $$非根非叶节点至少有\lceil m/2\rceil 个分支$$ 因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

添加节点

插入节点时当个数大于m-1时： $$\begin{gathered} 将\lceil m/2\rceil 位置的元素“提”出来 \\ (将左侧与右侧的关键字分别装在新的节点中) \end{gathered}$$ 当前层分解，传入上一层(可能产生连锁反应) 插入元素8 拆分上移

上部分超过三叉树的元素限制，连锁反应

删除节点

删除的节点是“终端”节点

1.直接删除

2.兄弟够借

3.兄弟不够借

合并操作：

删除的节点为非终端节点

如果子树元素都为1： 将要删除节点用其前驱或后继替代(位置替换)，然后删除