第八章 文件内容概述在实际的应用中，特别是涉及事务管理类型的问题，比如企业的管理信息系统、大型的信息检索系统、数字图书馆等问题中将涉及大量数据，由于内存不适合存储这类数据量大且需长期保存的数据，因此这类数据需要存储在外存储器上。习惯上称存储在内存中的数据集合为表，称存储在外存储器（二级存储器）中的数据集合为文件。本章讨论文件的相关概念、表示方法及各种运算的实现方法。重点与难点重点为顺序文件的操作和索引顺序文件的结构。难点是散列文件的设计模型桶散列。思考与习题1顺序文件的优缺点2直接文件的优点3VSAM的总体结构4假设在一个按桶散列的文件组织中，若有B个桶，现在要对文件进行重组成2B个桶，试用算法描述这种重组。5倒排文件的结构特点与优点第一节文件概述本节主要介绍文件的逻辑结构、物理结构以及文件操作。1、与文件有关的四个术语（域、纪录、文件、数据库）（1）域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数据对象的属性，不可分割的域含有一个简单的值，如姓名、日期等。域的特征可由长度和数据类型表示。域的长度可以是固定的，也可以是可变的。可变长度的域包含两个或三个子域：要保存的实际值和域名，在某些情况下还需要域的长度。（2）记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。例如，一个职员记录可以包括姓名、社会保险号、工作类型、参加工作时间等。根据设计的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变的，则该记录就是可变长度的记录。（3）文件（File）是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。文件有一个惟一的名字，可以被创建或删除。（4）数据库（Database）是一组相关的数据，它的本质特征是数据单元间存在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种或多种不同类型的文件组成。2、构建文件物理结构的方法文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系。有两类方法可用来构造文件的物理结构。第一类称为计算法，其实现原理是设计映射算法，例如线性计算法、杂凑法等，通过对记录关键字的计算转换成对应的物理块地址，从而找到所需记录。直接寻址文件、计算寻址文件，顺序文件均属此类。计算法的存取效率较高，又不必增加存储空间存放附加控制信息，能把分布范围较广的关键字均匀地映射到一个存储区域中。第二类称为指针法，这类方法设置专门指针，指明相应记录的物理地址或表达各记录之间的关联。索引文件、索引顺序文件、倒排文件等均属此类。使用指针的优点是可将文件信息的逻辑次序与在存储介质上的物理排列次序完全分开，便于随机存取，便于更新，能加快存取速度。但使用指针要耗用较多存储空间，大型文件的索引查找要耗费较多处理器时间，所以，究竟采用哪种文件存储结构，必须根据应用目标、响应时间和存储空间等多种因素进行权衡。3、文件的相关操作对文件的操作主要有记录的检索、插入、删除、更新和文件排序。1记录的检索检索文件的某条记录或若干条记录。记录的检索方式有三种：（1）检索下一条记录：检索当前记录的下一条记录。（2）检索第i条记录：按照所给文件记录的逻辑顺序号检索记录。（3）按关键字检索：给定一个值，查询一个或一批关键字与给定值相关的记录。对于数据库文件可以有如下四种查询方式：（a）简单检索：查询关键字等于给定值的记录。例如检索学号为200507001的学生记录。（b）区域检索：查询关键字值在某个区域内的记录。例如检索某个年级数据结构考试成绩在8090分的学生记录。（c）函数检索：给定关键字的某个函数，检索符合条件得记录。例如查询总分在全体学生的平均分以上的记录。（d）布尔检索：以上三种检索式用布尔运算符组合起来的检索。例如，查询总分在600分以上且数学在100分以上，或者总分在平均分以下的外语在98分以上的全部记录。2记录的插入在文件的指定位置插入一个新记录。文件位置的指定由记录的检索功能完成，记录的插入实际是在记录检索功能的基础上增加插入一条新记录的功能。3记录的删除把指定位置上的记录删除。这通常有以下两种情况：（1）删除文件的第i条记录。这实际是在记录检索功能的基础上增加删除一条记录的功能。（2）删除文件中符合给定条件的记录。这实际上是在按关键字检索功能的基础上增加删除对应记录的功能。4记录的更新修改指定位置上的记录。通常有如下两种情况：（1）更新文件中第i条记录的某些数据项值。即在检索第i个记录功能的基础上增加更新该记录的某些数据项的功能。（2）更新文件中符合给定条件的记录的某些数据项。这实际上是在按关键字检索功能的基础上增加更新对应记录某些数据项的功能。5文件排序根据给定的关键字，对文件中的记录按关键字值升序或降序重新进行组织。第二节顺序文件顺序文件是在批处理文件、系统文件中用得最多的文件组织方式。本节介绍顺序文件的特点和操作。1、顺序文件的优缺点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。其特点是：（1）若存取文件中第i个记录，必须先搜索在它之前的i-1个记录。（2）插入新的记录时只能追加在文件的末尾。（3）若要更新文件中的某个记录，则必须将整个文件进行复制。顺序文件的基本优点是：顺序存取记录时速度较快。所以，批处理文件、系统文件用得最多。采用磁带存放顺序文件时，总可以保持快速存取的优点。若以磁盘作存储介质时，顺序文件的记录也按物理邻接次序排列，因而顺序的磁盘文件能像磁带文件一样进行严格的顺序处理。然而，由于多程序访问，在同一时间另外的用户作业可能驱动磁头移向其它文件，因而可能要花费较多的处理器时间降低了这一优越性。顺序文件的主要缺点是：建立文件前需要能预先确定文件长度，以便分配存储空间；修改、插入和增生文件记录有困难；对直接存储器作连续分配，会造成少量空闲块的浪费。2、分块插值查找的算法假设文件由记录R1，R2，Rn组成，并已知记录按关键字升序排列：K1K2KN，h、l分别表示当前查找范围的上界和下界。现在我们要查找关键字值为K的记录。我们回顾一下折半查找的具体做法，首先选取查找范围内的中间点i=，然后将Ki与K进行比较。插值法查找并不是选取查找范围的中间点作为比较点，而是按关键字的比例选取l和h之间的某一点ii=这表示i的选取与查找范围的下界关键字、上界关键字和要查找的关键字有关。然后将Ki与K比较，若K=Ki，则Ri就是要找的记录；若KKi，则下一步查找范围的上界为i-1，下界为l；若KKi，则下一步查找范围的上界为h，下界为i+1。由于文件记录存放在外存的物理块上，因此文件的查找采用分块插值查找，此时，h、l、i表示物理块号。假设整个文件的最小关键字为K0，最大关键字为Km，要查找的关键字为K，整个文件分为N个物理块，并设：low:查找范围内的最小物理块号；high:查找范围内的最大物理块号；Li：第i个物理块内的记录的最小关键字；Hi：第i个物理块内的记录的最大关键字分块插值查找的算法描述如下：（1）初始化low=1；high=N。（2）反复执行下面操作，直到highlow成立(b)读取第i个物理块，获得Li和Hi(c)分下面三种情况执行lLiKHi时，查找成功，第i个物理块即为所求;lKHi时，执行low=i+1;lKLi时，执行high=i-1;(3)查找失败，算法结束。按块插值查找是一种比较高速的查找方法。第三节直接文件(散列文件)在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件（散列文件）。本节介绍典型的直接文件的设计模型桶（Bucket）散列法。1、桶散列方法的基本思想桶散列方法的基本思想是把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。散列函数H把关键字key值转换成存储桶号，即H(key)表示具有关键字key的记录所在的存储桶号。如果一个桶溢出，即它容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更多的记录。2、桶散列结构上是操作（查找、插入、删除）的实现思想【例8-1】图8-2表示一个具有B个桶的散列文件。为了使图例易于处理，假设每个物理块只存放一个逻辑记录，且B=4，即散列函数的返回值介于03之间。假设记录的关键字为字母af，并且假定h(d)=0，h(c)=h(e)=1，h(b)=2，h(f)=h(a)=3。因此，这六个记录的分布如图8-2所示。在散列文件上可以进行查找、插入、删除、修改等操作，下面讨论这些操作的主要思路。1.查找假设要查找一个关键字值等于一个给定值key的记录。我们首先计算H（key），得到存储桶号i，然后查看存储桶目录表以找到第i号存储桶的第一个物理块地址，把该物理块调入内存，然后顺序搜索其中的每一个记录，检查有无关键字值等于key的记录，若找到就结束查找，否则根据该物理块上的链表指针找出下一个物理块并调入内存，以同样方式查找。以此类推直到找到关键字值等于key的记录或断定不存在关键字值等于key的记录（即桶中所有物理块全部查找完毕）为止。2插入插入前先根据上述查找过程查找桶号为H（key）的存储桶中是否存在关键字值等于key的记录。如果存在，则表示出错，因为插入一个与文件中已有记录具有相同关键字值的记录是没有意义的。若不存在相应的记录，则将该记录存放到该存储桶的空闲物理块中。如果存储桶中所有的物理块都没有空间，我们就增加一个新的溢出块到该存储桶的链表上，并将新记录存入其中。3删除首先根据查找过程在桶号为H（key）的存储桶中寻找是否存在关键字值等于key的记录，若不存在，则表示出错。若找到，则将该记录的删除标志置为1，表示该记录已被删除。如果我们可以将记录在物理块中移动，那么删除记录后，我们可选择合并同一链表上的物理块，但合并一条链上的物理块随时都要冒风险，因为当我们往一个存储桶里交替地插入或删除记录时，可能每一步都会导致物理块的创建或删除。4修改假定我们要修改关键字值为key的记录的一个或多个域，若需要修改的域中涉及到关键字，则这样的修改相当于删除加插入。因为散列文件中，关键字值的变化可能改变记录的存储位置，修改后的记录可能与原记录位于不同的存储桶中，因而需要先删除原记录，再插入新修改的记录。如果修改的域没有涉及到关键字，则首先查找到这个记录，找到后调入内存进行修改，修改后再写回存储桶（外存）中，若找不到，则出错。3、可扩展散列文件的组织方式可扩展散列文件的组织方式是：散列函数H把关键字key转换成一个定长的二进制位串k（伪关键字）,取k前i位二进制数（设为k）作为存储桶目录表中的目录项号，即表示目录表中第k个目录项，目录项中的指针指向的物理块就是具有关键字key的记录所在的物理块；存储桶目录项的个数为2i。所选择散列