每個檔案底下的記帳難題
在上一篇導覽裡，你把索引節點撬開來看：那是一筆磁碟上的小紀錄，存著一個檔案的中繼資料——大小、擁有者、權限、時間戳——以及，最關鍵的，一組指向真正裝著檔案位元組之資料區塊的指標。當時我們對那些指標一筆帶過。這篇導覽，要談的就是它們究竟指向什麼。記得嗎，磁碟不過是一個長長的、扁平的固定大小區塊陣列，從 0、1、2 一路編號上去；一個 30 KB 的檔案，若用 4 KB 的區塊來存，就需要八塊。問題看似簡單：是哪八塊？而索引節點又如何記住它們？
我們把這稱作配置問題（allocation problem），並留意它正是你在記憶體那一階已經見過的問題在檔案系統裡的雙胞胎。在那裡，作業系統得把行程安置進實體 RAM，而你看過外部破碎的痛苦：可用空間被打散成一個個沒用的小縫。同一個幽靈，也在磁碟上作祟。一種配置方法，就只是一套「把區塊指派給檔案、並把這份指派記下來」的策略，而如同本課程裡每一個設計，它是一組取捨——在「循序讀有多快」「跳到中間有多快」「記帳本身浪費多少空間」與「磁碟在數月使用後破碎得多嚴重」之間權衡。
連續式：一段不間斷的延伸
最簡單的想法，也是最像人會想到的想法：把整個檔案存在一段不間斷、一塊接一塊的區塊裡。這就是連續配置，就跟你把一張專輯的曲目一首接一首鋪在錄音帶上一模一樣——並排、依序。索引節點現在幾乎什麼都不必記：只要記住起始區塊號碼，以及長度（共幾塊）。一個位在第 200 到第 207 塊的檔案，記成「起始 200、長度 8」。這就是整張地圖。這跟記憶體那一階的基底暫存器與界限暫存器是同一個點子：一個起點加一段跨距，就把一個連續區域完整地描述了。
在轉動式磁碟上，回報好得不得了。循序讀達到硬體允許的極限速度——磁臂只尋軌一次到第 200 塊，接著就一路串流，因為第 201 塊就在隔壁。而隨機存取也輕而易舉：檔案的第 i 塊就是「起始加 i」，一次加法而已，所以跳到中間不必多跳幾步。對於那種把檔案從頭讀到尾的工作，比如串流一段影片，連續配置基本上無可匹敵。這也是為什麼它今天仍存活於像 CD-ROM 與某些媒體格式之中——那裡的檔案寫一次、依序讀。
但兩個殘酷的問題，讓它作為一種通用方案沉了船。第一個，正是記憶體那一階的老毛病：外部破碎。隨著檔案被建立、被刪除，可用空間碎裂成一塊塊小洞拼湊的圖案。你也許總共有 100 塊空閒，卻湊不出連續的 20 塊——於是一個 20 塊的檔案放不進去，明明空間是夠的。第二個問題是成長：一個把它分到的那段填滿的檔案，無處可擴張，因為它隔壁的區塊早已屬於別人。你得把整個檔案複製到別處才能讓它變大——很痛，而你建立檔案時，往往根本不知道它最終會多大。
鏈結式：一場橫越磁碟的尋寶
如果「堅持要一段不間斷」是陷阱，那就把這份堅持丟掉。在鏈結配置裡，一個檔案的各個區塊可以散落在磁碟的任何地方，而每一塊都帶著一個小小的指標，指向鏈中的下一塊。索引節點只存第一塊的位址；那一塊的結尾放第二塊的位址；如此下去，直到最後一塊，它的「下一個」指標是一個特別的「檔案結束」標記。這是一場尋寶：每條線索告訴你下一條線索藏在哪。外部破碎完全消失——任何地方的任何空閒區塊都行得通——而檔案要成長，只要再抓一塊空閒區塊、把它鏈上去就好。
代價高昂，且全落在隨機存取上。要讀第 5000 塊，你別無選擇，只能從頭順著鏈走——讀第 1 塊才知道第 2 塊在哪、讀第 2 塊才知道第 3 塊在哪，整整 4999 跳，每一跳都是一次全新的磁碟存取，還可能尋軌到天涯海角。沒有算術捷徑能直達中間，因為唯一記著「第 5000 塊在哪」的地方，就是第 4999 塊本身。連純粹的循序讀也受害：因為各區塊實體上可在任何地方，磁臂幾乎每讀一次就得尋軌一次，把尋軌時間一付再付，而不是一路串流。
還有一道更微妙的傷。指標偷走了每個資料區塊內部的空間。如果一個 4 KB 的區塊得花 4 個位元組放「下一個」指標，那麼檔案的資料就不再對齊漂亮的 2 的次方，而一個想讀乾淨 4 KB 的應用程式，現在就會橫跨區塊邊界。經典的修法，是把每一個指標都從資料區塊裡抽出來、集中成一張大表——這就直接通往這個家族裡最有名的成員。
索引式：一塊區塊把它們全列出來
FAT 靠著把指標集中起來而改良了鏈結配置，但它是把整個磁碟區的指標集中成一張巨大的共用表。索引配置把這個點子再往前推一步，給每個檔案它自己私有的清單。挪出一塊區塊——稱為索引區塊（index block）——在裡頭填入一個依序排列的陣列，存著這個檔案各資料區塊的號碼：第 0 格放檔案第一塊的位址、第 1 格放第二塊，依此類推。索引節點指向這個索引區塊，索引區塊再指向所有的資料。把它想成課本最後面的索引，或記憶體那一階的分頁表：一份精簡的目錄，把一個邏輯位置直接對映到一個實體位置。
這把鏈結配置失去的一切都買了回來。隨機存取又快了：要找檔案的第 5000 塊，你讀它的索引區塊、直接看第 5000 格——一次查詢，不必走鏈。外部破碎依然不存在，因為資料區塊可以自由散落。而指標也不再汙染資料區塊；它們一起住在乾淨的索引區塊裡。你得到了鏈結式的大半彈性，加上連續式的大半直接——這正是為什麼真正的 Unix 風格檔案系統，就建立在這個方案之上。
CONTIGUOUS inode: start=200, len=8 -> blocks 200 201 202 ... 207 (in a row)
LINKED inode: first=200
200 -> 312 -> 41 -> 905 -> ... -> [EOF] (each block names the next)
INDEXED inode -> index block:
[ 0 ] = 200
[ 1 ] = 312
[ 2 ] = 41 data blocks scattered anywhere;
[ 3 ] = 905 slot i -> the file's i-th block
... (one lookup jumps to any block)索引配置藏起來的麻煩——以及 Unix 如何修補它
索引配置有一個尷尬、卻躲不掉的問題：索引區塊有多大？它本身不過是一塊磁碟區塊，所以只裝得下那麼多指標。如果一塊是 4 KB、每個指標 4 個位元組，一個索引區塊就裝 4096 / 4 = 1024 個指標，把檔案上限卡在 1024 塊——大約 4 MB。那遠遠太小了。但把索引區塊弄得超大，又會替絕大多數又小又迷你的檔案浪費空間：一張 2 KB 的便條，不該拖著一個半空的 4 KB 索引到處跑。我們需要一種結構，對小檔案維持便宜，卻又能擴展到巨大的檔案。
經典的 Unix 答案是多層索引（multilevel index），而它優美地務實。索引節點本身就握有少少幾個指標——譬如十二個直接（direct）指標，直截了當地點名資料區塊。一個很小的檔案，光靠這些就被完整描述，一塊額外的區塊都不必：立即、便宜、根本不用索引區塊。當檔案大到容不下它們，索引節點就伸手去拿一個間接區塊（indirect block）：一個指向「一整塊裝滿了指向資料之指標」的指標，就像一條索引條目能把你導到一個子索引。還要更多？一個雙重間接指標，瞄準的是「一塊裝著指向（裝著指向資料之指標的區塊）之指標的區塊」，而三重間接再加一層。
這正是這個方案的天才之處：該便宜的地方便宜，該有能耐的地方有能耐。小檔案——壓倒性的多數——一點間接的代價都不必付，因為它們的區塊就裝在索引節點裡頭的直接指標中。只有真正大的檔案，才爬進單重、雙重、三重間接的層級，而即便是三重間接的樹，也搆得到 TB 之譜。前一篇導覽允諾過索引節點握有指向資料的指標；現在你看得出，那些指標根本不是一張扁平的清單，而是一棵小樹，檔案要求多深，它就長多深。下一篇導覽，會把這些間接區塊完整地打開，並轉向記帳的另一半——一開始，到底怎麼追蹤哪些區塊是空閒的。