文件系統 | 文件的物理結構

05-13

連續文件

將邏輯文件中的信息順序存儲到連續的物理盤塊中。

如下是外存中的物理盤塊的分布圖：

這是我們文件的目錄：

在文件目錄中，有兩個屬性的信息：文件名和物理地址（在外存中存放的位置）。

主要優點：

順序訪問速度快。只要找到一個盤塊的位置，就可以依次很容易的找到其他的盤塊。
可隨機存取。

主要缺點：

磁碟空間會產生碎片。如上面的第18號盤塊。
文件修改困難。比較難以實現文件的增刪改操作。

串聯文件

利用指針將文件所佔的盤塊連接起來。

串聯文件結構（隱式鏈接）

串聯文件的缺點：

文件容易丟失。一旦某一個盤塊的後續位置信息丟失就會遺失之後的所有節點。
文件只能順序存取。只能從第一個節點開始依次讀取磁碟塊。

文件映照結構（顯式鏈接）

所有鏈接指針統一存放在一張顯示的鏈接表(fat表：文件分配表)中。一個邏輯磁碟設置一張表，以物理盤塊號為序，表項內容為指向某文件的下一盤塊的指針。

例：若文件f1佔據了2，4，5，1四個盤塊：

FAT文件系統磁碟組織結構：

FAT1 和 FAT2 是互為備份的連個相同的文件。

FAT32引導區主要內容有：

每扇區位元組數；通常512B
每簇扇區數；
FAT1的位置；
磁碟分區大小（扇區數）；
FAT表大小（扇區數）；
根目錄位置；
引導區備份扇區的位置；
文件系統類型。

串聯文件性能評價

1.存儲空間利用率高；沒有文件存儲空間碎片的問題了。

2.文件創建時用戶不必指出文件的大小；採用指針的形式。

3.文件動態擴充和修改容易。採用指針的形式。

4.順序存取效率高，隨機存取效率較低。

FAT 表大小的計算方法

例：一個磁碟分區大小為20GB，若盤塊大小為1KB，計算該磁碟分區的FAT表大小？

盤塊數=20GB/1KB =20MB≈2^25B，所有至少需要25個二進位位。由於每個FAT的表項可以是半個整數倍，所以25位最少取3.5個位元組。所以FAT表大小=20MB×3.5B=70MB

索引文件

1、什麼是索引文件

索引表：系統為每個文件建立的邏輯塊號與物理塊號的對照表。

如對應的文件 file1 分配到4個磁碟塊：

其所構建的索引表對應的結構就是：

索引塊：存放文件的索引表的物理塊，其塊號保存在文件目錄項的物理地址中；

文件由數據文件和索引表構成。這種文件稱為索引文件。

單級索引分配

就如上例所示的樣子

多級索引分配

文件file2分配到1000個磁碟塊：2，3，5，20，22，25，…1200，1511，若每個盤塊號佔4B，每個盤塊1KB：

由於每個盤塊只有1KB，所以最多存放的盤塊號是 1KB/4B = 256個。不能存放1000個盤塊號，所以需要分組，分為四個部分。為了找到剛才建立的索引塊，所以我們需要建立一個二級索引來記錄以及索引所佔的盤塊號。最好，我們需要在文件目錄中記錄二級索引表所佔的盤塊號。

混合索引分配

Unix：i 節點中的物理地址欄位 iaddr(13)

iaddr(0) ～iaddr(9): 直接地址；

Iaddr(10)：一級索引；

iaddr(11): 二級索引；

iaddr(12): 三級索引。

例：設某文件長度為xB，若盤塊大小為4KB，每個盤塊號4B，則:

（1）文件盤塊數量為： n=[x/4k] + 1

（2）每個索引塊能存放的盤塊號數量：=4K/4 =1K(個)

對 n 進行分類：

(1)n≤10：

所有數據塊號全部存放在iaddr(0) ～iaddr(9)中：

(2)10＜n≤1034：

前面10個數據塊號全部存放在iaddr(0) ～iaddr(9)中；

剩下的不超過1024個數據塊號放在一個一級索引塊中；

並將該一級索引塊號存入iaddr(10)中：

(3)1034＜n≤1034+1M：

前面10個數據塊號全部存放在iaddr(0) ～iaddr(9)中；

剩下的不超過1024+1M個數據塊號放在不超過1025個一級索引塊

將第一個一級索引塊號存入iaddr(10)中；

將剩下的不超過1024個一級索引塊號存入一個二級索引塊中；

最後將該二級索引塊號存入iaddr(11)中：

（4)1034+1M＜n≤1034+1M+1G：

前面10個數據塊號全部存放在iaddr(0) ～iaddr(9)中；

剩下的不超過1024+1M+1G個數據塊號放在不超過1025+1M個一級索引塊中；

將第一個一級索引塊號存入iaddr(10)中；

剩下的不超過1024+1M個一級索引塊號存入≤1025個二級索引塊中；

再將第一個二級索引塊存入iaddr(11)中；

剩下的不超過1024個二級索引塊號存入一個三級索引塊中；

最後將該三級索引塊塊號存入iaddr(12)中：

文件物理結構的比較

順序文件的優點是不需要額外的空間開銷，只要在文件目錄中指出文件的大小和首塊的塊號即可，對順序的訪問效率很高。適應於順序存取且文件不經常修改的情況。缺點是文件動態地增長和縮小時系統開銷很大；文件創建時要求用戶提供文件的大小；存儲空間浪費較大。
鏈接文件（串聯文件）克服了連續文件的不足之處，但文件的隨機訪問系統開銷較大。適應於順序訪問的文件。
索引文件既適應於順序存訪問，也適應於隨機訪問，是一種比較好的文件物理結構，但要有用於索引表的空間開銷和文件索引的時間開銷。UNIX系統和Linux系統是使用索引結構成功的例子。