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

本节主要介绍文件的逻辑结构、物理结构以及文件操作。

1、与文件有关的四个术语（域、纪录、文件、数据库）

（1）域（Field）是数据的基本单位，又称为字段或数据项。域通常用于描述数据对象的属性，不可分割的域含有一个简单的值，如姓名、日期等。域的特征可由长度和数据类型表示。域的长度可以是固定的，也可以是可变的。可变长度的域包含两个或三个子域：要保存的实际值和域名，在某些情况下还需要域的长度。

（2）记录（Record）是一组相关域的集合，它可以看作是应用程序的一个单元。例如，一个职员记录可以包括姓名、社会保险号、工作类型、参加工作时间等。根据设计的不同，记录可以是固定长或可变长。如果记录中某些域的长度是可变的，则该记录就是可变长度的记录。

（3）文件（File）是由大量性质相同的记录组成的集合，它被应用程序看作是一个实体。文件有一个惟一的名字，可以被创建或删除。

    （4）数据库（Database）是一组相关的数据，它的本质特征是数据单元间存在明确的关系，并且设计成可供许多不同的应用程序使用。数据库自身是由一种或多种不同类型的文件组成。 

文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系。

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

对文件的操作主要有记录的检索、插入、删除、更新和文件排序。

检索文件的某条记录或若干条记录。记录的检索方式有三种：

（1）检索下一条记录：检索当前记录的下一条记录。

（2）检索第i条记录：按照所给文件记录的逻辑顺序号检索记录。

（3）按关键字检索：给定一个值，查询一个或一批关键字与给定值相关的记录。对于数据库文件可以有如下四种查询方式：

（a）简单检索：查询关键字等于给定值的记录。例如检索学号为的学生记录。

（b）区域检索：查询关键字值在某个区域内的记录。例如检索某个年级数据结构考试成绩在80~90分的学生记录。

（c）函数检索：给定关键字的某个函数，检索符合条件得记录。例如查询总分在全体学生的平均分以上的记录。

（d）布尔检索：以上三种检索式用布尔运算符组合起来的检索。例如，查询总分在600分以上且数学在100分以上，或者总分在平均分以下的外语在98分以上的全部记录。

在文件的指定位置插入一个新记录。文件位置的指定由记录的检索功能完成，记录的插入实际是在记录检索功能的基础上增加插入一条新记录的功能。

把指定位置上的记录删除。这通常有以下两种情况：

（1）删除文件的第i条记录。这实际是在记录检索功能的基础上增加删除一条记录的功能。

（2）删除文件中符合给定条件的记录。这实际上是在按关键字检索功能的基础上增加删除对应记录的功能。

修改指定位置上的记录。通常有如下两种情况：

（1）更新文件中第i条记录的某些数据项值。即在检索第i个记录功能的基础上增加更新该记录的某些数据项的功能。

（2）更新文件中符合给定条件的记录的某些数据项。这实际上是在按关键字检索功能的基础上增加更新对应记录某些数据项的功能。

根据给定的关键字，对文件中的记录按关键字值升序或降序重新进行组织。

顺序文件是在批处理文件、系统文件中用得最多的文件组织方式。本节介绍顺序文件的特点和操作。

顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。其特点是：

（1）若存取文件中第i个记录，必须先搜索在它之前的i-1个记录。

（2）插入新的记录时只能追加在文件的末尾。

（3）若要更新文件中的某个记录，则必须将整个文件进行复制。

顺序文件的基本优点是：顺序存取记录时速度较快。所以，批处理文件、系统文件用得最多。采用磁带存放顺序文件时，总可以保持快速存取的优点。若以磁盘作存储介质时，顺序文件的记录也按物理邻接次序排列，因而顺序的磁盘文件能像磁带文件一样进行严格的顺序处理。然而，由于多程序访问，在同一时间另外的用户作业可能驱动磁头移向其它文件，因而可能要花费较多的处理器时间降低了这一优越性。

顺序文件的主要缺点是：建立文件前需要能预先确定文件长度，以便分配存储空间；修改、插入和增生文件记录有困难；对直接存储器作连续分配，会造成少量空闲块的浪费。

假设文件由记录R1，R2，…，Rn组成，并已知记录按关键字升序排列：K1…，h、l分别表示当前查找范围的上界和下界。现在我们要查找关键字值为K的记录。我们回顾一下折半查找的具体做法，首先选取查找范围内的中间点i=

