B树的结构详细讲解.ppt

《B树的结构详细讲解.ppt》由会员分享，可在线阅读，更多相关《B树的结构详细讲解.ppt（20页珍藏版）》请在金锄头文库上搜索。

1、7、B_ 树和树和 B+ 树树 1、为什么采用、为什么采用B_ 树和树和 B+ 树：树：大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。在在 1970 年由年由 R bayer 和和 E macreight 提出用提出用B_ 树作为索引组织文件。提高访问速度、减少时间。树作为索引组织文件。提高访问速度、减少时

2、间。内存内存E.G: 用二叉树组织文件，当文件用二叉树组织文件，当文件的记录个数为的记录个数为 100，000时，要找时，要找到给定关键字的记录，需访问外存到给定关键字的记录，需访问外存17次（次（log100,000）,太长了！太长了！502510751535609020304055708095索索引引文文件件数数据据文文件件文件头，可常驻内存文件头，可常驻内存文件访问示意图：索引文件、数据文件存在盘上文件访问示意图：索引文件、数据文件存在盘上7、B_ 树和树和 B+ 树树 2、B_ 树是一种多分支数，首先介绍树是一种多分支数，首先介绍 m 阶阶 B_ 树：树： 定义：定义： m 阶阶 B_

3、 树满足或空，或：树满足或空，或：A、根结点要么是叶子，要么至少有两个儿子根结点要么是叶子，要么至少有两个儿子B、除根结点和叶子结点之外，每个结点的儿子个数为除根结点和叶子结点之外，每个结点的儿子个数为: m/2 = s = mC、有有 s 个儿子的非叶结点具有个儿子的非叶结点具有 n = s 1 个关键字，即个关键字，即: s = n + 1 这些结点的数据信息为：这些结点的数据信息为： （n, A0, K1, R1, A1, K2, R2, A2, Kn, Rn, An） 这里：这里：n: 关键字的个数关键字的个数 A0： K1 且且 Kn 的结点的地址（指在该的结点的地址（指在该 B_

4、树中）树中） 注意：注意：K1 =K2 = . = KnD、所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。7、B_ 树和树和 B+ 树树 例如：例如：m = 4 阶阶 B_ 树。树。除根结点和叶子结点之外，每个结点的儿子个数除根结点和叶子结点之外，每个结点的儿子个数至少为至少为 m/2 = 2 个；结点的关键字个数至少为个；结点的关键字个数至少为 1 。该。该 B_ 树的深度为树的深度为 4。叶子结点都在第叶子结点都在第 4 层上。层上。1，993，47，58，641，391，271，112，43，7

5、81，181，35FFFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层)7、B_ 树和树和 B+ 树树 3、B_ 树的查找代价分析：树的查找代价分析： 查找过程，类似于二叉树的查找。如查找关键字为查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。的记录。 从根开始查找，如果从根开始查找，如果 Ki = KEY 则查找成功，则查找成功，Ri 为关键字为为关键字为 KEY 的记录的地址。的记录的地址。 若若 Ki KEY Ki+1; 查找查找 Ai 指向的结点指向的结点 若若 KEY Kn; 查找查找 An指向的结点指向的结点 若若 找到

6、叶子，则查找失败。找到叶子，则查找失败。注意：每次查找将去掉注意：每次查找将去掉 （s-1）/s 个分支，比二分查找快得多。个分支，比二分查找快得多。 设关键字的总数为设关键字的总数为 N ，求求 m阶阶 B_ 树的最大层次树的最大层次 L。层次层次结点数结点数关键字的个数（最少）关键字的个数（最少）111222（ m/2 -1）3 2（ m/2 ） 2（ m/2 ） （ m/2 -1）4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1）L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1）L+1 2（ m/2 ）L-1所以，所以，N=1 2（ m/2 -1） +.

7、+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1故：故：Llog （N+1）/2）+ 17、B_ 树和树和 B+ 树树 3、B_ 树的查找代价分析：树的查找代价分析： 设关键字的总数为设关键字的总数为 N ，求求 m阶阶 B_ 树的最大层次树的最大层次 L。故：故：Llog m/2 （N+1）/2）+ 1设设 N 1000，000 且且 m256 ，则则 L m-1, 则该结点满。必须分裂成两个结点。否则不满结束。则该结点满。必须分裂成两个结点。否则不满结束。如结点原为：如结点原为： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1

