B树插入删除操作

B-树定义：

一种平衡的多路查找树。

用于：索引组织文件，减少访问外存次数，节约搜索时间。

一棵m阶B-树或为空树，或满足下列特性：（为尽量简单，把考试不考的内容全部略去） 1、树中每个结点至多有m个分支，最少有[m/2]分支，取上整，除根结点外；

2.关键字数大于等于m/2-1，小于等于m-1，/2取上整

3、如果树的结点数大于1，则根结点至少两分支

例4阶B-树，来自zzh的ppt

插入操作

(1)若该结点的关键字个数<m-1 直接在最底层插入

（2）若该结点的关键字个数=m-1

此种情况m-1+1=m溢出，把出问题的那一分支的中间结点插入到父结点中，如果父结点也溢出，递归解决，显然树高可能因此增加一层，举个例子最形象！

删除结点

三种情况

（1）被删关键字所在结点中的关键字个数>=[m/2],说明删去该关键字后该结点仍满足B-树的定义。

直接删去关键字即可。

（2）被删关键字所在结点中关键字个数n=[m/2]-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。

①如果其左（右）兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于[m/2]-1。

则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的最大（小）关键字下

移至被删 关键 字所在结点中。

有点像以兄弟结点为原点进行了一次左旋或右旋，父母中紧靠被删关键字的下来，兄弟中紧靠被删关键字的关键字上取

②被删关键字所在结点和其相邻的左右兄弟节点中的关键码个数均等于[m/2]-1，以常考的3阶B-树为例就是被删结点和相邻的左

右兄弟结点都只有一个关键字，左右兄弟都不够借。

需把要删除关键字的结点剩余部分与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点

如果因此使双亲结点中的关键字数目少于ceil(m/2)-1，则依次类推。