山大《数据结构》讲义08文件

1、第八章 文件内容概述在实际的应用中，特别是涉及事务管理类型的问题，比如企业的管理信息系统、大型的信息检索系统、数字图书馆等问题中将涉及大量数据，由于内存不适合存储这类数据量大且需长期保存的数据，因此这类数据需要存储在外存储器上。习惯上称存储在内存中的数据集合为表，称存储在外存储器（二级存储器）中的数据集合为文件。本章讨论文件的相关概念、表示方法及各种运算的实现方法。重点与难点重点为顺序文件的操作和索引顺序文件的结构。难点是散列文件的设计模型桶散列。思考与习题1顺序文件的优缺点2直接文件的优点3VSAM的总体结构4假设在一个按桶散列的文件组织中，若有B个桶，现在要对文件进行重组成2B个桶，试用算

2、法描述这种重组。5倒排文件的结构特点与优点第一节文件概述本节主要介绍文件的逻辑结构、物理结构以及文件操作。1、与文件有关的四个术语（域、纪录、文件、数据库）（1）域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数据对象的属性，不可分割的域含有一个简单的值，如姓名、日期等。域的特征可由长度和数据类型表示。域的长度可以是固定的，也可以是可变的。可变长度的域包含两个或三个子域：要保存的实际值和域名，在某些情况下还需要域的长度。（2）记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。例如，一个职员记录可以包括姓名、社会保险号、工作类型、参加工作时间等。根据设计

3、的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变的，则该记录就是可变长度的记录。（3）文件（File）是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。文件有一个惟一的名字，可以被创建或删除。（4）数据库（Database）是一组相关的数据，它的本质特征是数据单元间存在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种或多种不同类型的文件组成。2、构建文件物理结构的方法文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系。有两类方法可用来构造文件的物理结构。第一类称为计算法，其实现原理是设计映射算法，例如线性计算法、杂凑法等，通过对记录

4、关键字的计算转换成对应的物理块地址，从而找到所需记录。直接寻址文件、计算寻址文件，顺序文件均属此类。计算法的存取效率较高，又不必增加存储空间存放附加控制信息，能把分布范围较广的关键字均匀地映射到一个存储区域中。第二类称为指针法，这类方法设置专门指针，指明相应记录的物理地址或表达各记录之间的关联。索引文件、索引顺序文件、倒排文件等均属此类。使用指针的优点是可将文件信息的逻辑次序与在存储介质上的物理排列次序完全分开，便于随机存取，便于更新，能加快存取速度。但使用指针要耗用较多存储空间，大型文件的索引查找要耗费较多处理器时间，所以，究竟采用哪种文件存储结构，必须根据应用目标、响应时间和存储空间等多种

5、因素进行权衡。3、文件的相关操作对文件的操作主要有记录的检索、插入、删除、更新和文件排序。1记录的检索检索文件的某条记录或若干条记录。记录的检索方式有三种：（1）检索下一条记录：检索当前记录的下一条记录。（2）检索第i条记录：按照所给文件记录的逻辑顺序号检索记录。（3）按关键字检索：给定一个值，查询一个或一批关键字与给定值相关的记录。对于数据库文件可以有如下四种查询方式：（a）简单检索：查询关键字等于给定值的记录。例如检索学号为200507001的学生记录。（b）区域检索：查询关键字值在某个区域内的记录。例如检索某个年级数据结构考试成绩在8090分的学生记录。（c）函数检索：给定关键字的某个函

6、数，检索符合条件得记录。例如查询总分在全体学生的平均分以上的记录。（d）布尔检索：以上三种检索式用布尔运算符组合起来的检索。例如，查询总分在600分以上且数学在100分以上，或者总分在平均分以下的外语在98分以上的全部记录。2记录的插入在文件的指定位置插入一个新记录。文件位置的指定由记录的检索功能完成，记录的插入实际是在记录检索功能的基础上增加插入一条新记录的功能。3记录的删除把指定位置上的记录删除。这通常有以下两种情况：（1）删除文件的第i条记录。这实际是在记录检索功能的基础上增加删除一条记录的功能。（2）删除文件中符合给定条件的记录。这实际上是在按关键字检索功能的基础上增加删除对应记录的功

7、能。4记录的更新修改指定位置上的记录。通常有如下两种情况：（1）更新文件中第i条记录的某些数据项值。即在检索第i个记录功能的基础上增加更新该记录的某些数据项的功能。（2）更新文件中符合给定条件的记录的某些数据项。这实际上是在按关键字检索功能的基础上增加更新对应记录某些数据项的功能。5文件排序根据给定的关键字，对文件中的记录按关键字值升序或降序重新进行组织。第二节顺序文件顺序文件是在批处理文件、系统文件中用得最多的文件组织方式。本节介绍顺序文件的特点和操作。1、顺序文件的优缺点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。其特点是：（1）若存取文件中第i个记录，必须先搜索在它