8、)）插入一个关键字之后变为：插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2), (Km, Am)）该结点将进行分裂：该结点将进行分裂： . (K m/2 , p ) .（m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。PP(K m/2 , p ) 数据项数据项插入上层结点之中插入上层结点之中7、B_ 树和树和 B+ 树

9、树 例如：例如：3 阶阶 B_ 树的插入操作。树的插入操作。m=3, m/2 - 1 = 1; 至少至少 1 个关键字，二个儿子结点。个关键字，二个儿子结点。3，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入插入7、B_ 树和树和 B+ 树树 5、B_ 树的删除操作树的删除操作1、查找具有给定键值的关键字、查找具有给定键值的关键字 Ki 2、如果如果 在在第第 L 层，可直接删除（注意：第

10、层，可直接删除（注意：第 L+1 层为叶子结点），转层为叶子结点），转 4 。3、否则，则首先生成、否则，则首先生成 “替身替身”。用。用 的右子树中的最左面的结点的关键字值，即的右子树中的最左面的结点的关键字值，即 处于第处于第 L 层上的最层上的最小小 关键字值取代关键字值取代 。然后，删除第。然后，删除第 L 层上的该关键字。层上的该关键字。4、从第、从第 L 层开始进行删除。层开始进行删除。 A、不动：若删除关键字值的那个结点的关键字的个数仍处于不动：若删除关键字值的那个结点的关键字的个数仍处于 m/2 -1和和 m-1之间。则结束。之间。则结束。 B、借：若删除关键字值的那个结点的关

11、键字的个数原为借：若删除关键字值的那个结点的关键字的个数原为 m/2 -1 。而它们的左或右邻居结而它们的左或右邻居结 点的关键字的个数点的关键字的个数 m/2 -1 ; 则借一个关键字过来。处理结束。则借一个关键字过来。处理结束。 C、并：若该结点的左或右邻居结点的关键字的个数为并：若该结点的左或右邻居结点的关键字的个数为 m/2 -1 ; 则执行合并结点的操作。则执行合并结点的操作。如结点原为：如结点原为： （ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1L 第第 L 层：找到了被删结点的替身。层：

12、找到了被删结点的替身。7、B_ 树和树和 B+ 树树 例如：例如：3 阶阶 B_ 树的删除操作。树的删除操作。m=3, m/2 - 1 = 1; 至少至少 1 个关键字，二个儿子结点。个关键字，二个儿子结点。3244553 90371005061，70被删关键字被删关键字3244561 90371005370借：向被删结点方向旋转借：向被删结点方向旋转假定再删除该关键字假定再删除该关键字32445 903710061，70假定再删除该关键字假定再删除该关键字3，2445 9010061，703，24 45 9010061，70并并并并并并并：和父结点的一个关键字、及邻居合并。有可并：和父结点的

13、一个关键字、及邻居合并。有可能进行到根，使能进行到根，使B_ 树的深度降低一层！树的深度降低一层！B+B+树树树树n nB+B+树树可可以以看看作作是是B_B_树树的的一一种种变变形形，在在实实现现文文件件索索引引结结构构方方面比面比B_B_树使用得更普遍。树使用得更普遍。n n一棵一棵 m m 阶阶B+B+树可以定义如下：树可以定义如下： 树中每个非叶结点最多有树中每个非叶结点最多有 m m 棵子树；棵子树； 根根结结点点 ( (非非叶叶结结点点) ) 至至少少有有 2 2 棵棵子子树树。除除根根结结点点外外, , 其其它它的的非非叶叶结结点点至至少少有有 m m/2/2 棵棵子子树树；有有

14、 n n 棵棵子子树树的的非非叶结点有叶结点有 n n- -1 1 个关键码。个关键码。 所所有有叶叶结结点点都都处处于于同同一一层层次次上上，包包含含了了全全部部关关键键码码及及指指向向相相应应数数据据对对象象存存放放地地址址的的指指针针，且且叶叶结结点点本本身身按关键码从小到大顺序链接按关键码从小到大顺序链接； 每个叶结点中的子树棵数每个叶结点中的子树棵数 n n 可以多于可以多于 m m，可以少于，可以少于 m m，视关键码字节数及对象地址指针字节数而定。，视关键码字节数及对象地址指针字节数而定。 若设结点可容纳最大关键码数为若设结点可容纳最大关键码数为 m m1 1，则指向对象的，则指

