B树

辅存上的数据结构,对程序的运行时间分为两个主要组成部分

  1. 磁盘存取的时间
  2. cpu(计算)的时间

B树的定义

  • B树为具有如下性质的有根树:

1.每个节点x有以下域:
a. n[x],当前存储在节点x中的关键字数量
b. n[x]个关键字升序存放:key(1)[x] <= key(2)[x] <= … <= key(n[x])[x]
c. leaf[x]是一个布尔值,如果x是叶子则为true,否则为false

2.每个内节点x还包含n[x]+1个指向其子女的指针: C(1)[x], C(2)[x], …, C(n[x]+1)[x],叶节点没有子女,故它们的C(i)域无定义

3.个关键字key(i)[x]对存储在各子树中的关键字范围加以分割:如ki为存储在以C(i)[x]为根的子树中的关键字,则:

k1 <= key(1)[x] <= k2 <= key(2)[x] <= … <= key(n[x])[x] <= kn[x]+1

4.每个叶节点具有相同的深度,即树的高度h

5.每个节点能包含关键字数有一个上届和下界,这些界可用一个称作B树的最小度数的固定整数t >= 2 来表示
a. 每个非根的节点必须至少有t-1个关键字,每个非根的内节点至少有t个子女,如果树是非空的,则根节点至少包含一个关键字
b. 美国节点可包含至多 2*t-1个关键字,t=2是的B树是简单的,即 2-3-4 树

B树的高度

如果n >= 1, 则对任意一棵包含n个关键字,高度为h,最小度数 t >= 2 的B树T,有: h <= logt((n+1)/2)

B树的基本操作

首先做两个约定:

  1. B树的根节点始终保存在主存中,但根节点被改变,需要写一次磁盘
  2. 任何被当作参数的节点被传递之前,先要从磁盘中读出来

搜索B树

    BTreeSearch( x, k )     //x是子树根,初始调用为 BTreeSearch( root[T], k )
        i = 1 ;
        while i <= n[x] and key(i)[x] < k
            i++ ;
                                                //BTreeSearch 读取磁盘数为 O(h)
        if i <= n[x] and key(i)[x] == k         //= O(logth)
            return x, i ;                       //cpu时间为O(t*h) = O(t*logth)

        if leaf[x]
            return nil ;
        else
            DiskRead( C(i)[x] ) ;
            return BTreeSearch( C(i)[x], k ) ;

创建一刻空的B树

    BTreeCreate( T )            //在O(1)内分配一个新节点
        x = AllocateNode( ) ;
        leaf[x] = true ;
        n[x] = 0 ;
        DiskWrite( x ) ;
        root[x] = x ;

插入关键字

    //B树中节点的分裂
    BTreeSpliteChild( x, i )        //x是非满父节点
        y = C(i)[x] ;               //y = C(i)[x]是满的节点,现在要分裂y
        t = ( n[y] + 1 ) / 2 ;      //如果 y 是 root[T],则x是无关键字的空节点

        z = AllocateNode( ) ;      //分配一个新节点
        
        leaf[z] = leaf[y] ;

        for j = 1 to t                  //将y的后半段
            key(j)[z] = key(j+t)[y] ;   //插入到z中
        if !leaf[z]
            for j = 1 to t
                C(j)[z] = C(j+t)[z] ;

        for j = n[x] down to i          //将x节点的对应位置
            key(j+1)[x] = key(j)[x] ;   //腾空,好将y中的元素
        for j = n[x]+1 down to i+1      //插入
            C(j+1)[x] = C(j)[x] ;

        key(i)[x] = key(t)[y] ;         //将y中元素插入
        C(i+1)[x] = z ;

        n[y] = t - 1 ;                  //以 2-3-4 树为例:
        n[z] = t - 1 ;                  //      1 - 9   <-- x
        n[x]++ ;                        //        |            
                                        //      3-5-7   <-- y
        DiskWrite( y ) ;                //        
        DiskWrite( x ) ;                //        |  分裂
        DiskWrite( z ) ;                //        V
                                        //
                                        //      1-5-9   <-- x
                                        //       / \
                                        //      3   7   <-- z
                                        //      ^
                                        //      |
                                        //      y


    //===================================
    //单程下行遍历方式插入关键字
    //需要O(h)次磁盘读写,O(h*t)cpu时间
    BTreeInsert( T, k )         //T是B树,k为新关键字
        r = root[T] ;

        if n[r] == 2*t-1        //一下处理树根是满的的情况
            x = AllocateNode( ) ;
            n[x] = 0 ;
            C(1)[x] = r ;
            leaf[x] = false ;
            root[T] = x ;
            BTreeSpliteChild( x, 1 ) ;//对根进行分裂是增加B树高度的唯一途径    
            BTreeInsertNonFull( x, k ) ;
        else
            BTreeInsertNonFull( r, k ) ;

    //-------------------
    BTreeInsertNonFull( x, k )
        i = 1 ;

        while i <= n[x] and key(i)[x] < k
            i++ ;

        if leaf[x]          //B树只在叶节点处插入关键字
            for j = n[x] down to i
                key(j+1)[x] = key(j)[x] ;

            key(i)[x] = k ;
            n[x]++ ;
            DiskWrite( x ) ;
        else
            DiskRead( C(i)[x] ) ;
            if n[C(i)[x]] == 2*t-1
                BTreeSpliteChild( x, i ) ;
            
            if key(i)[x] < k //关键字在最最右边
                i++ ;

            BTreeInsertNonFull( C(i)[x],k ) ;

删除关键字

假设用过程 BTreeDelete 从以x为子树根的子树中删除关键字k,这个过程始终保证x中的关键字数量至少为t

