数据结构__B树.ppt

《数据结构__B树.ppt》由会员分享，可在线阅读，更多相关《数据结构__B树.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n nB树树动态查找结构动态查找结构n n现现在在我我们们所所讨讨论论的的m路路查查找找树树多多为为可可以以动动态态调调整的多路查找树，它的一般定义为：整的多路查找树，它的一般定义为：n n一一棵棵m路路查查找找树树,它它或或者者是是一一棵棵空空树树,或或者者是是满满足如下性质的树：足如下性质的树：uu 根最多有根最多有 m 棵子树棵子树,并具有如下的结构：并具有如下的结构：n,A0,(K1,A1),(K2,A2),(Kn,An)其其中中，Ai 是是指指向向子子树树的的指指针针，0 i n m；Ki 是关键码，是关键码，1 i n m。Ki Ki+1,1 i n。动态的动态的m路查找树路查找树

2、uu 在子树在子树 Ai 中所有的关键码都中所有的关键码都小于小于 Ki+1，且且大于大于 Ki，0 i n。uu 在子树在子树 An 中所有的关键码都中所有的关键码都大于大于Kn；uu 在子树在子树 A0 中的所有关键码都中的所有关键码都小于小于 K1。uu 子树子树 Ai 也是也是 m 路查找树，路查找树，0 i n。一棵一棵3路查找树的示例路查找树的示例AVL树是树是2路查找树。如果已知路查找树。如果已知m路查找树的度路查找树的度 m和它的高度和它的高度 h,则树中的最大结点数为则树中的最大结点数为(等比级数前等比级数前 h 项求和项求和)n n每每个个结结点点中中最最多多有有 m-1

3、个个关关键键码码，在在一一棵棵高高度度为为 h 的的 m 路路查查找找树树中中关关键键码码的的最最大大个个数数为为 mh+1-1。uu 对对于于高高度度 h=2 的的二二叉叉树树，关关键键码码最最大大个个数数为为7；uu 对对于于高高度度 h=3 的的3路路查查找找树树，关关键键码码最最大大个个数为数为 34-1=80。n n提提高高查查找找树树的的路路数数 m，可可以以改改善善树树的的查查找找性性能能。对对于于给给定定的的关关键键码码数数 n，如如果果查查找找树树是是平平衡衡的的，可可以以使使 m 路路查查找找树树的的性性能能接接近近最最佳佳。下下面面我我们们将将讨讨论论一一种种称称之之为为

4、B-树树的的平平衡衡的的 m 路路查查找找树树。在在B-树树中中我我们们引引入入“失失败败”结结点点。一一个个失失败败结结点是当查找值点是当查找值x不在树中时才能到达的结点。不在树中时才能到达的结点。B-树树n n一棵一棵一棵一棵 m m 阶阶阶阶B-B-树是一棵树是一棵树是一棵树是一棵 m m 路查找树，它或者是空树，或路查找树，它或者是空树，或路查找树，它或者是空树，或路查找树，它或者是空树，或者是满足下列性质的树：者是满足下列性质的树：者是满足下列性质的树：者是满足下列性质的树：uu树中每个结点至多有树中每个结点至多有树中每个结点至多有树中每个结点至多有mm棵子树；棵子树；棵子树；棵子树

