数据结构（C）：一分钟看懂B-树的插入和删除

1.B-树

B-树定义：一种平衡的多路查找树。用作索引组织文件，可减少访问外存次数，提高访问速度、减少时间。一棵m阶B-树或为空树，或满足下列特性：
1、树中每个结点至多有m个子树；(结点中的关键字个数最多m-1)
2、若根结点不是叶子结点，至少有两棵子树(根至少有一个关键字)
3、除根结点外，其余非叶子结点至少有m/2（下取整）棵子树。(比关键字个数多一个)
4.关键字的个数，范围是： m/2(下取整)-1≤n≤m-1
5、所有的叶子结点都出现在同一层上，不带信息（可看成是外部结点或查找失败的结点，并不存在）
6.节点的表示：（n,A0,K1, A1,K2, A2, ……… Kn, An），n：关键字的个数，A：指针，K：关键字

2.B-树的插入

**插入过程说明：**B-树的生成从空树开始，逐个插入关键字。由于B-树结点中的关键字个数必须≥m/2-1，每次插入一个关键字不是在树中增加一个叶子结点，而是在最低层的某个非终端结点中添加一个关键字。插入分两种情况讨论:
(1)若该结点的关键字个数<m-1
直接在最底层插入

（2）若该结点的关键字个数>=m-1
以中间关键码（m/2上取整）为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点(ｋ-1层)中。同理，父亲节点也可能需要分裂，最终可能导致树长高一层。

3.B-树的删除

删除非终端节点：首先找到要删除的关键码所在结点，**用指针Ai（右指针） 所指子树中最小关键码Y代替Ki，**然后在相应终端结点中删去Y，这样就转为删除终端结点中的关键码的问题了。

删除终端节点:

（1）被删关键码所在结点中的关键码个数>=[m/2],说明删去该关键字后该结点仍满足B-树的定义。
这种情况最为简单，只需从该结点中直接删去关键字即可。

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

①如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于[m/2]-1。
则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的最大（小）关键字下移至被删 关键 字所在结点中。
父母中紧靠被删关键字的下来，兄弟中紧靠被删关键字的关键字上取

②被删关键码所在结点和其相邻的左右兄弟节点中的关键码个数均等于[m/2]-1，左右兄弟都不够借。
需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，合并到Ai（即双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于[m/2]-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。
父母节点中与被删的关键字紧靠的关键字下来，然后去和兄弟节点合并

注意：发现母亲节点也不够删除的时候，将母亲节点这一层看做叶子，连带着其孩子看着整体一起移动