順序存取

存取方式是用户通過對文件的存取完成對文件的各種操作。文件的存取方式是由文件的性質和用户使用文件的情況確定的，一般有順序存取和隨機存取兩種。順序存取是按順序存入或檢出文檔中數據項的存取方法。典型的處理方式是把數據按順序存貯在磁帶上，使用時按事先確定的順序依次提取磁帶上的數據，同時按事先設計好的格式打印出來。這種方法遠比隨機存取更難使用，而且對於有些問題證明是不可行的。使用順序存取的需要對於算法的選擇產生了極大的而且往往是災難性的影響。隨機存取又稱直接存取，即允許用户根據關鍵字存取文件的任何一個記錄，或者根據存取命令把讀寫指針轉移到指定位置進行讀寫 ^[2]  。

文件是記錄的集合。文件中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進行排列。一般地，可歸納為以下兩種情況：

第一種是串結構，各記錄之間的順序與關鍵字無關。通常的辦法是由時間來決定，即按存入時間的先後排列，最先存入的記錄作為第一個記錄，其次存入的為第二個記錄……，依此類推。

第二種情況是順序結構，指文件中的所有記錄按關鍵字(詞)排列。可以按關鍵詞的長短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。對順序結構文件可有更高的檢索效率，因為在檢索串結構文件時，每次都必須從頭開始，逐個記錄地查找，直至找到指定的記錄，或查完所有的記錄為止。而對順序結構文件，則可利用某種有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法來提高檢索效率。其中又有定長的、不定長的順序文件，只能順序存取。。對於定長記錄的順序文件，如果已知當前記錄的邏輯地址，便很容易確定下一個記錄的邏輯地址。在讀一個文件時，可設置一個讀指針 Rptr，令它指向下一個記錄的首地址，每當讀完一個記錄時，便執行

Rptr:=Rptr + L

操作，使之指向下一個記錄的首地址，其中的 L 為記錄長度。類似地，在寫一個文件時，也應設置一個寫指針 Wptr，使之指向要寫的記錄的首地址。同樣，在每寫完一個記錄時，又須執行以下操作:

Wptr:=Wptr + L

對於變長記錄的順序文件，在順序讀或寫時的情況相似，但應分別為它們設置讀或寫指針，在每次讀或寫完一個記錄後，須將讀或寫指針加上 L。L 是剛讀或剛寫完的記錄的長度。順序文件的最佳應用場合是在對諸記錄進行批量存取時，即每次要讀或寫一大批記錄時。此時，對順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上，並能有效地工作。

在交互應用的場合，如果用户(程序)要求查找或修改單個記錄，為此係統便要去逐個地查找諸記錄。這時，順序文件所表現出來的性能就可能很差，尤其是當文件較大時，情況更為嚴重。例如，有一個含有 10 4 個記錄的順序文件，如果對它採用順序查找法去查找一個指定的記錄，則平均需要查找 5×10 3 個記錄；如果是可變長記錄的順序文件，則為查找一個記錄所需付出的開銷將更大，這就限制了順序文件的長度。順序文件的另一個缺點是，如果想增加或刪除一個記錄都比較困難。為了解決這一問題， 可以為順序文件配置一個運行記錄文件(Log File)，或稱為事務文件(Transaction File)，把試圖增加、刪除或修改的信息記錄於其中，規定每隔一定時間，例如 4 小時，將運行記錄文件與原來的主文件加以合併，產生一個按關鍵字排序的新文件 ^[3]  。

常用的文件存儲設備有磁盤、磁帶、光盤等。存儲設備的特性決定了文件的存取。為了有效地利用文件存儲設備和便於對文件信息進行處理，通常把文件的存儲空間劃分為若干個大小相等的物理塊。順序存取設備是指只有當前面的物理塊被存取以後，才能存取後面的物理塊。磁帶就是一種典型的順序存取設備，磁帶的兩個相鄰的物理塊之間一般有一個間隙，其目的是為了讓磁帶機存取後面的物理塊時方便地找到下個物理塊的位置。