B树的插入、删除操作详解_b树的插入与删除

背景

在大规模数据存储中，在实现索引查询这样一个实际背景下，二叉查找树结点存储的元素数量是有限的，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构，B树也就应运而生。

B树的定义

一棵m阶的B树满足下列条件∶

1. 每个结点至多有m棵子树。
2.  除根结点外，其它每个分支至少有 t = ⌈m/2⌉棵子树。
3. 根结点至少有两棵子树(除非B树只有一个结点)。
4. 所有叶结点在同一层上。
5. B树的叶结点可以看成一种外部结点，不包含任何信息。
6. 某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它 有j个孩子的非叶结点恰好有j-1个关键码，关键码按递增次序排列。

应用场景：适合于键值数据库

                               4阶的B树

B树的插入

对高度为h的m阶B树，新结点一般是插在第h层。通过检索可以确定关键码应插入的位置。然后分两种情况讨论：

（1）若该结点中关键码个数小于m-1，则直接插入。

（2）如该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点， 并把中间关键码插入到父结点（h-1层）中。

（3）向父亲结点插入中间关键字的时候，重复以上两个步骤最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层

当试着向左上图中一个4阶的B树插入S时，插入后结点NPQS的关键字个数大于4-1，所以进行分裂，分裂为NP和S，并将中间关键字Q加入父亲结点，在这是发现父亲结点的关键字个数也超了，再次分裂，使得Q结点成为新的根结点，使得树的高度+1。

B树的删除

在删除B树结点时，为了避免回溯，当遇到需要合并的结点时就立即执行合并，B树的删除算法如下：从root向叶子结点按照查询规律遍历：

     （1）如果target在叶结点x中，则直接从x中删除target，情况（2）和（3）会保证当再叶子结点找到target时，肯定能借结点或合并成功而不会引起父结点的关键字个数少于t-1。

   （2）如果target在内部结点（简称内结点：非叶子结点）x中：  

             (a)如果x的左分支结点y至少包含t个关键字，则找出y的最右的关键字prev，并替换target，并在y中递归删除prev。

             (b) 如果x的右分支结点z至少包含t个关键字，则找出z的最左的关键字next，并替换target，并在z中递归删除next。

             (c) 否则，如果y和z都只有t-1个关键字，则将target与z合并到y中，使得y有2t-1个关键字，再从y中递归删除target。

    (3) 如果关键字不在内部结点x中，则必然在x的某个分支结点p[i]为根的子树中，如果p[i]结点只有t-1个关键字，执行3a、3b或者3c以保证我们降至一个包含至少t个关键字的结点，然后通过对x的某个合适的子结点递归而结束。

            (a) 如果p[i-1]拥有至少t个关键字，则将x的某个关键字降至p[i]中，将p[i-1]的最大结点上升至x中。

             (b) 如果p[i+1]拥有至少t个关键字，则将x个某个关键字降至p[i]中，将p[i+1]的最小关键字上升至x个。 否则将p[i]与其中一个兄弟合并，将x的一个关键字降至合并的结点中，成为中间关键字。

从如下图的4阶B树中删除T，其中t = 2。

  (1) 根结点的右子树的关键字个数为3 > 2，直接下降至LOT结点。

  (2) 由于T在内部结点LOT，T的前子结点和后子结点都只包含t-1 = 1个关键字，所以满足②c将两个子结点和T合并，生成结点PTY，并递归从PTY中删除T。

 (3) T在PTY中，而且PTY是一个叶子结点，所以直接删除。

删除如下树中的I（假设是6阶，最小度为3）

欢迎大家一起交流讨论，我的微信