索引配置留下的漏洞
第 2 篇導覽以一個高潮作結。索引配置打敗了連續與鏈結兩種佈局：把一個檔案所有的區塊指標都收進一個索引區塊，你就得到快速的隨機存取（直接跳到第 n 個指標），既不必像 FAT 那樣掃描一張表，也沒有外部碎裂。但我們含糊帶過了一個本該一直困擾你的問題：那個索引區塊有多大？它就只是一個普通的磁碟區塊——譬如一個 4 KB 的區塊。如果每個指標是 4 個位元組，一個索引區塊裝得下 4096 / 4 = 1024 個指標。在 4 KB 的區塊大小下，這把一個檔案上限卡在 1024 * 4 KB = 4 MB。一張現代手機拍的照片就能輕鬆衝破它。
你或許會聳聳肩說：那就用一個更大的索引區塊嘛。但那只是把一種浪費換成另一種。真實磁碟上大多數檔案都很小——幾 KB 的設定檔、一支短小的腳本、一張縮圖。如果每個檔案一開始都得替一個巨大的索引區塊付費，你就會在幾近全空的指標陣列上燒掉龐大的空間。我們要的恰恰相反：小檔案應該幾乎不花成本，但一個巨大的檔案仍然必須能被觸及。這正是 Unix 索引節點所解開的張力，而這個解法正是這篇導覽的核心。
多層索引：先直接，再間接，然後更間接
訣竅在這裡，而且它是真正的優美。索引節點裡裝的不是一種指標，而是一架分級的階梯，稱為多層索引。索引節點裡頭幾個指標——譬如十二個——是直接指標：每一個都直接指名檔案的一個資料區塊。對一個小檔案而言，故事到此為止。一個 30 KB 的檔案裝進八個 4 KB 區塊，全都由直接指標觸及，沒有任何額外的讀取。最常見的情況——一個小檔案——除了索引節點本身之外不花一分錢。
當一個檔案長過那十二個直接區塊，索引節點就伸手去拿它的下一個指標：單層間接指標。這一個並不指向一個資料區塊——它指向一個間接區塊，也就是一整個塞滿了另外 1024 個資料區塊指標的磁碟區塊。所以光是這個單層間接指標就多加了 1024 個區塊、也就是另外 4 MB 的觸及範圍。代價是多一次磁碟讀取：要找到第 100 個資料區塊，作業系統先讀那個間接區塊，再讀它所指向的資料區塊。索引節點維持小巧；容量只在檔案真正需要時才付費。
現在把這個點子往上重複一層。雙層間接指標指向一個裝著 1024 個指標的區塊，但其中每一個又各自指向另一個裝著 1024 個資料指標的間接區塊——所以它涵蓋 1024 * 1024 ≈ 一百萬個區塊（約 4 GB）。而三層間接指標再加一層：1024 * 1024 * 1024 ≈ 十億個區塊，進到了 TB 等級。透過三層觸及一個區塊要付三次額外讀取（每層一次）外加那次資料讀取，但你只在一個龐大檔案最深處的範圍才付這個代價。這架階梯就是整個設計：對佔多數的小檔案而言淺而免費，對罕見的巨人而言深卻仍能觸及。
inode +-----------------------------+ | metadata (size, perms, ...) | | direct[0] --------------------> data block | direct[1] --------------------> data block | ... (12 direct pointers) ... | direct[11] --------------------> data block | | | single indirect ---> [ 1024 ptrs ] --> 1024 data blocks | | | double indirect ---> [ 1024 ptrs ] --> each --> [ 1024 ptrs ] --> data | | | triple indirect ---> [ 1024 ptrs ] --> [ 1024 ] --> [ 1024 ] --> data +-----------------------------+ Reach (4 KB block, 4-byte ptr, 1024 ptrs/block): 12 direct = 12 blocks (48 KB) 0 extra reads single indirect = 1024 blocks (4 MB) 1 extra read double indirect = 1024^2 blocks (4 GB) 2 extra reads triple indirect = 1024^3 blocks (4 TB) 3 extra reads
把一個邏輯偏移量沿階梯走下去
當你追蹤一次存取時，這個機制就變得具體。假設一支程式對一個檔案呼叫 read，想要位於偏移量 8 MB 處的位元組。檔案系統在放置資料時從不以位元組為單位——它以固定大小的區塊為單位，很像分頁把一個位址拆成分頁編號與偏移量。所以第一步是把這個位元組偏移量轉成一個邏輯區塊編號：在 4 KB 區塊下，區塊編號 = floor(8 MB / 4 KB) = 2048，而那個位元組落在該區塊內的偏移量 0 處。如今唯一的問題是：邏輯區塊 2048 在磁碟上的哪裡？而這正是那架階梯所回答的。
- 區塊編號小於 12 嗎？不（2048 不是），所以它不是直接指標。減掉那 12 個直接區塊：2048 - 12 = 2036。
- 它裝得進單層間接區塊那 1024 個指標裡嗎？2036 比 1024 大，所以不行。減掉 1024：2036 - 1024 = 1012。這個區塊住在雙層間接指標底下。
- 讀那個雙層間接區塊。在它裡頭以 1012 / 1024 = 0 索引，挑出正確的第二層間接區塊，接著讀那個第二層區塊、在其中以 1012 mod 1024 = 1012 索引，取得最終的資料區塊指標。
- 讀那個資料區塊。這次存取的磁碟讀取總數：雙層間接區塊、第二層間接區塊，然後是資料——兩次額外讀取，恰恰是雙層所預測的代價。
另一半：誰來管那張自由清單？
到目前為止，我們只問過一個檔案如何找到它已經擁有的區塊。但每當一個檔案長大，索引節點就需要從某處要一個全新的資料區塊；而當一個檔案被刪除，它的區塊必須回到流通之中。這份簿記就是自由空間管理，它和那架階梯一樣不可或缺。弄錯了，你不是發出一個已經在使用中的區塊（毀損），就是漏掉一些誰也再回收不了的區塊（緩慢、無聲的容量流失）。檔案系統需要對一個問題有一個可靠的答案：這顆磁碟上，現在哪些區塊是空的？
主流的答案是自由空間點陣圖。想像一長排的位元，磁碟上每個區塊對應一個位元：1 表示「已配置、使用中」，0 表示「空閒、可用」（確切的慣例各有不同，但概念是對稱的）。一顆 100 GB、4 KB 區塊的磁碟約有兩千六百萬個區塊，所以它的點陣圖約是兩千六百萬個位元——大約 3 MB，相對於磁碟大小不過是個捨入誤差。配置一個區塊就是「找一個 0、把它翻成 1」；刪除時釋放一個區塊就是「把它的位元翻回 0」。正因為點陣圖如此精簡，檔案系統可以把它大部分留在記憶體裡，讓配置決策很快。
點陣圖悄悄替你帶來一個鏈結式自由清單給不了的紅利：區域性。要把一個檔案的區塊放在彼此附近（這讓日後在會旋轉的磁碟上做循序讀取更快），配置器可以掃描點陣圖、找出一連串連續的 0 位元，把它們當作一整塊連續區域抓下來。相較之下，一條由自由區塊構成的鏈結清單，是依它們被釋放時那種散亂的順序發出去的，沒有簡單的辦法去問「這些鄰居也是空的嗎？」這正是為什麼像 ext 家族那樣的真實系統，伸手去拿的是點陣圖，而不是自由清單。
誠實的極限與一條往前的連結
誠實面對這架階梯是什麼、又不是什麼。它與其說是一個聰明的新點子，不如說是把分頁表的訣竅套用到磁碟上：一棵由指標區塊構成的樹，對小東西維持淺、只在有需求時才加深——和記憶體那邊的階層式分頁表是同一個形狀。而它有實在的代價：一個碎裂的巨大檔案、在它最深處被存取時，真的會付那些額外讀取，而間接區塊本身也會吃掉磁碟空間（每 1024 個資料區塊就要一個間接區塊）。這是一個審慎的取捨，不是免費的午餐。它的高明之處只在於：最常見的情況——小檔案——什麼也不必付。
再一個告誡，因為它真的會咬到真實系統。點陣圖與索引節點的指標是同一個真相的兩種視角——一個在點陣圖裡被標成「1」的區塊，應該恰好能從一個索引節點觸及（或者是中介資料）。當機之後，這兩種視角可能彼此矛盾：索引節點或許已經抓了一個區塊，而點陣圖的更新還在半路上。那種不一致，正是檔案系統檢查器（fsck）所要獵捕的，也是本階最後一篇導覽用日誌機制更優雅地解決的問題。把這條線記在心裡：這裡的這些結構，只有在每一次更新都一致落地的前提下才是正確的。