5、；uu 根结点至少有根结点至少有 2 棵子树；棵子树；uu 除根结点以外的所有非终端结点至少有除根结点以外的所有非终端结点至少有 m/2 棵棵子树；子树；uu 所有非终端结点中包含下列信息数据所有非终端结点中包含下列信息数据 (n,A(n,A0 0,K,K1 1,A,A1 1,K,K2 2,A,A2 2,K Kn n ,A,An n)，其中：其中：其中：其中：K Ki i (i=1,n)(i=1,n)为关键字为关键字为关键字为关键字，且，且，且，且K Ki i K Ki+1 i+1,A,Ai i(i=0,n)(i=0,n)为指向子树根为指向子树根为指向子树根为指向子树根结点的指针结点的指针结点

6、的指针结点的指针,n n为关键字的个数为关键字的个数为关键字的个数为关键字的个数uu 所有的叶子结点（失败结点）都位于同一层。所有的叶子结点（失败结点）都位于同一层。事实上，每个结点中还应包含指向每个关键字的记事实上，每个结点中还应包含指向每个关键字的记录的指针。录的指针。非非B-树树 B-树树 B-树的查找算法树的查找算法n nB-树树的的查查找找过过程程是是一一个个顺顺指指针针查查找找结结点点和和在在结结点点的的关关键键字字进进行行查查找找交交叉叉进进行行的的过过程程。因因此此，B-树树的的查查找找时时间间与与B-树树的的阶阶数数m和和B-树树的的高高度度h直接有关，必须加以权衡。直接有关

7、，必须加以权衡。n n在在B-树树上上进进行行查查找找，查查找找成成功功所所需需的的时时间间取取决决于于关关键键码码所所在在的的层层次次，查查找找不不成成功功所所需需的的时时间间取取决决于于树树的的高高度度。如如果果我我们们定定义义B-树树的的高高度度h 为为失失败败结结点点所所在在的的层层次次，需需要要了了解解树树的的高高度度h 与与树树中的关键码个数中的关键码个数 N 之间的关系。之间的关系。n n设在设在 m 阶阶B-树中，失败结点位于第树中，失败结点位于第 h+1层。在层。在这棵这棵B-树中关键码个数树中关键码个数 N 最小能达到多少？最小能达到多少？从从B-树的定义知树的定义知,uu

8、 1层层 1 个结点个结点uu 2层层 至少至少 2 个结点个结点uu 3层层 至少至少 2 m/2 个结点个结点uu 4层层 至少至少 2 m/2 2 个结点个结点uu 如此类推，如此类推，uu h 层层 至少有至少有2 m/2 h-2个结点。所有这些个结点。所有这些结点都不是失败结点。结点都不是失败结点。高度高度h与关键码个数与关键码个数 N 之间的关系之间的关系n n若树中关键码有若树中关键码有 N 个个,则失败结点数为则失败结点数为 N+1。这是因为失败一般发生在这是因为失败一般发生在 Ki x Ki+1,0 i N，设，设K0=-，KN+1=+。因此，有因此，有 N+1=失败结点数失

9、败结点数=位于第位于第 h+1 层的结点数层的结点数 2 m/2 h-1 N 2 m/2 h-1-1n n反之，如果在一棵反之，如果在一棵 m 阶阶B-树中有树中有 N 个关键码，个关键码，则所有的非失败结点所在层次都小于则所有的非失败结点所在层次都小于 h，则则 h-1 log m/2 (N+1)/2)n n示例：若示例：若B-树的阶数树的阶数 m=199，关键码总数关键码总数 N=1999999，则则B-树的高度树的高度 h 不超过不超过 log100 1000000+1=4n n若若B-树的阶数树的阶数 m=3，高度高度 h=4，则关键码总则关键码总数至少为数至少为 N=2 3/2 4-

10、1-1=15。m值的选择值的选择n n如果提高如果提高B-树的阶数树的阶数 m，可以减少树的高度，可以减少树的高度，从而减少读入结点的次数，因而可减少读磁盘从而减少读入结点的次数，因而可减少读磁盘的次数。的次数。n n事实上，事实上，m 受到内存可使用空间的限制。当受到内存可使用空间的限制。当 m很大超出内存工作区容量时，结点不能一次读很大超出内存工作区容量时，结点不能一次读入到内存，增加了读盘次数，也增加了结点内入到内存，增加了读盘次数，也增加了结点内查找的难度。查找的难度。n nm值的选择：应使得在值的选择：应使得在B-树中找到关键码树中找到关键码 x 的的时间总量达到最小。时间总量达到最