1.如果关键字k在节点x中,且x是个叶节点,则从x中删除k

2.如果关键字k在节点x中,且x是个内节点.则作如下操作:
 a.如果节点x中前于k的子节点y包含至少t个关键字,则找出k在y为根的子树中的前驱k1,递归地删除k1,并在x中用k1取代k.(找到k1并删除它可在沿树下降的一趟过程中完成)
 b.对称的,如果节点x中位于k之后的子节点z包含至少t个关键字,则找出k在z为根的子树中的前驱k1,递归地删除k1,并在x中用k1取代k.(找到k1并删除它可在沿树下降的一趟过程中完成)
 c.否则,如果y和z都只有t-1个关键字,则将k和z中所有关键字合并进y,使得x失去k和指向z的指针,这使y包含 2*t-1 个关键字,然后释放z并将k从y中递归删除

3.如果关键字k不在内节点x中,则确定必定包含k的正确的子树根C(i)[x],如果C(i)[x]只有 t-1 个关键字,执行步骤 3a 或者 3b 以确保我们降至一个包含至少t个关键字的节点,然后,通过对 x 的某个合适的子节点递归而结束
 a.如果C(i)[x]只包含t-1个关键字,但它的一个相邻的兄弟包含至少t个关键字,则将x中的某一个关键字降至C(i)[x]中,将C(i)[x]的相邻的左兄弟或者右兄弟中的某一个关键字升至x,将该兄弟中合适的子女指针移到C(i)[x]中,使得C(i)[x]增加一个额外的关键字.
 b.如果C(i)[x]以及C(i)[x]所有相邻兄弟都只包含 t-1 个关键字,则将C(i)[x]与一个兄弟合并,即将x的一个关键字移到新合并的节点,使之成为该节点的中间关键字

    BTreeDelete( x, k )
        i = 1 ;
        while i <= n[x] and key(i)[x] < k
            i++ ;

        if i <= n[x] and key(i)[x] == k     //在x中找到k
            if leaf[x]
                while i <= n[x]-1
                    key(i)[x] = key(i+1)[x] ;
                n[x]-- ;
            else if n[C(i)[x]] >= t or n[C(i+1)[x]] >= t  //2a 和 2b 情况
                if n[C(i)[x]] >= t
                    k1 = Max( C(i)[x] ) ;   //以C(i)[x]为根的子树的最大值
                    C = C(i)[x] ;
                else
                    k1 = Min( C(i+1)[x] ) ;   //以C(i+1)[x]为根的子树的最小值
                    C = C(i+1)[x]

                BTreeDelete( Ci[x], k1 ) ;
                key(i)[x] = k1 ;
            else                            //2c 情况
                MergeChilds( x, i ) ;       //合并key(i)[x],C(i)[x],C(i+1)[x]
                BTreeDelete( C(i)[x], k ) ;
        else                                //在x中没有找到k
            if leaf[x]                      //x不存在B树中
                return NotFoundError ;
            else if n[C(i)[x]] >= t         //k可能在以C(i)[x]为根的子树中
                BTreeDelete( C(i)[x], k ) ;
            else                            //C(i)[x]节点的关键字数量不够
                if i > 1 and n[C(i-1)[x]] >= t //C(i)[x]的左兄弟中关键字有t个以上
                    LeftGet( x, i ) ;
                else if i <= n[x] and n[C(i+1)[x]] >= t //C(i)[x]的右兄弟中关键字有t个以上
                    RightGet( x, i ) ;
                else //C(i)[x]的左右兄第中都不够t个关键字
                    if i == n[x]+1
                        i-- ;
                    MergeChilds( x, i ) ;
                BTreeDelete( C(i)[x], k ) ;


    //-----------
    MergeChilds( x, i )
        j = n[Ci[x]] + 1 ;
        key(j)[C(i)[x]] = key(i)[x] ;//将关键字key(i)[x]并入节点C(i)[x]
        j++ ;
        C(j)[C(i)[x]] = C(1)[C(i+1)[x]] ; //将指针并入节点C(i)[x]

        for w = 1 to n[C(i+1)[x]]   //将节点C(i+1)[x]中的关键字和指针并入节点C(i)[x]
            key(j)[C(i)[x]] = key(w)[C(i+1)[x]] ;
            C(j+1)[C(i)[x]] = C(w+1)[C(i+1)[x]] ;
            j++ ;

        for j = i to n[x]-1         //紧缩x节点的关键字和指针
            key(j)[x] = key(j+1)[x] ;
            C(j+1)[x] = C(j+2)[x] ;
        n[x]-- ;
        n[C(i)[x]] = 2*t - 1 ;

        free( C(i+1)[x] ) ;

    //-------------
    LeftGet( x, i )
        for j = n[C(i)[x]] + 1 down to 2        //为新关键字和指针腾出位置
            key(j)[C(i)[x]] = key(j-1)[C(i)[x]] ;
            C(j+1)[C(i)[x]] = C(j)[C(i)[x]] ;
        C(2)[C(i)[x]] = C(1)[C(i)[x]] ;

        //节点C(i)[x]并入x节点的关键字
        key(1)[C(i)[x]] = key(i-1)[x] ;

        //节点x并入节点C(i-1)[x]中的最后一个关键字
        key(i-1)[x] = key(n[C(i-1)[x]])[C(i-1)[x]] ;

        //将节点C(i-1)[x]中的最后一个指针到节点C(i)[x]
        C(1)[C(i)[x]] = C(n[C(i-1)[x]]+1)[C(i-1)[x]] ;

        n[C(i-1)[x]]-- ;
        n[C(i)[x]]++ ;

    //---------------
    RightGet( x, i )
        /*略*/
        ... ;