[科普中国]-顺序分块文件-

简介

文件是指由创建者所定义的、具有文件名的一组相关元素的集合。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例如，可以将一个班的学生记录作为一个文件。

顺序分块文件是是将顺序文件分为若干块，使其分块有序。所谓分块有序（block order）是指将文件划分为若干块，每一块内不要求有序（即快内无序），但第二块中所有记录的关键码均大于第一块中所有记录的关键码，第三块中所有记录的关键码均大于第二块中所有记录的关键码。2顺序分块文件主要目的是减少文件查找的代价。

顺序文件顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。一切存储在顺序存取存储器(如磁带)上的文件，都只能是顺序文件。顺序文件是最常用的文件组织形式。顺序文件由一系列记录按照某种顺序排列形成。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。

顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。

在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。例如，有一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5×103个记录；如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。

顺序文件的另一个缺点是，如果想增加或删除一个记录，都比较困难。为了解决这一问题，可以为顺序文件配置一个运行记录文件(Log File)或称为事务文件(Transaction File)，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如4小时，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。

文件结构分类文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的顺序进行排列。一般地，可归纳为以下两种情况：

第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录……，依此类推。

第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必须从头开始，逐个记录地查找，直至找到指定的记录，或查完所有的记录为止。

查找方法顺序分块文件查找方法和顺序文件查找方法差不多，主要有：顺序查找法存取，也可以用分块查找或二分查找进行存取方法。

顺序查找顺序查找法即顺序扫描文件，按记录的主关键字逐个查找。要检索第i个记录，必须检索前i-1个记录。注意：

① 这种查找法对于少量的检索是不经济的，但适合于批量检索。

② 顺序存取存储器上的文件只能用顺序查找法存取

分块查找法具体方法：设文件按主关键字的递增序，每100个记录为一块，各块的最后一个记录的主关键字为Kl00，K200，…，K100i，…：

查找时，将所要查找的记录的主关键字K，依次和各块的最后一个记录的主关键字比较，当K大于K100(i-1)且小于或等于K100i时，则在第i块内进行扫描。

注意：分块查找法在查找时不必扫描整个文件中的记录。

二分查找法① 二分查找法只适合对较小的文件或一个文件的索引进行查找。

② 当文件很大，在磁盘上占有多个柱面时，二分查找将引起磁头来回移动，增加寻查时间。