的选取与查找范围的下界关键字、上界关键字和要查找的关键字有关。然后将Ki与K比较，若K=Ki，则Ri就是要找的记录；若K＜Ki，则下一步查找范围的上界为i-1，下界为l ；若K＞Ki，则下一步查找范围的上界为h，下界为i+1。

由于文件记录存放在外存的物理块上，因此文件的查找采用分块插值查找，此时，h、l、i表示物理块号。假设整个文件的最小关键字为K0，最大关键字为Km，要查找的关键字为K，整个文件分为N个物理块，并设：

low:查找范围内的最小物理块号；

high: 查找范围内的最大物理块号；

Li：第i个物理块内的记录的最小关键字；

Hi：第i个物理块内的记录的最大关键字

分块插值查找的算法描述如下：

（2）反复执行下面操作，直到high＜low成立

第三节 直接文件(散列文件)

在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件（散列文件）。本节介绍典型的直接文件的设计模型——桶（Bucket）散列法。

桶散列方法的基本思想是把文件的记录通过散列函数H分别存储在许多存储桶中，每个存储桶包含一个或多个物理块，一个存储桶中的物理块用指针连接形成链表，每个物理块存放若干记录。散列函数H把关键字key值转换成存储桶号，即H(key)表示具有关键字key的记录所在的存储桶号。如果一个桶溢出，即它容纳不下所有属于它的记录，那么可以给该存储桶增加一个溢出块链表以存放更多的记录。

 2、桶散列结构上是操作（查找、插入、删除）的实现思想 

【例8-1】图8-2表示一个具有B个桶的散列文件。为了使图例易于处理，假设每个物理块只存放一个逻辑记录，且B=4，即散列函数的返回值介于0~3之间。假设记录的关键字为字母a~f，并且假定h(d)=0，h(c)=h(e)=1，h(b)=2，h(f)=h(a)=3。因此，这六个记录的分布如图8-2所示。

在散列文件上可以进行查找、插入、删除、修改等操作，下面讨论这些操作的主要思路。

假设要查找一个关键字值等于一个给定值key的记录。我们首先计算H（key），得到存储桶号i，然后查看存储桶目录表以找到第i号存储桶的第一个物理块地址，把该物理块调入内存，然后顺序搜索其中的每一个记录，检查有无关键字值等于key的记录，若找到就结束查找，否则根据该物理块上的链表指针找出下一个物理块并调入内存，以同样方式查找。以此类推直到找到关键字值等于key的记录或断定不存在关键字值等于key的记录（即桶中所有物理块全部查找完毕）为止。

插入前先根据上述查找过程查找桶号为H（key）的存储桶中是否存在关键字值等于key的记录。如果存在，则表示出错，因为插入一个与文件中已有记录具有相同关键字值的记录是没有意义的。若不存在相应的记录，则将该记录存放到该存储桶的空闲物理块中。如果存储桶中所有的物理块都没有空间，我们就增加一个新的溢出块到该存储桶的链表上，并将新记录存入其中。

首先根据查找过程在桶号为H（key）的存储桶中寻找是否存在关键字值等于key的记录，若不存在，则表示出错。若找到，则将该记录的删除标志置为1，表示该记录已被删除。如果我们可以将记录在物理块中移动，那么删除记录后，我们可选择合并同一链表上的物理块，但合并一条链上的物理块随时都要冒风险，因为当我们往一个存储桶里交替地插入或删除记录时，可能每一步都会导致物理块的创建或删除。

假定我们要修改关键字值为key的记录的一个或多个域，若需要修改的域中涉及到关键字，则这样的修改相当于删除加插入。因为散列文件中，关键字值的变化可能改变记录的存储位置，修改后的记录可能与原记录位于不同的存储桶中，因而需要先删除原记录，再插入新修改的记录。如果修改的域没有涉及到关键字，则首先查找到这个记录，找到后调入内存进行修改，修改后再写回存储桶（外存）中，若找不到，则出错。

可扩展散列文件的组织方式是：散列函数H把关键字key转换成一个定长的二进制位串k′（伪关键字）,取k′前i位二进制数（设为k〞）作为存储桶目录表中的目录项号，即表示目录表中第k〞个目录项，目录项中的指针指向的物理块就是具有关键字key的记录所在的物理块；存储桶目录项的个数为2i。所选择散列函数尽可能具有如下性质：它所产生的伪关键字中约有一半是第一个二进制位为0，约1/4是前两位为01，约1/8是前三位为010，…等等，即尽可能使所产生的伪关键字分布均匀。

