基本介紹
- 中文名：磁碟檔案結構
- 外文名：Disk File Structure
- 學科：計算機
- 定義：檔案在磁碟上的分配方式
- 種類：連結式檔案結構、索引式檔案結構
- 領域：檔案管理
簡介,檔案結構,磁碟檔案結構的種類,順序式的檔案結構,連結式檔案結構,索引式檔案結構,
簡介
磁碟具有可直接訪問的特性，故當利用磁碟來存放檔案時，具有很大的靈活性。磁碟檔案結構是指檔案在磁碟上的分配方式。屬於檔案外存分配方式，檔案的物理結構直接與外存分配方式有關。在採用不同的分配方式時，將形成不同的檔案物理結構。例如，在採用連續分配方式時的檔案物理結構，將是順序式的檔案結構；連結分配方式將形成連結式檔案結構；而索引分配方式則將形成索引式檔案結構。
檔案結構
檔案是由一系列的記錄組成的。檔案系統設計的關鍵要素，是指將這些記錄構成一個檔案的方法，以及將一個檔案存儲到外存上的方法。事實上，對於任何一個檔案，都存在著以下兩種形式的結構：
(1) 檔案的邏輯結構(File Logical Structure)。這是從用戶觀點出發所觀察到的檔案組織形式， 是用戶可以直接處理的數據及其結構， 它獨立於檔案的物理特性， 又稱為檔案組織(FileOrganization)。
(2) 檔案的物理結構，又稱為檔案的存儲結構，是指檔案在外存上的存儲組織形式。這不僅與存儲介質的存儲性能有關，而且與所採用的外存分配方式有關。
無論是檔案的邏輯結構，還是其物理結構，都會影響對檔案的檢索速度。
磁碟檔案結構的種類
順序式的檔案結構
順序式的檔案結構即檔案採用連續分配方式，連續分配(Continuous Allocation)要求為每一個檔案分配一組相鄰接的盤塊。 一組盤塊的地址定義了磁碟上的一段線性地址。例如，第一個盤塊的地址為 b，則第二個盤塊的地址為b+1，第三個盤塊的地址為 b+2……。通常，它們都位於一條磁軌上，在進行讀/寫時，不必移動磁頭，僅當訪問到一條磁軌的最後一個盤塊後，才需要移到下一條磁軌，於是又去連續地讀/寫多個盤塊。在採用連續分配方式時，可把邏輯檔案中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的檔案結構稱為順序檔案結構，此時的物理檔案稱為順序檔案。這種分配方式保證了邏輯檔案中的記錄順序與存儲器中檔案占用盤塊的順序的一致性。為使系統能找到檔案存放的地址，應在目錄項的“檔案物理地址”欄位中，記錄該檔案第一個記錄所在的盤塊號和檔案長度(以盤塊數進行計量)。圖 1示出了連續分配的情況。圖中假定了記錄與盤塊的大小相同。Count 檔案的第一個盤塊號是 0，檔案長度為 2，因此是在盤塊號為 0 和 1 的兩盤塊中存放檔案 1 的數據。
連續分配的主要優點如下：
(1) 順序訪問容易。訪問一個占有連續空間的檔案非常容易。系統可從目錄中找到該順序檔案所在的第一個盤塊號，從此開始順序地、逐個盤塊地往下讀/寫。連續分配也支持直接存取。例如，要訪問一個從 b 塊開始存放的檔案中的第 i 個盤塊的內容，就可直接訪問b+i 號盤塊。
(2) 順序訪問速度快。因為由連續分配所裝入的檔案，其所占用的盤塊可能是位於一條或幾條相鄰的磁軌上，這時，磁頭的移動距離最少，因此，這種對檔案訪問的速度是幾種存儲空間分配方式中最高的一種。
連續分配的主要缺點如下：
(1) 要求有連續的存儲空間。要為每一個檔案分配一段連續的存儲空間，這樣，便會產生出許多外部碎片，嚴重地降低了外存空間的利用率。如果是定期地利用緊湊方法來消除碎片，則又需花費大量的機器時間。
(2) 必須事先知道檔案的長度。要將一個檔案裝入一個連續的存儲區中，必須事先知道檔案的大小，然後根據其大小，在存儲空間中找出一塊其大小足夠的存儲區，將檔案裝入。在有些情況下，知道檔案的大小是件非常容易的事，如可拷貝一個已存檔案。但有時卻很難，在此情況下，只能靠估算。如果估計的檔案大小比實際檔案小，就可能因存儲空間不足而中止檔案的拷貝，須再要求用戶重新估算，然後再次執行。這樣，顯然既費時又麻煩。這就促使用戶往往將檔案長度估得比實際的大，甚至使所計算的檔案長度比實際長度大得多，顯然，這會嚴重地浪費外存空間。對於那些動態增長的檔案，由於開始時檔案很小，在運行中逐漸增大，比如，這種增長要經歷幾天、幾個月。在此情況下，即使事先知道檔案的最終大小，在採用預分配存儲空間的方法時，顯然也將是很低效的，即它使大量的存儲空間長期地空閒著。
連結式檔案結構
連結式檔案結構即檔案採用連結分配方式，如同記憶體管理一樣， 連續分配所存在的問題就在於: 必須為一個檔案分配連續的磁碟空間。如果在將一個邏輯檔案存儲到外存上時，並不要求為整個檔案分配一塊連續的空間，而是可以將檔案裝到多個離散的盤塊中，這樣也就可以消除上述缺點。在採用連結分配(Chained Allocation)方式時，可通過在每個盤塊上的連結指針，將同屬於一個檔案的多個離散的盤塊連結成一個鍊表，把這樣形成的物理檔案稱為連結檔案。由於連結分配是採取離散分配方式，消除了外部碎片，故而顯著地提高了外存空間的利用率；又因為是根據檔案的當前需要，為它分配必需的盤塊，當檔案動態增長時，可動態地再為它分配盤塊，故而無需事先知道檔案的大小。此外，對檔案的增、刪、改也十分方便。
連結方式又可分為隱式連結和顯式連結兩種形式。
隱式連結
在採用隱式連結分配方式時，在檔案目錄的每個目錄項中，都須含有指向連結檔案第一個盤塊和最後一個盤塊的指針。圖 2 中示出了一個占用 5 個盤塊的連結式檔案。在相應的目錄項中，指示了其第一個盤塊號是 9，最後一個盤塊號是 25。而在每個盤塊中都含有一個指向下一個盤塊的指針，如在第一個盤塊 9 中設定了第二個盤塊的盤塊號是 16；在16 號盤塊中又設定了第三個盤塊的盤塊號 1。如果指針占用 4 個位元組，對於盤塊大小為 512位元組的磁碟，則每個盤塊中只有 508 個位元組可供用戶使用。
隱式連結分配方式的主要問題在於：它只適合於順序訪問，它對隨機訪問是極其低效的。如果要訪問檔案所在的第 i 個盤塊，則必須先讀出檔案的第一個盤塊……，就這樣順序地查找直至第 i 塊。當 i=100 時，須啟動 100 次磁碟去實現讀盤塊的操作，平均每次都要花費幾十毫秒。可見，隨機訪問的速度相當低。此外，只通過連結指針來將一大批離散的盤塊連結起來，其可靠性較差，因為只要其中的任何一個指針出現問題，都會導致整個鏈的斷開。
為了提高檢索速度和減小指針所占用的存儲空間， 可以將幾個盤塊組成一個簇(cluster)。比如，一個簇可包含 4 個盤塊，在進行盤塊分配時，是以簇為單位進行的。在連結檔案中的每個元素也是以簇為單位的。這樣將會成倍地減小查找指定塊的時間，而且也可減小指針所占用的存儲空間，但卻增大了內部碎片，而且這種改進也是非常有限的。
顯式連結
這是指把用於連結檔案各物理塊的指針，顯式地存放在記憶體的一張連結表中。該表在整個磁碟僅設定一張，如圖 3所示。表的序號是物理盤塊號，從 0 開始，直至 N-1；N 為盤塊總數。在每個表項中存放連結指針，即下一個盤塊號。在該表中，凡是屬於某一檔案的第一個盤塊號，或者說是每一條鏈的鏈首指針所對應的盤塊號，均作為檔案地址被填入相應檔案的 FCB 的“物理地址”欄位中。由於查找記錄的過程是在記憶體中進行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁碟的次數。由於分配給檔案的所有盤塊號都放在該表中，故把該表稱為檔案分配表 FAT(File Allocation Table)。
索引式檔案結構
索引式檔案結構即檔案採用索引分配方式，一般分為單級索引分配、多級索引分配、混合索引分配方式。
單級索引分配
連結分配方式雖然解決了連續分配方式所存在的問題，但又出現了下述另外兩個問題：
(1) 不能支持高效的直接存取。 要對一個較大的檔案進行直接存取， 須首先在 FAT 中順序地查找許多盤塊號。
(2) FAT 需占用較大的記憶體空間。由於一個檔案所占用盤塊的盤塊號是隨機地分布在FAT 中的， 因而只有將整個 FAT 調入記憶體， 才能保證在 FAT 中找到一個檔案的所有盤塊號。當磁碟容量較大時，FAT 可能要占用數兆位元組以上的記憶體空間，這是令人難以接受的。事實上，在打開某個檔案時，只需把該檔案占用的盤塊的編號調入記憶體即可，完全沒有必要將整個 FAT 調入記憶體。為此，應將每個檔案所對應的盤塊號集中地放在一起。索引分配方法就是基於這種想法所形成的一種分配方法。它為每個檔案分配一個索引塊(表)，再把分配給該檔案的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個含有許多盤塊號的數組。在建立一個檔案時，只需在為之建立的目錄項中填上指向該索引塊的指針。圖4示出了磁碟空間的索引分配圖。
索引分配方式支持直接訪問。當要讀檔案的第 i 個盤塊時，可以方便地直接從索引塊中找到第 i 個盤塊的盤塊號；此外，索引分配方式也不會產生外部碎片。當檔案較大時，索引分配方式無疑要優於連結分配方式。
索引分配方式的主要問題是：可能要花費較多的外存空間。每當建立一個檔案時，便須為之分配一個索引塊，將分配給該檔案的所有盤塊號記錄於其中。但在一般情況下，總是中、小型檔案居多，甚至有不少檔案只需 1～2 個盤塊，這時如果採用連結分配方式，只需設定 1～2 個指針。如果採用索引分配方式，則同樣仍須為之分配一索引塊。通常是採用一個專門的盤塊作為索引塊，其中可存放成百個、甚至上千個盤塊號。可見，對於小檔案採用索引分配方式時，其索引塊的利用率將是極低的。
多級索引分配
當 OS 為一個大檔案分配磁碟空間時， 如果所分配出去的盤塊的盤塊號已經裝滿一個索引塊時， OS 便為該檔案分配另一個索引塊， 用於將以後繼續為之分配的盤塊號記錄於其中。依此類推，再通過鏈指針將各索引塊按序連結起來。顯然，當檔案太大，其索引塊太多時，這種方法是低效的。此時，應為這些索引塊再建立一級索引，稱為第一級索引，即系統再分配一個索引塊，作為第一級索引的索引塊，將第一塊、第二塊……等索引塊的盤塊號填入到此索引表中，這樣便形成了兩級索引分配方式。如果檔案非常大時，還可用三級、四級索引分配方式。
混合索引分配方式
所謂混合索引分配方式，是指將多種索引分配方式相結合而形成的一種分配方式。例如，系統既採用了直接地址，又採用了一級索引分配方式，或兩級索引分配方式，甚至還採用了三級索引分配方式。 這種混合索引分配方式已在 UNIX 系統中採用。 在 UNIX SystemⅤ的索引結點中， 共設定了13個地址項， 即iaddr(0)～iaddr(12)， 如圖5所示。 在BSD UNIX的索引結點中，共設定了 13 個地址項，它們都把所有的地址項分成兩類，即直接地址和間接地址。