8、之前的i-1个记录。（2）插入新的记录时只能追加在文件的末尾。（3）若要更新文件中的某个记录，则必须将整个文件进行复制。顺序文件的基本优点是：顺序存取记录时速度较快。所以，批处理文件、系统文件用得最多。采用磁带存放顺序文件时，总可以保持快速存取的优点。若以磁盘作存储介质时，顺序文件的记录也按物理邻接次序排列，因而顺序的磁盘文件能像磁带文件一样进行严格的顺序处理。然而，由于多程序访问，在同一时间另外的用户作业可能驱动磁头移向其它文件，因而可能要花费较多的处理器时间降低了这一优越性。顺序文件的主要缺点是：建立文件前需要能预先确定文件长度，以便分配存储空间；修改、插入和增生文件记录有困难；对直接存储

9、器作连续分配，会造成少量空闲块的浪费。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，则下一步查找范围的上

10、界为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时，

11、执行low=i+1;lKLi时，执行high=i-1;(3)查找失败，算法结束。按块插值查找是一种比较高速的查找方法。第三节直接文件(散列文件)在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件（散列文件）。本节介绍典型的直接文件的设计模型桶（Bucket）散列法。1、桶散列方法的基本思想桶散列方法的基本思想是把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。散列函数H把关键字key值转换成存储桶号，即H(key)表示具有关键字key的记

12、录所在的存储桶号。如果一个桶溢出，即它容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更多的记录。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的记录

13、。我们首先计算H（key），得到存储桶号i，然后查看存储桶目录表以找到第i号存储桶的第一个物理块地址，把该物理块调入内存，然后顺序搜索其中的每一个记录，检查有无关键字值等于key的记录，若找到就结束查找，否则根据该物理块上的链表指针找出下一个物理块并调入内存，以同样方式查找。以此类推直到找到关键字值等于key的记录或断定不存在关键字值等于key的记录（即桶中所有物理块全部查找完毕）为止。2插入插入前先根据上述查找过程查找桶号为H（key）的存储桶中是否存在关键字值等于key的记录。如果存在，则表示出错，因为插入一个与文件中已有记录具有相同关键字值的记录是没有意义的。若不存在相应的记录，则将该记

14、录存放到该存储桶的空闲物理块中。如果存储桶中所有的物理块都没有空间，我们就增加一个新的溢出块到该存储桶的链表上，并将新记录存入其中。3删除首先根据查找过程在桶号为H（key）的存储桶中寻找是否存在关键字值等于key的记录，若不存在，则表示出错。若找到，则将该记录的删除标志置为1，表示该记录已被删除。如果我们可以将记录在物理块中移动，那么删除记录后，我们可选择合并同一链表上的物理块，但合并一条链上的物理块随时都要冒风险，因为当我们往一个存储桶里交替地插入或删除记录时，可能每一步都会导致物理块的创建或删除。4修改假定我们要修改关键字值为key的记录的一个或多个域，若需要修改的域中涉及到关键字，则这

15、样的修改相当于删除加插入。因为散列文件中，关键字值的变化可能改变记录的存储位置，修改后的记录可能与原记录位于不同的存储桶中，因而需要先删除原记录，再插入新修改的记录。如果修改的域没有涉及到关键字，则首先查找到这个记录，找到后调入内存进行修改，修改后再写回存储桶（外存）中，若找不到，则出错。3、可扩展散列文件的组织方式可扩展散列文件的组织方式是：散列函数H把关键字key转换成一个定长的二进制位串k（伪关键字）,取k前i位二进制数（设为k）作为存储桶目录表中的目录项号，即表示目录表中第k个目录项，目录项中的指针指向的物理块就是具有关键字key的记录所在的物理块；存储桶目录项的个数为2i。所选择散列

16、函数尽可能具有如下性质：它所产生的伪关键字中约有一半是第一个二进制位为0，约1/4是前两位为01，约1/8是前三位为010，等等，即尽可能使所产生的伪关键字分布均匀。图8-3是使用两位散列函数值的散列文件。在图中，每个物理块存放两个逻辑记录，每个物理块上的“小凸块”中的数字表明由散列函数得到的二进制位串中有多少位用于确定记录在该物理块中的成员资格。可扩展散列文件上插入操作开始时类似于静态散列文件,即先进行查找操作。为了插入关键字为K的记录，我们计算出H（K），取出这一二进制位串的前i位（设为k），并找到序号为k的存储桶目录项。根据此目录项的指针找到物理块B。如果该物理块中有空闲空间，我们就把新

17、记录存入，插入操作完成。如果B中没有空闲空间，那么根据数字i的不同有两种可能：1）如果ji（j的值可在每个物理块的“小凸块”中找到），那么不必对存储桶目录表做任何变化。按下面规则操作：（a）将物理块B分裂成两个存储块。（b）根据记录关键字的散列值的第j+1位，将B中的记录分配到这两个存储块中，该位为0的记录继续保留在B中，而该位为1的记录放入到新块中。（c）把j+1存储到两个存储块的“小凸块”中，以标明用于确定成员资格的二进制位数。（d）调整存储桶目录项中指针，使原来指向块B的指针项指向块B或新块，这由记录关键字的散列值的第j+1位决定。注意，分裂B可能解决不了问题，因为有可能块B中所有记录将