图8-3是使用两位散列函数值的散列文件。在图中，每个物理块存放两个逻辑记录，每个物理块上的“小凸块”中的数字表明由散列函数得到的二进制位串中有多少位用于确定记录在该物理块中的成员资格。

可扩展散列文件上插入操作开始时类似于静态散列文件,即先进行查找操作。为了插入关键字为K的记录，我们计算出H（K），取出这一二进制位串的前i位（设为k〞），并找到序号为k〞的存储桶目录项。根据此目录项的指针找到物理块B。如果该物理块中有空闲空间，我们就把新记录存入，插入操作完成。如果B中没有空闲空间，那么根据数字i的不同有两种可能：

1）如果j＜i（j的值可在每个物理块的“小凸块”中找到），那么不必对存储桶目录表做任何变化。按下面规则操作：

（a）将物理块B分裂成两个存储块。

（b）根据记录关键字的散列值的第j+1位，将B中的记录分配到这两个存储块中，该位为0的记录继续保留在B中，而该位为1的记录放入到新块中。

（c）把j+1存储到两个存储块的“小凸块”中，以标明用于确定成员资格的二进制位数。

（d）调整存储桶目录项中指针，使原来指向块B的指针项指向块B或新块，这由记录关键字的散列值的第j+1位决定。

注意，分裂B可能解决不了问题，因为有可能块B中所有记录将分配到由B分裂成的两个存储块的其中一块中。如果这样，我们需要对仍太满的块用下一个更大的j值重复上述操作。

2）如果j=i，那么我们必须先将i加1，使存储桶目录项个数增加一倍，即2i+1。在新存储桶目录表中，序号为k〞0和k〞1（分别用0和1扩展k〞）的项都指向原k〞目录项指向的物理块。也就是说，这两个新目录项共享同一个物理块，而物理块本身没有变化。

 4、在可扩展散列文件上实现插入操作的方法 

【例8-2】在图8-3所示的可扩展散列文件中，首先插入关键字值为0000、0111的记录，然后再插入关键字值为1000的记录。

当插入关键字为0000、0111的记录时，由于这两个记录都属于第一个物理块，于是该存储块溢出。因为该存储块只用一位（即j=1）来确定成员资格，而i=2，所以我们不必调整存储桶目录表，只需分裂该存储块，让0000和0001留在该存储块，而将0111存放到新块中，存储桶01目录项指向该新块。插入后结果见图8-4（a）。

插入关键字值为1000的记录，目录项10所指向的存储块溢出。由于它已经使用两位数来确定其成员资格，这时需要再次分裂存储桶目录表，并将i设为3。

索引结构是实现非连续存储的另一种方法，适用于数据记录保存在随机存取存储设备上的文件。本节主要介绍索引文件的结构组成。

索引结构是链式结构的一种扩展，除了具备链式结构的优点外，还克服了它只能作顺序存取的缺点，具有直接读写任意一个记录的能力，便于文件记录的插入、删除、修改。在索引文件上插入一个记录时，将记录置于数据区的末尾，同时在索引表中插入相应的索引项即可；删除一个记录时，仅删除该记录在索引表中的索引项即可；更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。索引文件的缺点是：增加了索引表的空间开销和查找时间，索引表的信息量甚至可能远远超过文件记录本身的信息量。

索引文件中的索引项可以分为两类：一类称稠密索引，即对每个数据记录，在索引表里都有一个索引项，因而索引本身很大，但可以不要求数据记录排序，通过对索引的依次查找就可确定记录的位置或记录是否存在；另一种称稀疏索引，它对每一组数据记录有一索引项，因而索引表本身较小，但数据记录必须按某种次序排列。注意，虽然稀疏索引本身较小，但是，在查找时又要花出一定代价。因为找到索引之后，只判定了记录所在的组，而该记录是否存在？是组内哪一个记录？还要进一步查找。

索引顺序文件是顺序文件的扩展，其中各记录本身在介质上也是顺序排列的，它包含了直接处理和修改记录的能力。根据在系统运行时索引结构是否变化，又分为静态索引结构和动态索引结构，这正是本节所要介绍的内容。

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

Method）是B+树应用的一个典型例子，是一种索引顺序文件的组织方式。这种存取方法利用了操作系统中的虚拟存储器的功能，给用户提供方便。这种存取方法与存储设备无关，与柱面、磁道等物理存储单位没有必然联系，因为对用户而言，文件只有控制域和控制区间等逻辑存储单位。

