数据结构第9章查找3动态查找表

1、第第9 9章章 查找查找查找的基本概念静态查找表动态查找表哈希表vB-树树 (B-Trees) 9.2 动态查找表动态查找表 B-树是二叉查找树的自然推广，是为磁盘存储而设计的一种平衡多路查找树。vB-树树 (B-Trees) 9.2 动态查找表动态查找表vB-树树 (B-Trees) 9.2 动态查找表动态查找表B-树的定义树的定义 一棵 m 阶的 B- 树，或为空树或为满足下列特性的 m 叉树： F111271FF391991F6453473FFFFFFF a b c d e f g h (1)、树中每个结点至多有 m 棵子树； (2)、若根结点不是叶子结点，则至

2、少有两棵子树；(3)、除根之外的所有非终端结点至少有 m/2 棵子树； 阶 m 可以事先任意指定， 一旦指定后就固定不变。 (4)、所有的非终端结点的结构为：（n, A0, K1, A1, K2, A2, , Kn, An） 其中，Ki ( i = 1, , n ) 为按升序排列的关键字； Ai (i = 0, , n) 为指向子树 根结点的指针，且 Ai 所指子树中所有结点的关键字均小于 ki，An 所指子树 中所有结点的关键字均大于 kn，n ( 对于根结点 1nm 1, 对于其它结点 m/2 1 n m 1) 为关键字的个数（或 n +1 为子树个数）。 (5)、所有叶子结点在同一个层次

3、上，且不含有任何信息。（可 以看作是外部结点或查找失败的结点，实际上这些结点不 存在，指向这些结点的指针为空）。 B-树的特点树的特点B- 树特点 平衡 多路 查找 树中所有叶子结点均不带信息且在树的同一层次上； 根结点或为叶子结点，或至少含有两棵子树； 所有非叶子结点均含有 n （m/2 nm）棵子树。 在 m 阶的 B- 树上，每个非终端结点可能含有： n 个关键字 Ki（1in）n m n 个指向记录的指针 Di（1in） n+1 个指向子树的指针 Ai（0in）非叶子结点中的多个关键字均自小至大有序排列； Ai -1 所指子树上所有关键字均小于 Ki ； Ai 所指子树上所有关键字均大

4、于 Ki 。 B-树的查找树的查找 F111271FF391991F6453473FFFFFFF a b c d e f g h 47 47 从根结点出发，沿指针搜索结点和在顺序（或折 半）两个过程交叉进行。 若查找成功，则返回指向被查关键字所在结点的指针和关键 字在结点中的位置；若则vB-树上查找关键字树上查找关键字479.2 动态查找表动态查找表1 135351 118181 111111 127271 139393 34747535364641 199992 243437878一棵4阶的B-树4753434735vB-树的插入树的插入9.2 动态查找表动态查找表

5、 设要插入关键值为k的记录，指向k所在记录的指针为p 首先找到k应插入的叶子结点，将k和p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m(结点的关键字数是否m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个。方法是： 申请一个新结点，由指针p指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。 538545 243 12375053 9061 70 95插入插入3030 373030插入插入8585

6、 8585617070 9070703 3阶阶B-B-树树12 37 70 插入1212 37 70324459037 703 12 244590插入24371245 70 90插入90插入45371245 7037 70124590371270从空树开始,插入关键字,创建一棵 3阶B-树37插入3737 703 124590插入31270324459037B-树的创建树的创建 37 , 70 , 12 , 45 , 90 , 3 , 24 空树37 70插入70分裂分裂分裂分裂vB-树的删除树的删除9.2 动态查找表动态查找表 若为最下层的非终端结点，且关键字个数不少于m/2，则删除完成；否

7、则，要进行“合并”结点的操作。 若删除的关键字为非终端结点中的Ki，则可以指针Ai所指子树的最小关键字Y替代Ki，然后删除相应结点的Y，实际问题转化为删除最下层非终端结点中的关键字的情形。vB-树的删除树的删除9.2 动态查找表动态查找表分为3种情况： a.被删除关键字所在结点的关键字不小于 m/2 b.被删除关键字所在结点的关键字等于 m/2 -1，而兄弟 m/2 -1 c.被删除关键字所在结点的关键字与其兄弟结点的关键字数目均等于 m/2 -1v在如图示在如图示3阶阶B-树中删除关键字树中删除关键字12，50，539.2 动态查找表动态查找表452433753 901005061,7045

8、243 123753 901005061 70删除12 (1)被删关键字所在结点中的关键字数目不小于m/2 ，则只需从该结点中删去该关键字Ki和相应指针Ai，树的其它部分不变。v在如图示在如图示3阶阶B-树中删除关键字树中删除关键字12，50，539.2 动态查找表动态查找表452433753 901005061,70452433761 901005370删除50(2)被删关键字所在结点中的关键字数目等于m/2 -1 ，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于m/2 -1 ，则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键

9、字的关键字下移至被删关键字所在结点中。 v在如图示在如图示3阶阶B-树中删除关键字树中删除关键字12，50，539.2 动态查找表动态查找表452433761 901005370删除53(3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于m/2 -1 。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)。45243379010061 70vB+树树9.2 动态查找表动态查找表B+树是B-树的一种变型, 它和B-树的差异是:

10、1.有n棵子树的结点含有n个关键字。2.叶子结点含有全部关键字及指向对应记录的指针, 且叶子结点间按关键字有序顺序链接。3.所有分支结点可看作索引, 结点中仅含其子树(根结点)中的最大(小)关键字。vB+树树9.2 动态查找表动态查找表vB+树树9.2 动态查找表动态查找表B+树是B-树的变体，也是一种多路搜索树：1.其定义基本与B-树同，除了：2.非叶子结点的子树指针与关键字个数相同；3.非叶子结点的子树指针Pi，指向关键字值属于Ki, Ki+1)的子树（B-树是开区间）；5.为所有叶子结点增加一个链指针；6.所有关键字都在叶子结点出现；vB+树树9.2 动态查找表动态查找表B-树B+树vB+树的搜索树的搜索9.2 动态查找表动态查找表 B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；B+的特性