参考第9章查找part

1、第九章 查找主讲：戚玉涛第九章 查找9.1 查找的基本概念9.2 静态查找表基于线性表的查找法 9.3 动态查找表基于树表的查找法 9.4 哈希表计算式查找法动态查找表用树型结构存储表二叉排序树平衡二叉排序树B树 B- 树 B+ 树B-树B-树的定义：B-树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。一棵m阶B-树或者是一棵空树,或者是满足下列要求的m叉树：(1)树中每个结点至多有m棵子树；(2)若根结点不是叶子结点，则根结点至少有两棵子树；(3)除根结点之外的所有非终端结点至少有m/2棵子树；(4)所有的非终端结点中包含下列信息数据 ( n, A0, K1, A1,

2、 K2, A2, , Kn, An )n：关键字个数。除根结点外,其它结点的n( m/2-1nm-1)；Ki：关键字，满足kiki+1(递增有序)；Ai：指向子树根结点的指针，指针Ai-1所指子树中所有结点关键字均小于等于Ki，An所指子树中所有结点的关键字均大于Kn。(5) 所有叶子结点都在同一层上,并且不带信息（可看作外部结点或查找失败的结点）。B-树中每个结点中的关键字从小到大排列叶结点不包含关键字可看成外部结点，指向其指针为空叶结点总数=树中关键字总数+1351F432781112713914735364991181FFFFFFFFFFFtabcdefgh例：4阶B-树，深度为4B-树

3、的操作查找操作插入操作删除操作B-树的查找B-树的查找过程：1.把根结点取来，在根结点所包含的关键字K1，Kn中查找给定的关键字(关键字个数不多时，可用顺序查找；个数较多时，可用二分查找)2.若找到等于给定值的关键字，则查找成功。否则，一定可以确定要查找的关键字是在某个Ki和Ki+1之间(因为在结点内部的关键字是排序的)3.于是，取Ai所指向的结点继续查找。4.重复（2）（3），直到找到，或指针Ai为空时，查找失败。 351F432781112713914735364991181FFFFFFFFFFFtabcdefgh查找操作：4阶B-树，深度为4查找key=47查找key=23B-树的查找B

4、-树的查找的两种访问情况：在树中找结点（在磁盘上进行的，内外存交换）在结点中找关键字（在内存中进行的）B-树的查找过程是一个顺指针查找结点和在结点的关键字中进行查找交替进行的过程。因此B-树的查找时间与B-树的阶数m和B-树的高度h直接有关，必须加以权衡。在B-树上进行查找，查找成功所需的时间取决于关键字所在的层次，查找不成功所需的时间取决于树的高度。需要了解树的高度h 与树中的关键字个数 N 之间的关系。B-树查找分析在磁盘上查找的次数，即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。含N个关键字的m阶B-树的最大深度是多少？若一棵L+1层的m阶B-树包含N个关键字，

5、查找失败的关键字会有N+1种情况，而B-树叶结点表示树中并不存在的外部结点，正好对应N+1种查找失败的情况。因此，B-树有N+1个叶节点，叶节点都在第L+1层。第一层为根，至少一个结点，根至少有两个孩子，即第二层至少有两个结点。B-树查找分析除根和树叶外，其他结点至少有m/2个孩子。因此，第三层至少有2 m/2个结点，第四层至少有2(m/2)2个结点第L+1层至少有2(m/2)L-1个结点，于是有：在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上，涉及的结点数不超过L层次数。即： N+12( m/2 )L-1 B-树查找分析若B-树的阶数 m = 199，关键字总数 N

6、= 1999999，则B-树的高度 h 不超过 log100 1000000 +1= 4这意味着若N = 1999999 ，m=199，则L至多等于4。也就是说，一次查找最多进行L次访问外部存储器的存取操作。因此，B-树的查找效率是相当高的，是一种组织和维护外存文件系统非常有效的数据结构。 B-树的插入对于叶结点处于第L+1层的B-树，插入的关键字总是进入第L层的非叶子结点。每次插入一关键字是在最低层（L层）某结点添加一关键字若该结点的关键字个数不超过m-1，则插入完成，否则结点分裂。B-树的插入结点分裂的方法： 令 s = m/2，在原结点中保留 （A0，K1， ， Ks-1，As-1）；

7、建新结点 （As，Ks+1， ，Kn，An）； 将（Ks，p）插入双亲结点若双亲为空，则建新的根结点。例如：下图的3阶B-树，深度为453 903 12375061 7010045bta24bcdefgh53 903 12 375061 7010045bta24bcdefgh30插入30例：3阶B-树的插入53 903 12 30 375061 7010045bta24bcdefgh插入26分裂d2653 905061 7010045bta24 30b3 12c37defgh26d例：3阶B-树的插入插入8553 905061 70 10045bta24 30b3 12c37defgh26d8

8、5分裂g53 905010045bta24 30b3 12c37defgh26dg618570例：3阶B-树的插入535010045 bta24 30b3 12c37defgh26dg90e6185分裂e70535010045 70 bta24 30b3 12c37defgh26dg90e6185插入77例：3阶B-树的插入535010045 70 bta 24 30b3c37defgh26dg90e618512c分裂c7分裂b5350100 45 70 bta7b3c37defgh26dg90e618512c30b24例：3阶B-树的插入分裂a535010045btm7b3c37defgh2

9、6dg90e618512c30b24a70a例：3阶B-树的插入B-树删除B-树上删除一个关键字的步骤：1.找到该关键字所在结点2.若该结点为最下层非终端结点，则根据情况执行删除，借调或合并操作，转；否则，转 。3.若该结点为非最下层非终端结点中的关键字Ki ，则以该结点Ai所指子树中的最小关键字x来代替被删关键字Ki所在的位置，然后在x所在的结点中删除 x（最下层非终端结点中的关键字）。4.结束B-树删除在最下层非终端结点上删除关键字有 3 种情况：和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1；若删除后结点中关键字个数小于m/2-1

10、 ，要从其左(或右)兄弟结点“借调”关键字；若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。情况1 直接删除：被删关键字所在结点中的关键字个数 n m/2，则直接删去该关键字Ki和相应指针Ai，树的其它部分不变 。删除55情况2 借调：被删关键字所在结点中关键字个数 n = m/2 -1，与该结点相邻的右兄弟 (或左兄弟) 结点的关键字个数 n m/2 -1，则进行关键字借调。关键字借调的两个步骤：将双亲结点中刚刚大于 (或小于) 该被删关键字的关键字 Ki (1 i n) 下移；将右兄弟 (或左兄弟) 结点中的最小 (或最大)关键字上移到双亲结点的 K

11、i 位置；删除65情况3 合并：被删关键字所在结点中关键字个数 n = m/2 -1，若这时与该结点相邻的右兄弟 (或左兄弟) 结点的关键字个数 n = m/2 -1，则必须合并结点。合并的方法：删除关键字的结点与其右 (或左)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。结点合并删除55B-树删除在非最下层结点上删除关键字的过程：要删除关键字Ki，在删去该关键字后，以该结点Ai所指子树中的最小关键字x来代替被删关键字Ki所在的位置，然后在x所在的结点中删除 x。这样就把在非最下层结点上删除关键字的问题转化成了在最下层结点上删除关键字的问题。删除50B+树B+树可以看作是B-树的一种变形，在实现文件索引结构方面比B-树使用得更普遍。一棵m阶B+树与m阶B-树的差异：有n棵子树的结点中含有n个关键