数据结构文件及查找31.ppt

第九章 文件及查找 提纲 9.1 文件概述 9.2 顺序文件 9.3 索引文件 9.4 B-树与B+树 9.5 杂凑（Hash）文件 9.1 文件概述 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.2 顺序文件 9.3 索引文件 9.3 索引文件 9.3 索引文件 9.4 B-树与B+树 B树是一种平衡的多路查找树，它在数据处理中有着巨大的作用，已经成为数据处理中主要的文件组织形式。它以占用存储空间少，查找效率高的优势在数据库系统的索引技术中占据了重要的地位。 定义 ：一棵m阶的B树，或者为空树，或为满足下列特性的m叉树。 （1）对树中子树的要求： 每个结点至多有m棵子树。 若根结点不是叶子结点，则至少有两棵子树。 除根结点之外的所有非终端结点至少有?m/2? 棵子树。 9.4 B-树与B+树 （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）对叶子结点的要求： 所有的叶子结点都出现在同一层次上，并且不带信息（可以看做是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。 9.4 B-树与B+树 例 一棵5阶的B树 9.4 B-树与B+树 例 一棵7阶的B树 在一棵7阶的B树中，树根结点的关键字个数最少为1，最多为m?1=6，子树个数最少为2，最多为m=7； 每个非树根结点的关键字个数最少为「m/2? －1=「7/2??1=3，最多为m?1=6，子树个数最少为「m/2?=「7/2?=4，最多为m=7。 9.4 B-树与B+树 例1 在一棵3阶B树上依次插入关键字65、24、50和38 9.4 B-树与B+树 例2 有下列关键字序列{20，54，69，84，71，30，78，25，93，41，7，76，51，66，68，53，3，79，35，12，15，65}，建立5阶B树 9.4 B-树与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+树 B+树定义 一个m阶B+树满足下列条件： (1)每个分支节点至多m棵子树 (2)出根结点外，其它每个分支结点至少有ceiling(m/2)棵子树 (3)跟结点至少有两颗子树 (4) 有n棵子树的结点有n个关键字 (5)叶子结点中存放了数据文件的中记录的关键字及指向该记录的指针，或存放数据文件分块后没块的最大关键字及指向该块的指针，也结点关键字值按大小顺序链接。 (6)所有分支结点可以看成是索引的索引，结点中仅包含它的各个子结点中最大（或最小）关键字及指向子结点的指针 9.4 B-树与B+树 B+树操作 （1）查找 （2）插入 （3）删除 9.5 杂凑（Hash）文件 查找操作要完成什么任务？ 我们学过哪些查找技术？这些查找技术的共性？ 顺序查找、二叉排序树查找等。 以上讨论的查找方法，由于记录的存储位置与关键字之间不存在确定的关系，因此查找时需要进行一系列对关键字的查找比较，即“查找算法”是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。 9.5 杂凑（Hash）文件 能否不用比较，通过关键码直接确定存储位置？ 理想的情况是，依据关键字直接得到其对应的记录位置，即要求关键字与记录位置间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的记录位置。 9.5 杂凑（Hash）文件 散列技术仅仅是一种查找技术吗？ 散列既是一种查找技术，也是