18、分配到由B分裂成的两个存储块的其中一块中。如果这样，我们需要对仍太满的块用下一个更大的j值重复上述操作。2）如果j=i，那么我们必须先将i加1，使存储桶目录项个数增加一倍，即2i+1。在新存储桶目录表中，序号为k0和k1（分别用0和1扩展k）的项都指向原k目录项指向的物理块。也就是说，这两个新目录项共享同一个物理块，而物理块本身没有变化。4、在可扩展散列文件上实现插入操作的方法【例8-2】在图8-3所示的可扩展散列文件中，首先插入关键字值为0000、0111的记录，然后再插入关键字值为1000的记录。当插入关键字为0000、0111的记录时，由于这两个记录都属于第一个物理块，于是该存储块溢出。

19、因为该存储块只用一位（即j=1）来确定成员资格，而i=2，所以我们不必调整存储桶目录表，只需分裂该存储块，让0000和0001留在该存储块，而将0111存放到新块中，存储桶01目录项指向该新块。插入后结果见图8-4（a）。插入关键字值为1000的记录，目录项10所指向的存储块溢出。由于它已经使用两位数来确定其成员资格，这时需要再次分裂存储桶目录表，并将i设为3。第四节索引文件索引结构是实现非连续存储的另一种方法，适用于数据记录保存在随机存取存储设备上的文件。本节主要介绍索引文件的结构组成。1、索引文件的结构索引结构是链式结构的一种扩展，除了具备链式结构的优点外，还克服了它只能作顺序存取的缺点，

20、具有直接读写任意一个记录的能力，便于文件记录的插入、删除、修改。在索引文件上插入一个记录时，将记录置于数据区的末尾，同时在索引表中插入相应的索引项即可；删除一个记录时，仅删除该记录在索引表中的索引项即可；更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。索引文件的缺点是：增加了索引表的空间开销和查找时间，索引表的信息量甚至可能远远超过文件记录本身的信息量。2、稀疏索引和稠密索引索引文件中的索引项可以分为两类：一类称稠密索引，即对每个数据记录，在索引表里都有一个索引项，因而索引本身很大，但可以不要求数据记录排序，通过对索引的依次查找就可确定记录的位置或记录是否存在；另一种

21、称稀疏索引，它对每一组数据记录有一索引项，因而索引表本身较小，但数据记录必须按某种次序排列。注意，虽然稀疏索引本身较小，但是，在查找时又要花出一定代价。因为找到索引之后，只判定了记录所在的组，而该记录是否存在？是组内哪一个记录？还要进一步查找。第五节索引顺序文件索引顺序文件是顺序文件的扩展，其中各记录本身在介质上也是顺序排列的，它包含了直接处理和修改记录的能力。根据在系统运行时索引结构是否变化，又分为静态索引结构和动态索引结构，这正是本节所要介绍的内容。1、ISAM多级索引结构ISAM采用多级索引：主索引、柱面索引、磁道索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放

22、在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。例如图8-6为存放在一个磁盘组上的ISAM文件，每个柱面建立一个磁道索引。每个磁道索引项由两部分组成：基本索引项和溢出索引项，如图8-7所示，每一部分都包括关键字和指针两项，前者表示该磁道中最末一个记录的关键字（在此为最大关键字），后者指示该磁道中第一个记录的位置。柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引主索引。2、VSAM的总体结构虚拟存储方法VSAM（VirtualS

23、equentialAccessMethod）是B+树应用的一个典型例子，是一种索引顺序文件的组织方式。这种存取方法利用了操作系统中的虚拟存储器的功能，给用户提供方便。这种存取方法与存储设备无关，与柱面、磁道等物理存储单位没有必然联系，因为对用户而言，文件只有控制域和控制区间等逻辑存储单位。VSAM的总体结构如图8-9所示。它由三部分组成：索引集、顺序集和数据集。文件的记录均存放在数据集中，顺序集也是文件索引的一部分，顺序集和索引集一起形成一棵B+树结构的文件索引。可以利用索引对VSAM进行随机存取，利用顺序集对文件进行顺序存取。3、在VSAM上插入与删除操作的实现方法在VSAM文件插入记录时，首先调用B+树的查找算法，确定该记录应插入的顺序集结点，进而确定该记录应插入的控制区间及相应位置。如果该控制区间中自由空间足以容纳该记录，则将要插入位置右面的记录右移腾出空间插入该记录，并在相应位置建立控制信息。例如，在图8-12的VSAM文件中插入ARS、BIT，结果如图8-13（a）所示。如果自由空间不够，则检查该控制区间所在的控制域中是否还有空闲的控制区间，若有，则将