顺序文件方式

文件是由一系列的记录组成的。文件系统设计的关键要素，是指将这些记录构成一个文件的方法，以及将一个文件存储到外存上的方法。事实上，对于任何一个文件，都存在着以下两种形式的结构:

(1) 文件的逻辑结构(File Logical Structure)。这是从用户观点出发所观察到的文件组织形式， 是用户可以直接处理的数据及其结构， 它独立于文件的物理特性， 又称为文件组织(FileOrganization)。

(2) 文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。

顺序文件方式是存取文件或数据时，文件的逻辑结构和物理结构都采用顺序方式，这和顺序文件结构一样。顺序文件方式的优点：连续存取的速度较快，能实现随机存取。不过修改十分麻烦，要大量移动文件。

顺序文件是记录按其在文件中的逻辑顺序依次存储进入存储介质中的，其逻辑顺序和物理顺序一致。

顺序有序文件：记录按其主关键字有序的顺序文件为顺序有序文件。

顺序无序文件：记录未按其主关键字有序排列的顺序文件为顺序有序文件。为提高检索效率，常将顺序文件组织成有序文件。

顺序文件的修改操作：由于文件中的记录不能像向量空间的数据那样"移动"，故只能通过复制整个文件的方法实现插人、删除和修改等更新操作。

批量处理方式实现顺序文件的更新，批量处理方式工作原理：

① 把所有对顺序文件(以下称主文件)的更新请求，都放入一个较小的事务文件中。
② 当事务文件变得足够大时，将事务文件按主关键字排序，
③ 再按事务文件对主文件进行一次全面的更新，产生一个新的主文件。
④ 最后，清空事务文件，以便积累此后的更新内容。

顺序文件的主要优点是连续存取的速度较快，即若文件中第i个记录刚被存取过，而下一个要存取的是第i+1个记录，则这种存取将会很快完成。磁带是一种典型的顺序存储设备，因此存储在磁带上的文件只能是顺序文件。磁带文件适合于文件的数量甚大、平均记录变化少、只作批量修改的情况。顺序文件可以用顺序查找法存取，也可以用分块查找或二分查找进行存取。^[1]

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

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

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

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

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

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

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

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

③ 对磁盘等直接存取设备，还可以对顺序文件进行插值查找和跳步查找。