顺序文件(Sequential File)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的,即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。若次序相继的两个物理记录在存储介质上的存储位置是相邻的,则又称连续文件;若物理记录之间的次序由指针相链表示,则称串联文件。

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

(1)存取第i个记录,必须先搜索在它之前的i一1个记录。

(2)插入新的记录时只能加在文件的末尾。

(3)若要更新文件中的某个记录,则必须将整个文件进行复制。

由于顺序文件的优点是连续存取的速度快,因此主要用于只进行顺序存取、批量修改的情况。若对应答时间要求不严时亦可进行直接存取。

磁带是一种典型的顺序存取设备,因此存储在磁带上的文件只能是顺序文件。磁带文件适合于文件的数据量甚大、平时记录变化少、只作批量修改的情况。在对磁带文件作修改时,一般需用另一条复制带将原带上不变的记录复制–遍,同时在复制的过程中插入新的记录和用更改后的新记录代替原记录写入。为了修改方便起见,要求待复制的顺序文件按关键字有序(若非数据库文件,则可将逻辑记录号作为关键字)。

磁带文件的批处理过程可如下进行:

待修改的原始文件称做主文件,存放在条磁带上,所有的修改请求集中构成一个文件,称做事务文件,存放在另一台磁带上,尚需第三台磁带作为新的主文件的存储介质。主文件按关键字自小至大(或自大至小)顺序有序,事务文件必须和主文件有相同的有序关系。因此,首先对事务文件进行排序,然后将主文件和事务文件归并成一个新的主文件。图1为这个过程的示意图。在归并的过程中,顺序读出主文件与事务文件中的记录,比较它们的关键字并分别进行处理。对于关键字不匹配的主文件中的记录,则直接将其写入新主文件中。“更改”和“删去”记录时,要求其关键字相匹配。“删去”不用写人,而“更改”则要将更改后的新记录写入新主文件。“插人”时不要求关键字相匹配,可直接将事务文件上要插入的记录写到新主文件的适当位置。

图1 磁带文件批处理示意图

​例如有一个银行的账目文件:其主文件保存着各储户的存款余额;每个储户作为一个记录,储户账号为关键字;记录按关键字从小到大顺序排列。一天的存入和支出集中在一个事务文件中,事务文件也按账号排序,成批地更改主文件并得到一个新的主文件,其过程如图2所示:

图2 银行账目文件成批示意图

​批处理的示意算法如算法1所示。算法中用到的各符号的含义说明如下:

f——主文件;g—事务文件; h─—新主文件。上述三者都按关键字递增排列。事务文件的每个记录中,还增设一个代码以示修改要求,其中:“I”表示插入;“D”表示删去;“U”表示更改。

算法 1

​分析批处理算法的时间。假设主文件包含n个记录,事务文件包含m个记录。一般情况下,事务文件较小,可以进行内部排序,则时间复杂度为O(mlogm)。内部归并的时间复杂度为O(n十m),则总的内部处理的时间为O(mlogm十n)。假设所有的输人/输出都是通过缓冲区进行的,并假设缓冲区大小为s(个记录),则整个批处理过程中读/写外存的次数为

磁盘上的顺序文件的批处理和磁带文件类似,只是当修改项中没有插人,且更新时不增加记录的长度时,可以不建立新的主文件,而直接修改原来的主文件即可。显然,磁盘文件的批处理可以在一台磁盘组上进行。

对顺序文件进行顺序查找,其平均查找长度为(n’+1)/2,其中n’为文件所含物理记录的数目(相对外存读/写而言,内存查找的时间可以忽略不计)。对磁盘文件可以进行分块查找或折半查找(对不定长文件不能进行折半查找)。但是,若文件很大,在磁盘上占多个柱面时,折半查找将引起磁头来回移动,增加寻查时间。

假若某个顺序文件,其记录修改的频率较低,则用批处理并不适宜,此时可另建立一个附加文件,以存储新插人和更新后的记录,待附加文件增大到一定程度时再进行批处理。在检索时可以先查主文件,若不成功再查附加文件,或反之。显然这将增加检索的时间,但可以采取其他措施弥补之。

然后今天就讲到这里啦,大家记得点赞收藏,分享转发,关注小哥哥哦! 最后,如果你想学或者正在学C/C++编程,可以加入小编的编程学习C/C++企鹅圈https://jq.qq.com/?_wv=1027&k=vLNylJeG