VSAM的总体结构如图8-9所示。它由三部分组成：索引集、顺序集和数据集。文件的记录均存放在数据集中，顺序集也是文件索引的一部分，顺序集和索引集一起形成一棵B+树结构的文件索引。可以利用索引对VSAM进行随机存取，利用顺序集对文件进行顺序存取。

在VSAM文件插入记录时，首先调用B+树的查找算法，确定该记录应插入的顺序集结点，进而确定该记录应插入的控制区间及相应位置。如果该控制区间中自由空间足以容纳该记录，则将要插入位置右面的记录右移腾出空间插入该记录，并在相应位置建立控制信息。例如，在图8-12的VSAM文件中插入ARS、BIT，结果如图8-13（a）所示。如果自由空间不够，则检查该控制区间所在的控制域中是否还有空闲的控制区间，若有，则将控制区间分裂，将其中的近似一半的记录移动到一个空闲的控制区间中，例如，在图8-13（a）上插入BEC，结果如图8-13（b）所示。如无，则进行一次控制域的分裂。无论是控制域的分裂还是控制区间的分裂，均需要在顺序集中插入索引项，并且这一插入有可能波及高层的索引，但这需要采用B+树的插入算法实现。

在VSAM文件中删除记录时，需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。若整个控制区间变空，则需修改顺序集中相应的索引项。

由此可见，VSAM文件占有较多的存储空间，一般只能保持约75％的存储空间利用率。但它的优点是：动态地分配和释放存储，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同的。

倒排文件是适合非主关键字查找的文件组织形式。本节简单介绍倒排文件的结构和优缺点。

具有倒排表形式的索引文件称为倒排文件（Reverse File）。之所以把这种文件组织称为“倒排”，是因为在一般的文件组织中，记录中各个属性之间地位平等，而在倒排文件组织中，将某个属性“突出”。倒排文件与索引文件的区别在于，索引文件一般指主索引文件，在其索引项中除了主关键字之外只有一个指针，不会出现许多指针。图8-14是倒排文件索引的示例，为了表达方便，在图中具有相同次关键字的记录之间不用指针相链，而是用一组记录号。

倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。例如，如果查询“信息管理”专业有哪些同学选修“数据结构”课程，则只要将“信息管理”索引中的记录号和“数据结构”索引中的记录号进行求“交”集运算即可。

倒排文件的缺点是维护困难。在同一索引表中，不同的关键字其记录数不同，各倒排表的长度不等，同一倒排表中各项长度也不等。

在为文件分配外存空间时所要考虑的主要问题是:怎样才能有效地利用外存空间和如何提高对文件的访问速度。
目前常用的外存分配方法有:连续分配、链接分配和索引分配。通常，在一个系统中，仅采用其中的一种方法来为文件

连续分配要求为每一一个文件分配组相邻接的盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构
，此时的物理文件称为顺序文件。

在采用链接分配方式时，可通过在每个盘块上的链接指针,将同属于一一个文件的多个离散的盘块链接成一一个链表，把这样形成的物理文件称为链接文件。
在采用隐式链接分配方式时， 在文件目录的每个目录项中，都须含有指向链接文件第一一个 盘块和最后一一个盘块的指针,它适合于顺序访问，对随机访问是极其低效的。
这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中，该表在整个磁盘仅设置一张。
由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT.

FAT32是FAT系列文件系统的最后-一个产品，FAT32的不足之处:如不支持4GB以上的大文件.
NTFS:使用了64位磁盘地址，理论上可以支持2的64次方字节的磁盘分区;可以很好地支持长文件名;具有系统容错功能;提供了数据的一致性;提供了文件加密、文件压缩功能.....

在打开某个文件时，只需把该文件所对应的盘块号集中地放在一起。索引分配方法为每个文件分配一
个索引块(表)，再把分配给该文件的所有盘块号，都记录在该索引块中，因而该索引块就是一一个含有许
索引分配方式支持直接访问，当要读文件的第I个盘块时，可以方便地直接从索引块中找到第I个盘块的盘块号;
此外，索引分配方式也不会产生外部碎片，当文件较大时，索引分配方式优于链接分配方式。