15、向对象的地址指针也有地址指针也有 m m1 1 个。个。 结点中的子树棵数结点中的子树棵数 n n 应满足应满足 n n m m1/21/2 , , m m11。 若根结点同时又是叶结点，则结点格式同叶结点。若根结点同时又是叶结点，则结点格式同叶结点。 所有的非叶结点可以看成是索引部分，结点中关键码所有的非叶结点可以看成是索引部分，结点中关键码 K Ki i 与指向子树的指针与指向子树的指针 P Pi i 构成对子树构成对子树 ( (即下一层索引块即下一层索引块) ) 的索引项的索引项 ( ( K Ki i, , P Pi i ) )，K Ki i 是子树中最小的关键码。是子树中最小的关键码。

16、 特别地，子树指针特别地，子树指针 P P0 0 所指子树上所有关键码均小所指子树上所有关键码均小于于 K K1 1。结点格式同。结点格式同B_B_树。树。n n叶结点中存放的是对实际数据对象的索引。叶结点中存放的是对实际数据对象的索引。n n在在B+B+树中有两个头指针：一个指向树中有两个头指针：一个指向B+B+树的根结点，一树的根结点，一个指向关键码最小的叶结点。个指向关键码最小的叶结点。n n可对可对B+B+树进行两种搜索运算：树进行两种搜索运算：循叶结点链顺序搜索循叶结点链顺序搜索另一种是从根结点开始，进行自顶向下，直至叶结点的随另一种是从根结点开始，进行自顶向下，直至叶结点的随机搜索

17、。机搜索。n n在在B+B+树上进行随机搜索、插入和删除的过程基本上与树上进行随机搜索、插入和删除的过程基本上与B_B_树树类似。只是在搜索过程中，如果非叶结点上的关键码等于类似。只是在搜索过程中，如果非叶结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针向下，一直查给定值，搜索并不停止，而是继续沿右指针向下，一直查到叶结点上的这个关键码。到叶结点上的这个关键码。n nB+B+树的搜索分析类似于树的搜索分析类似于B_B_树。树。 n nB+B+树的插入仅在叶结点上进行树的插入仅在叶结点上进行。每插入一个关键码。每插入一个关键码- -指针索指针索引项后都要判断结点中的子树棵数是否超出范围。

18、引项后都要判断结点中的子树棵数是否超出范围。n n当插入后结点中的子树棵数当插入后结点中的子树棵数 n n m m1 1 时，需要将叶结点分裂时，需要将叶结点分裂为两个结点，它们的关键码分别为为两个结点，它们的关键码分别为 ( (m m1+1)/21+1)/2 和和 ( (m m1+1)/21+1)/2 。并且它们的双亲结点中应同时包含这两个结。并且它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后，问题归于在非叶结点点的最小关键码和结点地址。此后，问题归于在非叶结点中的插入了。中的插入了。n n在非叶结点中关键码的插入与叶结点的插入类似，但非叶在非叶结点中关键码的插入与叶结点的

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

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

21、除删除12n n如如果果右右兄兄弟弟结结点点的的子子树树棵棵数数已已达达到到下下限限 m m1/21/2 ，没没有有多多余余的的关关键键码码可可以以移移入入被被删删关关键键码码所所在在的的结结点点，这这时时必必须须进进行行两两个个结结点点的的合合并并。将将右右兄兄弟弟结结点点中中的的所所有有关关键键码码- -指指针针索引项移入被删关键码所在结点，再将右兄弟结点删去。索引项移入被删关键码所在结点，再将右兄弟结点删去。删除删除33进行进行结点合并结点合并n n结结点点的的合合并并将将导导致致双双亲亲结结点点中中“ “分分界界关关键键码码” ”的的减减少少，有有可可能能减减到到非非叶叶结结点点中中子子树树棵棵数数的的下下限限 m m/2/2 以以下下。这这样样将将引起非叶结点的调整或合并。引起非叶结点的调整或合并。n n如如果果根根结结点点的的最最后后两两个个子子女女结结点点合合并并，树树的的层层数数就就会会减减少少一层。一层。20 物料管理物料管理SEAR20Algorithms and DataStructures:Searchn n郑郑州州诚诚诺诺数数据据恢恢复复正正式式加加入入海海月月数数据据恢恢复复成成功功签签约约成成为为 海海月月( (国国际际) )郑郑州州数数据据恢恢复复中中心心 网网站站总总部部 分分部部 希望大家以后多多关注希望大家以后多多关注 谢谢大家谢谢大家