数据结构文件和查找.ppt

第九章 文件及查找;9.1 文件概述;9.1 文件概述;;9.1 文件概述;9.1 文件概述;9.1 文件概述;9.1 文件概述;9.2 顺序文件; 顺序文件在存储介质中可以有两种不同的实现结构：连续结构和链结构。;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.2 顺序文件;9.3 索引文件;9.3 索引文件;9.3 索引文件;B树是一种平衡的多路查找树，它在数据处理中有着巨大的作用，已经成为数据处理中主要的文件组织形式。它以占用存储空间少，查找效率高的优势在数据库系统的索引技术中占据了重要的地位。 定义 ：一棵m阶的B树，或者为空树，或为满足下列特性的m叉树。 （1）对树中子树的要求： 每个结点至多有m棵子树。 若根结点不是叶子结点，则至少有两棵子树。 除根结点之外的所有非终端结点至少有?m/2? 棵子树。;（2）对树中关键字个数的要求： 所有的非终端结点中包含以下信息(n，A0，K1，A1，K2，…，Kn，An)。 其中，n为关键字个数，?m/2? ?1≤n≤m?1；Ki（i=1,2,…,n）为关键字，且KiKi+1；Ai为指向子树根结点的指针（i=0,1,…,n），且指针Ai－1所指子树中所有结点的关键字值均小于Ki（i=1,2,…,n），An所指子树中所有结点的关键字值均大于Kn。 （3）对叶子结点的要求： 所有的叶子结点都出现在同一层次上，并且不带信息（可以看做是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。;例 一棵5阶的B树 ;9.4 B-树与B+树;9.4 B-树与B+树;9.4 B-树与B+树;9.4 B-树与B+树;B+树是应文件系统所需而产生的一种B树的变形树。一棵m阶的B+树和m阶的B树的差异在于： （1）在B树中，每个结点含n个关键字，n+1棵子树；在B+树中，每个结点含n个关键字，n棵子树。 （2）在B树中，每个结点中关键字个数n的取值范围?m/2? ?1≤n≤m?1（除根）结点外。 在B+树中，每个结点中关键字个数n的取值范围?m/2?≤n≤m（除根结点外），1≤n≤m（根结点）。 （3）B+树中所有叶子结点包含了全部关键字及指向对应记录的指针，且所有叶子结点按关键字由小到大顺序依次链接。 （4）B+树中所有非叶子结点仅起索引作用，结点中仅含有其子树中的最大（或最小）关键字。 ;9.4 B-树与B+树;9.4 B-树与B+树;9.5 杂凑（Hash）文件;9.5 杂凑（Hash）文件;9.5 杂凑（Hash）文件;9.5 杂凑（Hash）文件;9.5 杂凑（Hash）文件;散列技术的关键问题： ⑵ 冲突的处理。如何采取合适的处理冲突方法来解决冲突。 ① Hash函数。若Hash函数选择得当，就可使Hash地址尽可能均匀地分布在Hash地址空间上，从而减少冲突的发生；否则，若Hash函数选择不当，就可能使Hash地址集中于某些区域，从而加大冲突的发生。 ② 处理冲突的方法。选择适当的Hash函数可以减少冲突，但不能避免冲突，因此当冲突发生时，必须有较好的处理冲突的方法。 ③ Hash表的装填因子。 ;9.5 杂凑（Hash）文件;9.5 杂凑（Hash）文件;根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。 ;对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。 ;将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。 ;由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。 ;9.5 杂凑（Hash）文件; 例：有关键字序列为{36，7，40，11，16，81，22，8，14}，Hash表表长为11， Hash(key)=key % 11，用线性探测法处理冲突，???立Hash表 ;例 以上例中的关键字建立Hash表。用二次探测法处理冲突，建立Hash表 ;9.5 杂凑（Hash）文件;9.5 杂凑（Hash）文件;例 关键字序列为{36，7，40，11，16，81，22，8，14}，Hash函数为 Hash(key)=key % 11 用链地址法处理冲突，建立Hash表 ;9.5 杂凑（Hash）文件;由于冲突的存在，产生冲突后的查找仍然是给定值与关键码进行比较的过程。 在查找过程中，关键码的比较次数取决于产生冲突的概率。而影响冲突产生的因素有： （1）散列函数是否均匀 （2）处理冲突的方法 （3）散列表的装载因子 α=表中填入的记录数/表的长度