山东大学《数据结构》讲义08文件.docx

第八章文件内容概述在实际的应用中，特别是涉及事务管理类型的问题，比方企业的管理信息系统、 大型的信息检索系统、数字图书馆等问题中将涉及大量数据，由于内存不适合存 储这类数据量大且需长期保存的数据，因此这类数据需要存储在外存储器上。习 惯上称存储在内存中的数据集合为表，称存储在外存储器（二级存储器）中的数 据集合为文件。本章讨论文件的相关概念、表示方法及各种运算的实现方法。重点与难点,点为加序文件的操作和索引顺序文件的结构。难点是散列文件的设计模型一桶散列。思考与习题.顺序文件的优缺点1 .直接文件的优点. VSAM的总体结构2 .假设在一个按桶散列的文件组织中，假设有B个桶，现在要对文件进行重组成 2B个桶，试用算法描述这种重组。3 .倒排文件的结构特点与优点第一节文件概述本节主要介绍文件的逻辑结构、物理结构以及文件操作。1、与文件有关的四个术语（域、纪录、文件、数据库）（1）域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数 据对象的属性，不可分割的域含有一个简单的值，如姓名、日期等。域的特征可 由长度和数据类型表示。域的长度可以是固定的，也可以是可变的。可变长度的 域包含两个或三个子域:要保存的实际值和域名，在某些情况下还需要域的长度。（2）记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。 例如，一个职员记录可以包括姓名、社会保险号、工作类型、参加工作时间等。 根据设计的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变 的，那么该记录就是可变长度的记录。（3）文件（File）是由大量性质相同的记录组成的集合，它被应用程序看作是一 个实体。文件有一个惟一的名字，可以被创立或删除。（4）数据库（Database）是一组相关的数据，它的本质特征是数据单元间存 在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种 或多种不同类型的文件组成。2、构建文件物理结构的方法文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系。有两类方法可用来构造文件的物理结构。第一类称为计算法，其实现原理是设计 映射算法，例如线性计算法、杂凑法等，通过对记录关键字的计算转换成对应的 物理块地址，从而找到所需记录。直接寻址文件、计算寻址文件，顺序文件均属 此类。计算法的存取效率较高，又不必增加存储空间存放附加控制信息，能把分 布范围较广的关键字均匀地映射到一个存储区域中。第二类称为指针法，这类方 法设置专门指针，指明相应记录的物理地址或表达各记录之间的关联。索引文件、 索引顺序文件、倒排文件等均属此类。使用指针的优点是可将文件信息的逻辑次 序与在存储介质上的物理排列次序完全分开，便于随机存取，便于更新，能加快 存取速度。但使用指针要耗用较多存储空间，大型文件的索引查找要耗费较多处 理器时间，所以，究竟采用哪种文件存储结构，必须根据应用目标、响应时间和 存储空间等多种因素进行权衡。3、文件的相关操作对文件的操作主要有记录的检索、插入、删除、更新和文件排序。1记录的检索检索文件的某条记录或假设干条记录。记录的检索方式有三种：(1)检索下一条记录：检索当前记录的下一条记录。(2)检索第i条记录：按照所给文件记录的逻辑顺序号检索记录。(3)按关键字检索：给定一个值，查询一个或一批关键字与给定值相关的记录。对于数据库文件可以有如下四种查询方式：(a)简单检索：查询关键字等于给定值的记录。例如检索学号为200507001的 学生记录。(b)区域检索：查询关键字值在某个区域内的记录。例如检索某个年级数据结 构考试成绩在80-90分的学生记录。(O函数检索：给定关键字的某个函数，检索符合条件得记录。例如查询总分 在全体学生的平均分以上的记录。(d)布尔检索：以上三种检索式用布尔运算符组合起来的检索。例如，查询总 分在600分以上且数学在100分以上，或者总分在平均分以下的外语在98分以 上的全部记录。2记录的插入在文件的指定位置插入一个新记录。文件位置的指定由记录的检索功能完成，记 录的插入实际是在记录检索功能的基础上增加插入一条新记录的功能。3记录的删除 把指定位置上的记录删除。这通常有以下两种情况：（1）删除文件的第i条记录。这实际是在记录检索功能的基础上增加删除一条 记录的功能。（2）删除文件中符合给定条件的记录。这实际上是在按关键字检索功能的基础 上增加删除对应记录的功能。4记录的更新修改指定位置上的记录。通常有如下两种情况：（1）更新文件中第i条记录的某些数据项值。即在检索第i个记录功能的基础上 增加更新该记录的某些数据项的功能。（2）更新文件中符合给定条件的记录的某些数据项。这实际上是在按关键字检 索功能的基础上增加更新对应记录某些数据项的功能。5文件排序根据给定的关键字，对文件中的记录按关键字值升序或降序重新进行组织。第二节顺序文件顺序文件是在批处理文件、系统文件中用得最多的文件组织方式。本节介绍顺序 文件的特点和操作。1、顺序文件的优缺点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。其特 点是：（1）假设存取文件中第i个记录，必须先搜索在它之前的il个记录。（2）插入新的记录时只能追加在文件的末尾。（3）假设要更新文件中的某个记录，那么必须将整个文件进行复制。顺序文件的基本优点是：顺序存取记录时速度较快。所以，批处理文件、系统文 件用得最多。采用磁带存放顺序文件时，总可以保持快速存取的优点。假设以磁盘 作存储介质时，顺序文件的记录也按物理邻接次序排列，因而顺序的磁盘文件能 像磁带文件一样进行严格的顺序处理。然而，由于多程序访问，在同一时间另外 的用户作业可能驱动磁头移向其它文件，因而可能要花费较多的处理器时间降低 了这一优越性。顺序文件的主要缺点是：建立文件前需要能预先确定文件长度，以便分配存储空 间；修改、插入和增生文件记录有困难；对直接存储器作连续分配，会造成少量 空闲块的浪费。2、分块插值查找的算法假设文件由记录RI, R2, Rn组成，并记录按关键字升序排列：KlK2.KN, h、I分别表示当前查找范围的上界和下界。现 在我们要查找关键字值为K的记录。我们回顾一下折半查找的具体做法，首先选 取查找范围内的中间点i二,然后将Ki与K进行比拟。插值法查找并不是选取查 找范围的中间点作为比拟点，而是按关键字的比例选取I和h之间的某一点 i i=这表示i的选取与查找范围的下界关键字、上界关键字和要查找的关键字有关。 然后将Ki与K比拟，假设K=Ki,那么Ri就是要找的记录；假设KVKi,那么下一步查找 范围的上界为i-1,下界为I；假设KKi,那么下一步查找范围的上界为h,下界为 i+lo由于文件记录存放在外存的物理块上，因此文件的查找采用分块插值查找，此时, h、I、i表示物理块号。假设整个文件的最小关键字为K0,最大关键字为Km, 要查找的关键字为K,整个文件分为N个物理块，并设：low:查找范围内的最小物理块号；high:查找范围内的最大物理块号；Li：第i个物理块内的记录的最小关键字；Hi：第i个物理块内的记录的最大关键字分块插值查找的算法描述如下：(1)初始化 low=l； high=No(2)反复执行下面操作，直到highvlow成立(b)读取第i个物理块，获得Li和Hi(c)分下面三种情况执行LiWKWHi时，查找成功，第i个物理块即为所求;IKHi 时，执行 low=i+l;IKVLi 时，执行 high=i-l;(3)查找失败，算法结束。按块插值查找是一种比拟高速的查找方法。第三节直接文件(散列文件)在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应 关系，利用这种关系实现存取的文件叫直接文件(散列文件)。本节介绍典型的 直接文件的设计模型桶(Bucket)散列法。工、桶散列方法的基本思想桶散列方法的基本思想是把文件的记录通过散列函数H分别存储在许多存储桶 中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成 链表，每个物理块存放假设干记录。散列函数H把关键字key值转换成存储桶号， 即H(key)表示具有关键字key的记录所在的存储桶号。如果一个桶溢出，即它 容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更 多的记录。2、桶散列结构上是操作(查找、插入、删除)的实现思想【例81】图8-2表示一个具有B个桶的散列文件。为了使图例易于处理，假设 每个物理块只存放一个逻辑记录，且B=4,即散列函数的返回值介于03之间。 假设记录的关键字为字母af,并且假定h(d)=O, h(c)=h(e)=l, h(b)=2, h(f)=h(a)=3o因此，这六个记录的分布如图82所示。在散列文件上可以进行查找、插入、删除、修改等操作，下面讨论这些操作的主 要思路。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的记录所在的物理块；存储桶目录项的个数为2L所选择散列 函数尽可能具有如下性质：它所产生的伪关键字中约有一半是第一个二进制位为 0,约1/4是前两位为01,约1/8是前三位为010,等等，即尽可能使所产生 的伪关键字分布均匀。图8-3是使用两位散列函数值的散列文件。在图中，每个物理块存放两个逻辑记 录，每个物理块上的小凸块中的数字说明由散列函数得到的二进制位串中有多 少位用于确定记录在该物理块中的成员资格。可扩展散列文件上插入操作开始时类似于静态散列文件，即先进行查找操作。为 了插入关键字为K的记录，我们计算出H （K）,取出这一二进制位串的前i位 （设为k ）,并找到序号为k的存储桶目录项。根据此目录项的指针找到物 理块B。如果该物理块中有空闲空间，我们就把新记录存入，插入操作完成。如 果B中没有空闲空间，那么根据数字i的不同有两种可能：1)如果jvi (j的值可在每个物理块的小凸块中找到)，那么不必对存储桶目 录表做任何变化。按下面规那么操作：(a)将物理块B分裂成两个存储块。(b)根据记录关键字的散列值的第j+1位，将B中的记录分配到这两个存储块 中，该位为0的记录继续保存在B中，而该位为1的记录放入到新块中。(O把j+1存储到两个存储块的小凸块中，以标明用于确定成员资格的二进 制位数。(d)调整存储桶目录项中指针，使原来指向块B的指针项指向块B或新块，这 由记录关键字的散列值的第j+1位决定。注意，分裂B可能解决不了问题，因为有可能块B中所有记录将分配到由B分 裂成的两个存储块的其中一块中。如果这样，我们需要对仍太满的块用下一个更 大的j值重复上述操作。2)如果j=i,那么我们必须先将i力口 1,使存储桶目录项个数增加一倍， 即2i+l。在新存储桶目录表中，序号为k。和k 1 (分别用。和1扩展k ) 的项都指向原k目录项指向的物理块。也就是说，这两个新目录项共享同一个 物理块，而物理块本身没有变化。4、在可扩展散列文件上实现插入操作的方法【例8-2】在图8-3所示的可扩展散列文件中，首先插入关键字值为0000、0111 的记录，然后再插入关键字值为1000的记录。当插入关键字为0000、0111的记录时，由于这两个记录都属于第一个物理块, 于是该存储块溢出。因为该存储块只用一位(即j=l)来确定成员资格，而i=2, 所以我们不必调整存储桶目录表,只需分裂该存储块,让0000和0001留在该 存储块，而将0111存放到新块中，存储桶01目录项指向该新块。插入后结果 见图 8-4 (a) o插入关键字值为1000的记录，目录项10所指向的存储块溢出。由于它已经使 用两位数来确定其成员资格，这时需要再次分裂存储桶目录表，并将i设为3。第四节索引文件索引结构是实现非连续存储的另一种方法，适用于数据记录保存在随机存取存储 设备上的文件。本节主要介绍索引文件的结构组成。工、索引文件的结构索引结构是链式结构的一种扩展，除了具备链式结构的优点外，还克服了它 只能作顺序存取的缺点，具有直接读写任意一个记录的能力，便于文件记录的插 入、删除、修改。在索引文件上插入一个记录时，将记录置于数据区的末尾，同 时在索引表中插入相应的索引项即可；删除一个记录时，仅删除该记录在索引表 中的索引项即可；更新记录时，应将更新后的记录置于数据区末尾，同时修改索 引表中相应的索引项。索引文件的缺点是：增加了索引表的空间开销和查找时间, 索引表的信息量甚至可能远远超过文件记录本身的信息量。2、稀疏索引和稠密索引索引文件中的索引项可以分为两类：类称稠密索引，即对每个数据记录，在索 引表里都有一个索引项，因而索引本身很大，但可以不要求数据记录排序，通过 对索引的依次查找就可确定记录的位置或记录是否存在；另一种称稀疏索引，它 对每一组数据记录有一索引项，因而索引表本身较小，但数据记录必须按某种次 序排列。注意，虽然稀疏索引本身较小，但是，在查找时又要花出一定代价。因 为找到索引之后，只判定了记录所在的组，而该记录是否存在？是组内哪一个记 录？还要进一步查找。第五节索引顺序文件索引顺序文件是顺序文件的扩展，其中各记录本身在介质上也是顺序排列的，它 包含了直接处理和修改记录的能力。根据在系统运行时索引结构是否变化，又分 为静态索引结构和动态索引结构，这正是本节所要介绍的内容。1、ISAM多级索引结构ISAM采用多级索引：主索引、柱面索引、磁道索引。文件的记录在同一盘组上 存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱 面，那么应按盘面的次序顺序存放。例如图8-6为存放在一个磁盘组上的ISAM文 件，每个柱面建立一个磁道索引。每个磁道索引项由两局部组成：基本索引项和 溢出索引项，如图87所示，每一局部都包括关键字和指针两项，前者表示该磁 道中最末一个记录的关键字（在此为最大关键字），后者指示该磁道中第一个记 录的位置。柱面索引的每一个索引项也由关键字和指针两局部组成，前者表示该 柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位 置。柱面索引存放在某个柱面上，假设柱面索引较大，占多个磁道时，那么可建立柱 面索引的索引主索引。2、VSAM的总体结构虚拟存储方法VSAM （VirtualSequentialAccessMethod）是B+树应用的一个典型 例子，是一种索引顺序文件的组织方式。这种存取方法利用了操作系统中的虚拟 存储器的功能，给用户提供方便。这种存取方法与存储设备无关，与柱面、磁道 等物理存储单位没有必然联系，因为对用户而言，文件只有控制域和控制区间等 逻辑存储单位。VSAM的总体结构如图8-9所示。它由三局部组成：索引集、顺序集和数据集。 文件的记录均存放在数据集中，顺序集也是文件索引的一局部，顺序集和索引集 一起形成一棵B+树结构的文件索引。可以利用索引对VSAM进行随机存取，利 用顺序集对文件进行顺序存取。3、在VSAM上插入与删除操作的实现方法在VSAM文件插入记录时，首先调用B+树的查找算法，确定该记录应插入的顺 序集结点，进而确定该记录应插入的控制区间及相应位置。如果该控制区间中自 由空间足以容纳该记录，那么将要插入位置右面的记录右移腾出空间插入该记录, 并在相应位置建立控制信息。例如，在图8-12的VSAM文件中插入ARS、BIT, 结果如图8-13 (a)所示。如果自由空间不够，那么检查该控制区间所在的控制域 中是否还有空闲的控制区间，假设有，那么将控制区间分裂，将其中的近似半的记 录移动到一个空闲的控制区间中，例如，在图8-13 (a)上插入BEC,结果如图 8-13 (b)所示。如无，那么进行一次控制域的分裂。无论是控制域的分裂还是控 制区间的分裂，均需要在顺序集中插入索引项，并且这一插入有可能涉及高层的 索引，但这需要采用B+树的插入算法实现。在VSAM文件中删除记录时，需将同一控制区间中较删除记录关键字大的记录向 前移动，把空间留给以后插入的新记录。假设整个控制区间变空，那么需修改顺序集 中相应的索引项。由此可见，VSAM文件占有较多的存储空间，一般只能保持约乃的存储空间利 用率。但它的优点是：动态地分配和释放存储，不需要对文件进行重组，并能较 快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的 时间是相同的。第六节倒排文件倒排文件是适合非主关键字查找的文件组织形式。本节简单介绍倒排文件的结构 和优缺点。1、倒排文件的结构具有倒排表形式的索引文件称为倒排文件(ReverseFile)。之所以把这种文件组 织称为倒排，是因为在一般的文件组织中，记录中各个属性之间地位平等，而 在倒排文件组织中，将某个属性突出。倒排文件与索引文件的区别在于，索引 文件一般指主索引文件，在其索引项中除了主关键字之外只有一个指针，不会出 现许多指针。图814是倒排文件索引的例如，为了表达方便，在图中具有相同 次关键字的记录之间不用指针相链，而是用一组记录号。2、倒排文件的优缺点倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就 可得到解答。例如，如果查询信息管理专业有哪些同学选修数据结构课程， 那么只要将信息管理索引中的记录号和数据结构索引中的记录号进行求交集 运算即可。倒排文件的缺点是维护困难。在同一索引表中，不同的关键字其记录数不同，各 倒排表的长度不等，同一倒排表中各项长度也不等。