文件的物理組織
文件在存儲設備上的存儲組織形式稱為文件的物理組織。文件的物理組織涉及一個文件在存儲設備上是如何放置的。它和文件的存取方法有密切關係，另外也取決於存儲設備的物理特性。
從邏輯上看，所有文件都是連續的，但在物理介質上存放時卻不一定連續。下面介紹4種基本的文件物理組織形式。
1．連續文件
連續文件（又稱作順序文件）是基於磁帶設備的最簡單的物理組織形式，它是把一個邏輯上連續的文件存放在連續編號的物理塊（或物理記錄）中。例如定長記錄文件fileA長度為2000字節，存放在連續分塊的磁帶上，每塊大小設為512字節，這樣它要佔用4塊，設首塊編號30。fileA在磁帶上的存放形式如圖所示。
連續文件的結構
連續文件的優點是在順序存取時速度較快，因為只需把磁頭定位到文件首塊的開頭，就可以連續地存取文件的信息，而不必反覆地對磁頭進行定位，從而加快了文件存取速度。所以，它常用於存放系統文件，如操作系統文件、編譯程序文件和其他由系統提供的實用程序文件，因為這類文件往往被從頭至尾依次存取。另外，這種方式也很容易直接存取文件中的任意一塊。例如，文件的起始塊是b，則訪問該文件第i塊的塊號就是b+i。
連續文件的缺點有：
- 要求建立文件時就確定它的長度，依此來分配相應的存儲空間，這往往很難實現。
- 它不便於文件的動態擴充。在實際計算時，作為輸出結果的文件往往隨執行過程而不斷增加新內容。當該文件需要擴大空間而其後的存儲單元已被別的文件佔用時，就必須另外尋找一個足夠大的空間，把原空間中的內容和新加入內容複製進去。這種文件的“大搬家”是很費時間的。
- 可能出現外部碎片。即在存儲介質上存在很多空閒塊，但它們都不連續，無法被連續的文件使用，從而造成浪費。
當創建一個文件時，實現連續盤塊分配的策略類似於內存的動態分配算法，可採用最先適應算法或最佳適應算法。
2．鏈接文件
為了克服連續文件的缺點，可把一個邏輯上連續的文件分散存放在不同的物理塊中，這些物理塊不要求連續，也不必規則排列。為使系統找到下一個邏輯塊所在的物理塊，可在各物理塊中設立一個指針（稱為鏈接字），它指示該文件的下一個物理塊。為了標示系統中各個文件的文件名、起始塊號和最後塊號，系統設立了一個文件分配表，每個文件在表中單獨佔一項。這裡起始塊號就相當於指向該文件的首指針。
鏈接文件的組織形式
當創建新文件時，就在相應的表項中建立一個新項。文件首指針初始為nil（鏈尾指針值），表示是個空文件，文件長度置為0。當寫文件時，就從空閒盤塊管理系統中找一個空閒盤塊，把信息寫到該塊上，然後把它鏈入該文件的末尾。讀文件時只是簡單地沿著鏈接指針一塊一塊地讀。雖然在鏈接分配方法中也可採用預分配策略，但是更常用的方法還是“按需分配”。這樣，挑選空閒盤塊就很簡單，任何空閒盤塊都可供寫文件使用。
這種物理組織形式的文件稱作鏈接文件或串連文件。鏈接文件的優點是：不會產生磁盤的外部碎片，因為每次按需要只分配一塊，若不夠，再分配另外的塊。所以，文件可以動態增長，只要有空閒塊可供使用就行。這種方法從來也不需要緊縮磁盤空間。
鏈接文件克服了連續文件的缺點，但也有缺點：
- 一般僅適於對信息的順序訪問，而不利於對文件的隨機存取。例如，為了存取一個文件的第i塊中的信息，必須從頭向後順次檢索，直至找到所需的物理塊號。而每次存取鏈接字都需要讀盤，因此，對鏈接文件進行隨機存取的效率是很低的。
- 每個物理塊上增加一個鏈接字，為信息管理添加了一些麻煩。例如，每個鏈接字佔用4 B，每個物理盤塊512 B，那麼，鏈接字就佔用盤塊的0.78%，這部分空間沒有存放文件信息。為了方便管理，信息塊大小通常是2n（n為9，10，11或12），然而鏈接字破壞了信息塊的這種規範尺寸。
- 可靠性。因為文件是通過指針將散佈在盤上的盤塊鏈接在一起的，如果因指針丟失或受損出現故障，會導致鏈接到空閒空間隊列或鏈入另一文件的盤塊鏈中。對此，可以採用雙鏈表，或者在每個盤塊中存放文件名和相關塊號。但這樣做會帶來更大開銷。
在實際系統中，往往採用改進的文件分配表，即常說的FAT（File Allocation Table）表。FAT表出現在每個磁盤分區開頭的扇區中。每個盤塊在表中佔一項，表的序號是物理盤塊號，每個表項中存放鏈接下一盤塊的指針，如圖5-9所示。這樣，FAT表就被用做鏈表。這種辦法簡單有效，在MS-DOS和OS/2操作系統中都使用它。
鏈接文件的結構
3．索引文件
鏈接分配解決了連續分配所存在的外部碎片和預先說明文件大小的問題，但是在沒有采用FAT表的情況下，它並不能有效地支持隨機存取。為了解決這個問題，引入索引文件。
索引文件是實現文件信息非連續存放的另一種方案。系統為每個文件建立一個索引表，其中的表項指出存放該文件的各個盤塊號，如索引表第i項的內容就是該文件的第i個盤塊號。而索引表本身也保存在一個盤塊中，由文件對應的目錄項指出該索引表所在的盤塊號。這種物理組織形式的文件稱做索引文件。
索引文件的組織形式
當創建一個文件時，就為它建立一個索引表，最初所有的盤塊號給定為一個特殊值，如-1。當第一次向該文件寫入第i個邏輯塊時，就從空閒盤塊中取出一塊，然後把它的盤塊號寫入索引表的第i項中。若要讀取文件的第i塊，就檢索該文件的索引表，從第i項中得到所需盤塊號。
索引文件除了具備鏈接文件的優點外，還克服了它的缺點。它可以方便地進行隨機存取，但是這種組織形式會增加索引錶帶來的空間開銷。如果這些表格僅放在磁盤上，那麼，在存取文件時，首先要取出索引表，然後才能查表，得到盤塊號。這樣，至少增加一次訪問磁盤的操作，從而降低了存取文件的速度，加重了I/O負擔。有一種改進辦法是：把索引表部分或全部放入內存。這是以內存空間代價來換取存取速度的方法。
4．多重索引文件
為了用戶使用方便，系統一般不應限制文件的大小。如果文件很大，那麼不僅存放文件信息需要大量盤塊，而且相應的索引表也必然很大。例如，盤塊大小為1 KB，長度為100 KB的文件就需要100個盤塊，索引表至少包含100項；若文件大小為1 000 KB，則相應索引表項要有1 000項。設盤塊號用4個字節表示，則該索引表至少佔用4 000 B（約4 KB）。很顯然，在這種情況下，把整個索引表放在內存是不合適的，而且不同文件的大小也不同，文件在使用過程中很可能需要擴充空間。
單一索引表結構無法滿足靈活性和節省內存的要求，為此引出多重索引結構（又稱多級索引結構）。在這種結構中採用間接索引方式，即最初由索引項中得到某個盤塊號，該塊中存放的信息是另一組盤塊號；而後者每一塊中又可存放下一組盤塊號（或者是文件本身信息），這樣間接幾級（通常為1～3級），最末尾的盤塊中存放的信息一定是文件內容。例如，UNIX/Linux的文件系統就採用多重索引的方式。左部是索引節點，其中含有對應文件的狀態和管理信息。一個打開文件的索引節點放在系統內存區，與文件存放位置有關的索引信息是索引節點的一個組成部分。它是由直接指針、一級間接指針、二級間接指針和三級間接指針構成的數組。
前12項作為直接指針。直接指針所指向的盤塊中放有該文件的數據，這種盤塊稱為直接塊。一級間接指針所指向的盤塊（間接塊）中放有直接塊的塊號表。如果盤塊的容量為1KB，每個盤塊號用4個字節表示，那麼該塊號表中可以存放256個盤塊號。為了通過間接塊存放文件數據，核心必須先讀出間接塊，找到相應的直接塊項，然後從直接塊中讀取數據。二級間接指針所指向的盤塊中放有一級間接塊號表（可以有256項）。同樣，三級間接指針所指向的盤塊中放有二級間接塊號表（可以有256項）。
因此，對於一般的小型文件來說，若其大小不超過12KB，則可以利用前12個直接指針立即得到存放該文件的盤塊號。對於大於12KB且小於268KB的中型文件來說，其超出12KB的部分要採用一級間接索引形式存放。對於大於268KB且小於（12+256+2562）=65 804KB的大型文件來說，其超出268KB的部分要用二級間接索引形式。以此類推，對於巨型文件要採用三級間接索引形式，最大的文件可以達到16GB。
這種方法具有一般索引文件的優點，但也存在著間接索引需要多次訪盤而影響速度的缺點。由於UNIX/Linux分時環境中多數文件都較小，這就減弱了其缺點所造成的不利影響。