索引分配方式的主要问题:可能要花费较多的外存空间。通常情况下，总是中、小型文件居多，如只需1~2
个盘块，这时如果采用链接分配，只需设置1~2个指针，如采用索引分配，则同样仍需为之分配一索引块。
通常采用一个专门的盘块作为索引块，对于小文件采用索引分配方式时，其索引块的利用率将是极低的。

7.6文件存储空间的管理

文件管理要解决的重要问题之一是如何为新创建的文件分配存储空间。存储空间的基本分配单位都是.
磁盘块而非字节。系统应为分配存储空间而设置相应的数据结构系统应提供对存储空间进行分配和回收的手段.

（1）首次适应算法（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给
作业，这种方法的目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到
高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
（2）最佳适应算法（Best Fit)：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使
碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一
个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。
（3）最差适应算法（Worst Fit)：从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。
为适应此算法，空闲分区表（空闲区链）中的空闲分区按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。

7.6.1空闲表法和空闲链表法

属于连续分配，为外存上的所有空闲区建立一张空闲表，
每个空闲区对应于一个空闲表项......再将所有空闲区按其
起始盘块号递增的次序排列。

(2)存储空间的分配与回收。
空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项直至找到第-一个其大小能满足要求的空闲区，再将
该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和
后区相邻接，对相邻接者应予以合并。

将所有空闲盘区拉成一条空闲链
(1)空闲盘块链:将磁盘上的所有空闲空间，

(2)空闲盘区链:将磁盘上的所有空闲盘区(每个
盘区可包含若干个盘块)拉成一条链。

位示图是利用二进制的一位来表示磁盘中- 一个盘块
的使用情况.当其值为”0”时，表示对应的盘块空闲;
为”1”时,表示已分配。
个二进制位与之对应。这样，由所有盘块所对应的
位构成一个集合，称为位示图。

(1)顺序扫描位示图，从中找出一个或一组其值为 “0”的二进制位(“0"表示空闲时)。

(2)将所找到的一一个或一-组二进制位，转换成与之相应的盘块号。假定找到的其值为“0"的二进制位，位于位示
的第i行、第j列，则其相应的盘块号应按下式计算:
式中，n代表每行的位数。

这种方法的主要优点是，从位示图中很容易找到一个或 -组相邻接的空闲 盘块。此外，由于位示
图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行盘区分配时，无需首先把盘
区分配表读入内存，从而节省了许多磁盘的启动操作。位示图常用于微型机和小型机中.

空闲表法和空闲链表发，都不适用于大型文件系统，
因为这会使空闲表或空闲链表太长。UNIX系统中采用的是
(2)文件区中的所有空闲盘块，被分成若干个组.....
(3)将每--组含有的盘块总数N和该组所有的盘块号

7.7提高磁盘I/O速度的途径和磁盘容错技术

(1)通过存取控制机制来防止由人为因素所造成的文件不安全性。

(2)通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。

(3)通过“后备系统”来防止由自然因素所造成的不安全性。

容错技术是通过在系统中设置冗余部件的办法，来提高系统可靠性的一种技术，磁盘容错技术则是通
过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的一种技术。即当磁盘系统的某部
分出现缺陷或故障时，磁盘仍能正常工作，且不致造成数据的丢失或错误。

1)双份目录和双份文件分配表

在磁盘上存放的文件目录和文件分配表FAT,是文件管理所用的重要数据结构。如果这些表格被破坏，将导致
磁盘上的部分或全部文件成为不可访问的，因而也就等效于文件的丢失。为了防止这类情况发生，可在不同的磁盘
上或在磁盘的不同区域中，分别建立(双份)目录表和FAT.其中，一份被称为主目录及主FAT;把另一份称为备份目录及备份FAT.

2)热修复重定向和写后读校验

系统将磁盘容量的一部分作为热修复重定向区，用于存放当发现磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记，以便于以后对
OS要向第12磁道的第10扇区的盘快中写入数据时，发现此盘块是坏的，于是便将数据写入热修复区中第153磁道的第27扇区的盘块中.....

事务是用于访问和修改各种数据项的一一个程序单位。事务也可以被看作是一系列相关读和写操作。 被访问的数据可以
分散地存放在同一文件的不同记录中，也可放在多个文件中。只有对分布在不同位置的同--数据所进行的读和写(含修改)操
作全部完成时，才能再以托付操作(Commit Operation)来终 止事务。只要有一一个读、写或修改操作失败，便须执行夭折操
作(Abort Operation)。 读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导致的。

引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化，
即每隔定时间便做一次下述工作:
首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中;其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中;然后是将事务记录表中的<检查点〉记录，
最后是每当出现-一个<检查点>记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。

