順序檔案是記錄按其在檔案中的邏輯順序依次進入存儲介質而建立的，即順序檔案中物理記錄的順序和邏輯記錄的順序是一致的。有時檔案中的記錄個數很多，查找的代價很大，為了加快查找速度，將檔案劃分為若干塊。順序分塊檔案是指將順序檔案中若干個記錄分為一塊，或者是將順序檔案分為若干塊。
基本介紹
- 中文名：順序分塊檔案
- 外文名：Sequential Block File
- 學科：計算機
- 定義：將順序檔案分為若干塊
- 有關術語：順序檔案
- 領域：數據結構
簡介,順序檔案,檔案結構分類,查找方法,順序查找,分塊查找法,二分查找法,
簡介
檔案是指由創建者所定義的、具有檔案名稱的一組相關元素的集合。檔案在檔案系統中是一個最大的數據單位，它描述了一個對象集。例如，可以將一個班的學生記錄作為一個檔案。
順序分塊檔案是是將順序檔案分為若干塊，使其分塊有序。所謂分塊有序（block order）是指將檔案劃分為若干塊，每一塊內不要求有序（即快內無序），但第二塊中所有記錄的關鍵碼均大於第一塊中所有記錄的關鍵碼，第三塊中所有記錄的關鍵碼均大於第二塊中所有記錄的關鍵碼。順序分塊檔案主要目的是減少檔案查找的代價。
順序檔案
順序檔案是指按記錄進入檔案的先後順序存放、其邏輯順序和物理順序一致的檔案。一切存儲在順序存取存儲器(如磁帶)上的檔案，都只能是順序檔案。順序檔案是最常用的檔案組織形式。順序檔案由一系列記錄按照某種順序排列形成。其中的記錄通常是定長記錄，因而能用較快的速度查找檔案中的記錄。
順序檔案的最佳套用場合，是在對諸記錄進行批量存取時，即每次要讀或寫一大批記錄。此時，對順序檔案的存取效率是所有邏輯檔案中最高的；此外，也只有順序檔案才能存儲在磁帶上，並能有效地工作。
在互動套用的場合，如果用戶(程式)要求查找或修改單個記錄，為此系統便要去逐個地查找諸記錄。這時，順序檔案所表現出來的性能就可能很差，尤其是當檔案較大時，情況更為嚴重。例如，有一個含有104個記錄的順序檔案，如果對它採用順序查找法去查找一個指定的記錄，則平均需要查找5×103個記錄；如果是可變長記錄的順序檔案，則為查找一個記錄所需付出的開銷將更大，這就限制了順序檔案的長度。
順序檔案的另一個缺點是，如果想增加或刪除一個記錄，都比較困難。為了解決這一問題，可以為順序檔案配置一個運行記錄檔案(Log File)或稱為事務檔案(Transaction File)，把試圖增加、刪除或修改的信息記錄於其中，規定每隔一定時間，例如4小時，將運行記錄檔案與原來的主檔案加以合併，產生一個按關鍵字排序的新檔案。
檔案結構分類
檔案是記錄的集合。檔案中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進行排列。一般地，可歸納為以下兩種情況：
第一種是串結構，各記錄之間的順序與關鍵字無關。通常的辦法是由時間來決定，即按存入時間的先後排列，最先存入的記錄作為第一個記錄，其次存入的為第二個記錄……，依此類推。
第二種情況是順序結構，指檔案中的所有記錄按關鍵字(詞)排列。可以按關鍵字的長短從小到大排序，也可以從大到小排序；或按其英文字母順序排序。對順序結構檔案可有更高的檢索效率，因為在檢索串結構檔案時，每次都必須從頭開始，逐個記錄地查找，直至找到指定的記錄，或查完所有的記錄為止。
查找方法
順序分塊檔案查找方法和順序檔案查找方法差不多，主要有：順序查找法存取，也可以用分塊查找或二分查找進行存取方法。
順序查找
順序查找法即順序掃描檔案，按記錄的主關鍵字逐個查找。要檢索第i個記錄，必須檢索前i-1個記錄。 注意：
① 這種查找法對於少量的檢索是不經濟的，但適合於批量檢索。
② 順序存取存儲器上的檔案只能用順序查找法存取
分塊查找法
具體方法：設檔案按主關鍵字的遞增序，每100個記錄為一塊，各塊的最後一個記錄的主關鍵字為Kl00，K200，…，K100i，…：
查找時，將所要查找的記錄的主關鍵字K，依次和各塊的最後一個記錄的主關鍵字比較，當K大於K100(i-1)且小於或等於K100i時，則在第i塊內進行掃描。
注意：分塊查找法在查找時不必掃描整個檔案中的記錄。
二分查找法
① 二分查找法只適合對較小的檔案或一個檔案的索引進行查找。
② 當檔案很大，在磁碟上占有多個柱面時，二分查找將引起磁頭來回移動，增加尋查時間。
③ 對磁碟等直接存取設備，還可以對順序檔案進行插值查找和跳步查找。