11、小。n n这个时间由两部分组成：这个时间由两部分组成：从磁盘中读入结点所用时间从磁盘中读入结点所用时间 在结点中查找在结点中查找 x 所用时间所用时间n n根据定义，根据定义，B-树的每个结点的大小都是固定的，树的每个结点的大小都是固定的，结点内有结点内有 m-1 个索引项个索引项(Ki,Di,Ai),1 i m。其中，其中，Ki 所占字节数为所占字节数为，Di 和和 Ai 所占字节数所占字节数为为，则结点大小近似为，则结点大小近似为 m(+2)个字节。读个字节。读入一个结点所用时间为：入一个结点所用时间为：tseek+tlatency+m(+2)ttran=a+bmB-树的插入树的插入n n

12、B-树是从空树起，逐个插入关键码而生成的。树是从空树起，逐个插入关键码而生成的。n n在在B-树，每个非失败结点的关键码个数都在树，每个非失败结点的关键码个数都在 m/2 -1,m-1 之间。之间。n n插入在插入在某个叶结点某个叶结点开始。如果在关键码插入后开始。如果在关键码插入后结点中的关键码个数超出了上界结点中的关键码个数超出了上界 m-1，则结点需则结点需要要“分裂分裂”，否则可以直接插入。，否则可以直接插入。n n实现结点实现结点“分裂分裂”的原则是：的原则是：uu 设结点设结点 A 中已经有中已经有 m-1 个关键码，当再插入个关键码，当再插入一个关键码后结点中的状态为一个关键码后

13、结点中的状态为 (m,A0,K1,A1,K2,A2,Km,Am)其中其中 Ki Ki+1,1 i muu 这时必须把结点这时必须把结点 p 分裂成两个结点分裂成两个结点 p 和和 q，它们包含的信息分别为：它们包含的信息分别为：uu 结点结点 p：(m/2 -1,A0,K1,A1,K m/2 -1,A m/2 -1)uu 结点结点 q：(m-m/2,A m/2,K m/2+1,A m/2+1,Km,Am)uu 位于中间的关键码位于中间的关键码 K m/2 与指向新结点与指向新结点 q 的的指针形成一个二元组指针形成一个二元组(K m/2,q)，插入到这插入到这两个结点的双亲结点中去。两个结点的

14、双亲结点中去。结点结点“分裂分裂”的示的示例例示例：从空树开始逐个加入关键码建立示例：从空树开始逐个加入关键码建立3阶阶B-树树n n在插入新关键码时，需要自底向上分裂结点，在插入新关键码时，需要自底向上分裂结点，最坏情况下从被插关键码所在叶结点到根的路最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂。径上的所有结点都要分裂。若设若设B-树的树的高度为高度为h,那那么在么在自顶向自顶向下下查找到查找到叶叶结点结点的过程的过程中需要进行中需要进行 h 次读盘。次读盘。B-树的插入算法树的插入算法n n当分裂一个非根的结点时需要向磁盘写出当分裂一个非根的结点时需要向磁盘写出 2 个个

15、结点结点,当分裂根结点时需要写出当分裂根结点时需要写出 3 个结点。个结点。n n如果我们所用的内存工作区足够大，使得在向如果我们所用的内存工作区足够大，使得在向下查找时读入的结点在插入后向上分裂时不必下查找时读入的结点在插入后向上分裂时不必再从磁盘读入，那么，在完成一次插入操作时再从磁盘读入，那么，在完成一次插入操作时 需要读写磁盘的次数需要读写磁盘的次数=找插入结点向下读盘次数找插入结点向下读盘次数+分裂非根结点时写盘次数分裂非根结点时写盘次数+分裂根结点时写盘次数分裂根结点时写盘次数=h+2(h-1)+3=3h+1。n n可以证明，在向一棵初始为空的可以证明，在向一棵初始为空的B-树中插

