数据结构__B树

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,B,树,B树,动态查找结构,现在我们所讨论的,m,路查找树多为可以动态调整的多路查找树，它的一般定义为：,一棵,m,路查找树,它或者是一棵空树,或者是满足如下性质的树：,根最多有,m,棵子树,并具有如下的结构：,n,A,0,(,K,1,A,1,),(,K,2,A,2,),(,K,n,A,n,),其中，,A,i,是指向子树的指针，,0,i,n,m,；,K,i,是关键码，,1,i,n,m,。,K,i,K,i+1,1,i,n,。,动态的,m,路查找树,在子树,A,i,中所有的关键码都,小于,K,i+1,，,且,大于,K,i,，,0,i,n,。,在子树,A,n,中所有的关键码都,大于,K,n,；,在子树,A,0,中的所有关键码都,小于,K,1,。,子树,A,i,也是,m,路查找树，,0,i,n,。,一棵,3,路查找树的示例,AVL,树是,2,路查找树。如果已知,m,路查找树的度,m,和它的高度,h,则树中的最大结点数为,(,等比级数前,h,项求和,),每个结点中最多有,m,-,1,个关键码，在一棵高度为,h,的,m,路查找树中关键码的最大个数为,m,h,+1,-,1,。,对于高度,h,=2,的二叉树，关键码最大个数为,7,；,对于高度,h,=3,的,3,路查找树，关键码最大个数为,3,4,-,1=80,。,提高查找树的路数,m,，,可以改善树的查找性能。对于给定的关键码数,n,，,如果查找树是平衡的，可以使,m,路查找树的性能接近最佳。下面我们将讨论一种称之为,B-,树的平衡的,m,路查找树。在,B-,树中我们引入“失败”结点。一个失败结点是当查找值,x,不在树中时才能到达的结点。,B-,树,一棵,m,阶,B-,树是一棵,m,路查找树，它或者是空树，或者是满足下列性质的树：,树中每个结点至多有,m,棵子树；,根结点至少有,2,棵子树；,除根结点以外的所有非终端结点至少有,m,/2,棵子树；,所有非终端结点中包含下列信息数据,(n,A,0,K,1,A,1,K,2,A,2,K,n,A,n,),，,其中：,K,i,(i=1,n),为关键字,，且,K,i,K,i+1,A,i,(i=0,n),为指向子树根结点的指针,n,为关键字的个数,所有的叶子结点（失败结点）都位于同一层。,事实上，每个结点中还应包含指向每个关键字的记录的指针。,非,B-,树,B-,树,B-,树的查找算法,B-,树的查找过程是一个顺指针查找结点和在结点的关键字进行查找交叉进行的过程。因此，,B-,树的查找时间与,B-,树的阶数,m,和,B-,树的高度,h,直接有关，必须加以权衡。,在,B-,树上进行查找，查找成功所需的时间取决于关键码所在的层次，查找不成功所需的时间取决于树的高度。如果我们定义,B-,树的高度,h,为失败结点所在的层次，需要了解树的高度,h,与树中的关键码个数,N,之间的关系。,设在,m,阶,B-,树中，失败结点位于第,h+1,层。在这棵,B-,树中关键码个数,N,最小能达到多少？从,B-,树的定义知,1,层,1,个结点,2,层 至少,2,个结点,3,层 至少,2,m,/2,个结点,4,层 至少,2,m,/2,2,个结点,如此类推，,h,层 至少有,2,m,/2,h,-,2,个结点。所有这些结点都不是失败结点。,高度,h,与关键码个数,N,之间的关系,若树中关键码有,N,个,则失败结点数为,N,+1,。,这是因为失败一般发生在,K,i,x,K,i+1,0,i,N,，设,K,0,=-,，,K,N+1,=+,。,因此，有,N,+1=,失败结点数,=,=,位于第,h+1,层的结点数,2,m,/2,h,-1,N,2,m,/2,h,-,1,-,1,反之，如果在一棵,m,阶,B-,树中有,N,个关键码，则所有的非失败结点所在层次都小于,h,，,则,h,-,1,log,m/2,(,N,+1)/2),示例：若,B-,树的阶数,m,=199,，,关键码总数,N,=1999999,，,则,B-,树的高度,h,不超过,log,100,1000000+1=4,若,B-,树的阶数,m,=3,，,高度,h,=4,，,则关键码总数至少为,N,=2,3/2,4,-,1,-,1=15,。,m,值的选择,如果提高,B-,树的阶数,m,，,可以减少树的高度，从而减少读入结点的次数，因而可减少读磁盘的次数。,事实上，,m,受到内存可使用空间的限制。当,m,很大超出内存工作区容量时，结点不能一次读入到内存，增加了读盘次数，也增加了结点内查找的难度。,m,值的选择：应使得在,B-,树中找到关键码,x,的时间总量达到最小。,这个时间由两部分组成：,从磁盘中读入结点所用时间,在结点中查找,x,所用时间,根据定义，,B-,树的每个结点的大小都是固定的，结点内有,m,-,1,个索引项,(,K,i,D,i,A,i,),1,i,m,。,其中，,K,i,所占字节数为,，,D,i,和,A,i,所占字节数为,，则结点大小近似为,m,(,+2,),个字节。读入一个结点所用时间为：,t,seek,+,t,latency,+,m,(,+2,),t,tran,=,a,+,bm,B-,树的插入,B-,树是从空树起，逐个插入关键码而生成的。,在,B-,树，每个非失败结点的关键码个数都在,m,/2,-,1,m,-,1,之间。,插入在,某个叶结点,开始。如果在关键码插入后结点中的关键码个数超出了上界,m,-,1,，,则结点需要“分裂”，否则可以直接插入。,实现结点“分裂”的原则是：,设结点,A,中已经有,m,-,1,个关键码，当再插入一个关键码后结点中的状态为,(,m,A,0,K,1,A,1,K,2,A,2,K,m,A,m,),其中,K,i,K,i,+1,1,i,m,这时必须把结点,p,分裂成两个结点,p,和,q,，,它们包含的信息分别为：,结点,p,：,(,m,/2,-,1,A,0,K,1,A,1,K,m,/2,-,1,A,m,/2,-,1,),结点,q,：,(,m,-,m,/2,A,m,/2,K,m,/2,+1,A,m,/2,+1,K,m,A,m,),位于中间的关键码,K,m,/2,与指向新结点,q,的指针形成一个二元组,(,K,m,/2,q),，,插入到这两个结点的双亲结点中去。,结点“分裂”的示例,示例：从空树开始逐个加入关键码建立,3,阶,B-,树,在插入新关键码时，需要自底向上分裂结点，最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂。,若设,B-,树的,高度为,h,那么在,自顶向下,查找到,叶结点,的过程中需要进行,h,次读盘。,B-,树的插入算法,当分裂一个非根的结点时需要向磁盘写出,2,个结点,当分裂根结点时需要写出,3,个结点。,如果我们所用的内存工作区足够大，使得在向下查找时读入的结点在插入后向上分裂时不必再从磁盘读入，那么，在完成一次插入操作时,需要读写磁盘的次数,=,=,找插入结点向下读盘次数,+,+,分裂非根结点时写盘次数,+,+,分裂根结点时写盘次数,=,=,h,+2(,h,-,1)+3=,=3,h,+1,。,可以证明，在向一棵初始为空的,B-,树中插入,N,个关键码,并且非失败结点个数为,p,时,分裂的结点总数最多为,p,-,2,。,由于根结点至少有一个关键码，其它各非失败结点至少有,m,/2,-,1,个关键码，则一棵拥有,p,个结点的,m,阶,B-,树至少有,1+(,m,/2,-,1)(,p,-,1),个关键码。,其平均分裂结点数,S,avg,为：,S,avg,=,分裂结点总次数,/,N,(,p,-,2)/(1+(,m,/2,-,1)(,p,-,1),m,1,时，需要将叶结点分裂为两个结点，它们的关键码分别为,(,m,1+1)/2,和,(,m,1+1)/2,。,并且它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后，问题归于在非叶结点中的插入了。,在非叶结点中关键码的插入与叶结点的插入类似，但非叶结点中的子树棵数的上限为,m,，,超出这个范围就需要进行结点分裂。,在做根结点分裂时，因为没有双亲结点，就必须创建新的双亲结点，作为树的新根。这样树的高度就增加一层了。,B+,树的删除仅在叶结点上进行,。当在叶结点上删除一个关键码,-,指针索引项后，结点中的子树棵数仍然不少于,m,1/2,，,这属于简单删除，其上层索引可以不改变。,如果删除的关键码是该结点的最小关键码，但因在其上层的副本只是起了一个引导查找的“分界关键码”的作用，所以上层的副本仍然可以保留。,如果在叶结点中删除一个关键码,-,指针索引项后，该结点中的子树棵数,n,小于结点子树棵数的下限,m,1/2,，,必须做结点的调整或合并工作。,删除,18,删除,12,如果右兄弟结点的子树棵数已达到下限,m,1/2,，,没有多余的关键码可以移入被删关键码所在的结点，这时必须进行两个结点的合并。将右兄弟结点中的所有关键码,-,指针索引项移入被删关键码所在结点，再将右兄弟结点删去。,删除,33,进行,结点合并,结点的合并将导致双亲结点中“分界关键码”的减少，有可能减到非叶结点中子树棵数的下限,m,/2,以下。这样将引起非叶结点的调整或合并。,如果根结点的最后两个子女结点合并，树的层数就会减少一层。,