当前位置:   article > 正文

B树的插入、删除操作详解_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)

 

 

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

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/878628
推荐阅读
相关标签
  

闽ICP备14008679号