-1.利用互斥锁实现“顺序性”
-2.利用互斥锁和共享锁实现顺序性

互斥锁仅允许-一个事务对相应对象执行读或写操作，而共享锁
则允许许多个事务对相应对象执行读操作，而不允许其中任何
一个事务对对象执行写操作。

为了描述盘块的使用情况，通常利用空闲盘块表(链)来记录所有尚未使用的空闲盘块的编号，文件分配表
FAT则是用于记录已分配盘块的使用情况。为了保证盘块数据结构的一致性，可利用软件方法构
成一一个计数器表，每个盘块号占一个表项，可有....-1项，N为盘块总数。每一一个表项中包含两个
计数器，分别用作空闲盘块号计数器和数据盘块号计数器......如果情况正常，这两组计数器中对应的一对数据应该互补....

在UNIX类型的文件目录中，其每个目录项内都含有一一个索引结点号，用于指向该文件的索引结点，对于一
个共享文件，其索引结点号会在目录中出现多次;另一方面，在该共享文件的索引结点中有一一个链接计数
count,用来指出共享本文件的用户(进程)数，在正常情况下，这两个数据应该一致，否则就会出现数据不致性差错....

1.文件类型与文件存储器、存取方法的关系:磁带是属于顺序组织的存储设备，用它来作为文件存储器，则宜采用连续分配的文件组织。
所以，它对于顺序存取的文件是合适的。在此情况下，当处理完一一个记录后，由于磁头已移到下一一个记录所在的物理块处，
固而可随即存取并处理下一一个记录而不需要额外的寻找时间。对于直接存取设备(磁盘、磁鼓)来说，上 述四种文件组织(包括Hash文件组织)都可以采用，究竟何种最适合，
则要看文件的使用情况而定。如果文件是顺序存取的，组织成连续文件或串联文件是可行的，但是，由于连续分配方式要求在建立文件时就得确定文件的大小，因而缺乏灵活性;
而链接式分配的串联文件具有较大的灵活性:扩展时可申请任一~空闲物理块;文件压缩时，可把不用的物理块归还给系统，以供其它文件使用。

如采用直接存取方式，且文件大小是不固定的，则选择索引式文件组织或计算寻址结构是适宜的，它们的灵活性比较大，至于串联文件，在这种场合反而是低效的。
因为要顺序通过一-系列物理块才能找到需要的记录，故存取速度慢。对于索引式文件组织，也可采用顺序存取方法，但其效率不如其它文件组织。
若文件大小是固定的，则采用连续分配方式文件组织也是可取的。链接块式和Hash结构文件，它们的优点是都能实现物理块的动态分配和回收;连续分配方式的主要优点是:实现简单，
不需要索引表，也无需链接指针。

-(1)、什么是记录的成组与分解:
由于磁盘块的大小是预先划分好的，大小固定，而逻辑记录的大小是用户文件
性质决定的，不一定和块大小一致，如果逻辑记录比物理块小得多时，可以把多个逻辑记录存放在一一个块中，这就
是记录的成组，用户使用时再把读取的一块信息中分离出所需的记录，这就是记录的分解。

-(2)、记录的成组:
把若干个逻辑记录合成-组存入一块的工作称为“记录的成组”每块中逻辑记录的个数称块因子利用主存缓冲区可以把多个逻辑记录一次性保存到磁
盘块上。也就是当记录要求存盘时，先存入主存缓冲区，缓冲区的大小等于最大逻辑长度乘以成组的块因子，就是块的大小。在缓冲区未存满时，不启动磁盘写，这样就提高了存
储空间的利用率，减少启动外设的次数，提高了系统的工作效率。
这是记录成组的一一个逆过程，先从磁盘中找到记录所在的块，并将本块读入主存缓冲区，再从缓冲区取出所需要的记录送到用户工作区。如果用户所
需的记录已经在缓冲区中，则不需要启动外设读块信息，这也可以提高系统工作效率。

例:假定磁带的记录密度为每英寸800个字符，每个逻辑记录长为160个字符，块与块之间的间隙为
0.6英寸，现有1000个逻辑记录需要存储到磁带上，分别回答下列问题:
a.不采用成组操作时磁带空间的利用率
b.采用以5个逻辑记录为一-组的成组操作时磁带
c.为了使磁带空间的利用率大于50%，采用记录
成组时其块因子至少为多少?