多層索引(multilevel index)
單一索引區塊就像一頁位址表:對小檔案綽綽有餘,但碰到巨大的檔案就裝不下了。經典的 Unix 索引節點用一個巧妙的混合方案解決這問題,它對常見情況(多數檔案都很小)很慷慨,卻仍能定址極大的檔案。它在索引節點裡直接保留幾個直接指標,再為罕見的巨大檔案加上一道間接的階梯。
索引節點裡放著比如 12 個直接指標,每個指名檔案的一個資料區塊。對於塞得進 12 個區塊的檔案,故事就此結束——很快,而且讀進索引節點的那一刻,區塊位址就已在記憶體裡。若檔案更大,索引節點的下一個指標是「單層間接指標」:它指向一個本身裝滿「資料區塊指標」的區塊。再大,「雙層間接指標」指向一個區塊,裡面是指向「指標區塊」的指標,那些指標再指向資料。還有一個,「三層間接指標」加上第三層。所以小檔案不需任何額外成本,大檔案則付出一、二或三次額外的區塊讀取才到得了它遙遠的區域——你只為你實際用到的深度付費。
這算式很驚人。若 4 KB 的區塊各能裝 1024 個指標(一個指標 4 位元組),12 個直接指標涵蓋 48 KB;單層間接再加 1024 個區塊(4 MB);雙層間接再加 1024 x 1024 個區塊(4 GB);三層間接再加 1024^3 個區塊(4 TB)。這就是一個小而固定大小的索引節點,如何能描述從 1 個位元組到數 TB 的檔案。代價是,要深入一個非常大的檔案,光是取得指標就可能需要多達三次額外讀取——不過在實務上,快取那些間接區塊隱藏了大部分成本。
某索引節點有 12 個直接 + 1 個單層 + 1 個雙層 + 1 個三層指標。要讀 4 KB 區塊檔案的第 100,000 個位元組偏移:那是邏輯區塊 24,超過了 12 個直接指標(0-11),所以落在單層間接區。作業系統讀那個單層間接區塊,取其第 24-12 = 12 個項目,就得到資料區塊——多一次讀取。
小檔案用直接指標,再以一/二/三層間接逐步解鎖越來越大的檔案。
這個方案刻意是不對稱的:小檔案(絕大多數)不付任何代價,只有真正巨大的檔案才付出額外的間接讀取。並不是每次存取都慢——只有深入時才慢。