16、入树中插入 N 个关键码个关键码,并且非失败结点个数为并且非失败结点个数为 p 时时,分裂的分裂的结点总数最多为结点总数最多为 p-2。由于根结点至少有一个关由于根结点至少有一个关键码，其它各非失败结点至少有键码，其它各非失败结点至少有 m/2 -1 个关个关键码，则一棵拥有键码，则一棵拥有 p 个结点的个结点的 m 阶阶B-树至少有树至少有 1+(m/2 -1)(p-1)个关键码。个关键码。n n其平均分裂结点数其平均分裂结点数Savg 为：为：Savg=分裂结点总次数分裂结点总次数/N (p-2)/(1+(m/2 -1)(p-1)mm1 1 时，需要将叶时，需要将叶时，需要将叶时，需要将叶

17、结点分裂为两个结点，它们的关键码分别为结点分裂为两个结点，它们的关键码分别为结点分裂为两个结点，它们的关键码分别为结点分裂为两个结点，它们的关键码分别为 (mm1+1)/21+1)/2 和和和和 (mm1+1)/21+1)/2 。并且它们的双亲结点中应并且它们的双亲结点中应并且它们的双亲结点中应并且它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后，同时包含这两个结点的最小关键码和结点地址。此后，同时包含这两个结点的最小关键码和结点地址。此后，同时包含这两个结点的最小关键码和结点地址。此后，问题归于在非叶结点中的插入了。问题归于在非叶结点中的插入了。问题归于在非叶结点中的插入了。

18、问题归于在非叶结点中的插入了。n n在非叶结点中关键码的插入与叶结点的插入类在非叶结点中关键码的插入与叶结点的插入类似，但非叶结点中的子树棵数的上限为似，但非叶结点中的子树棵数的上限为 m，超超出这个范围就需要进行结点分裂。出这个范围就需要进行结点分裂。n n在做根结点分裂时，因为没有双亲结点，就必在做根结点分裂时，因为没有双亲结点，就必须创建新的双亲结点，作为树的新根。这样树的须创建新的双亲结点，作为树的新根。这样树的高度就增加一层了。高度就增加一层了。n nB+树的删除仅在叶结点上进行树的删除仅在叶结点上进行。当在叶结点上。当在叶结点上删除一个关键码删除一个关键码-指针索引项后，结点中的子

19、树指针索引项后，结点中的子树棵数仍然不少于棵数仍然不少于 m1/2，这属于简单删除，其这属于简单删除，其上层索引可以不改变。上层索引可以不改变。n n如果删除的关键码是该结点的最小关键码，但如果删除的关键码是该结点的最小关键码，但因在其上层的副本只是起了一个引导查找的因在其上层的副本只是起了一个引导查找的“分界关键码分界关键码”的作用，所以上层的副本仍然可的作用，所以上层的副本仍然可以保留。以保留。n n如果在叶结点中删除一个关键码如果在叶结点中删除一个关键码-指针索引项后，指针索引项后，该结点中的子树棵数该结点中的子树棵数 n 小于结点子树棵数的下小于结点子树棵数的下限限 m1/2，必须做结

20、点的调整或合并工作。必须做结点的调整或合并工作。删除删除18删除删除12n n如如果果右右兄兄弟弟结结点点的的子子树树棵棵数数已已达达到到下下限限 m1/2，没没有有多多余余的的关关键键码码可可以以移移入入被被删删关关键键码码所所在在的的结结点点，这这时时必必须须进进行行两两个个结结点点的的合合并并。将将右右兄兄弟弟结结点点中中的的所所有有关关键键码码-指指针针索索引引项项移移入入被被删关键码所在结点，再将右兄弟结点删去。删关键码所在结点，再将右兄弟结点删去。删除删除33进行进行结点合并结点合并n n结结点点的的合合并并将将导导致致双双亲亲结结点点中中“分分界界关关键键码码”的的减减少少，有有可可能能减减到到非非叶叶结结点点中中子子树树棵棵数数的的下下限限 m/2 以以下下。这这样样将将引引起起非非叶叶结结点点的的调调整整或或合并。合并。n n如如果果根根结结点点的的最最后后两两个个子子女女结结点点合合并并，树树的的层层数就会减少一层。数就会减少一层。