檔案系統實作

檔案配置表(file allocation table,FAT)

/ fat /

鏈結配置把每個檔案的「下一區塊」指標藏在資料區塊裡,這使隨機存取又慢又脆。檔案配置表用一個漂亮的想法解決:把那些指標全部從資料區塊裡抽出來,集中到磁碟前段一個已知位置的單一張表中。這就是當年驅動 MS-DOS 的設計,至今仍活在每一支 USB 隨身碟和 SD 卡上。

這張表對磁碟上的每一個區塊(叢集)恰好有一個格子。每個格子存放的是「該區塊所屬檔案的下一個區塊號碼」——所以這張表本身就是那串指標,被抽出來變成一個陣列。某個檔案的目錄項目只記下它的第一個區塊號碼,比如 9。要讀這個檔案,你看表的第 9 格,它告訴你下一個是 16;你看第 16 格,說是 1;第 1 格說 25;第 25 格放著特殊的檔案結束標記。空閒區塊的格子放 0,所以同一張表也兼作可用空間圖。由於整張表可以快取在記憶體裡,你不必重讀資料區塊就能追蹤整條鏈,並能靠在 RAM 裡走這張表找到檔案的任何區塊——遠比純鏈結配置那種「在磁碟上逐塊跳」快得多。

FAT 的長處是簡單與近乎通用的支援,這正是它成為「必須能在每一種裝置上運作」的可攜媒體標準格式的原因。它的弱點在規模變大時浮現:表會隨磁碟一起變大、可能變得很龐大,而且找一個遠處的區塊仍得走過整條鏈(沒有真正的隨機存取),也沒有空間容納豐富的中繼資料、權限或當機復原的日誌。後來的版本(FAT12、FAT16、FAT32,以及相關的 exFAT)主要是把格子加寬,以定址更大的磁碟。

一張照片從叢集 9 開始。記憶體中的 FAT 讀到:slot[9]=16、slot[16]=1、slot[1]=25、slot[25]=EOF。作業系統完全在快取的表裡追蹤 9 -> 16 -> 1 -> 25,然後才從磁碟讀那四個資料叢集——資料區塊本身完全不帶任何指標。

FAT 把每一個「下一區塊」指標都集中進一張可快取的表;資料區塊維持純資料。

FAT 是被整理過的鏈結配置,不是另一個家族——快取整張表加速了走鏈,但要找遠處的區塊仍得走過整條鏈,並非常數時間查找。

又称
FATFAT12FAT16FAT32