【白话文严蔚敏数据结构】顺序文件

顺序文件就是逻辑顺序与物理顺序一致的文件叫做顺序文件，如果逻辑相邻物理相邻叫做连续文件，如果逻辑相邻物理不相邻叫做串联文件。

顺序文件是根据记录的位置（绝对位置和相对位置都可以）进行存取的文件组织方式。顺序文件的优点是连续存取速度快，因此主要用于只进行顺序存取和批量修改的情况。在进行直接存取时，如果对响应时间要求不严格，也可以使用顺序文件。

磁带是顺序存取的设备，只有顺序文件才能存到磁带上，磁带适合文件数据大，文件变化小的情况。对磁带文件进行修改的时候，要对文件进行复制一份，然后在复制的时候修改，对磁带文件进行添加的时候，只能添加到文件的末尾，存取磁带第 \(i\) 个记录时候，要先获得它前面的 \(i-1\) 个记录。为了修改更加方便，要求待复制的顺序文件按照关键字有序排列。

磁带文件的批处理有三条磁带，第一条磁带放主文件，第二条磁带放批处理命令，第三条磁带，放新的主文件。主文件按关键字有序，批处理命令按主文件顺序有序，然后将主文件和事务文件归并成一个新的主文件。

分析算法时间复杂度，如果主文件包含 \(n\) 个记录，事务文件包含 \(m\) 个记录。事务文件进行内部排序，最小时间复杂度为 \(O(mlogm)\) ，内部归并的时间复杂度为 \(O(n+m)\) ，总的内部处理时间为 \(O(n+mlogm)\) 。

对于一批需要进行处理的文件，可以将它们存储在磁带上，然后按照磁带上的顺序一个一个进行处理。更新不增加磁带长度时候，可以不用复制一条新的磁带，直接修改原来的主文件即可。