目錄實作（directory implementation）

從使用者那一側看，目錄不過是裝著一堆有名字的檔案的資料夾。但在底層，目錄其實是一張小表，把每個名稱對映到檔案的中繼資料——最常見的形式是存放（檔案名稱, 索引節點號碼）配對的清單，本身存在一個檔案裡。目錄實作要回答的問題是：怎麼存這張表，才能在資料夾裝著數千個項目時，查名稱依然快。

最單純的方案是線性清單：目錄就是一串項目，你從頭往下掃。查 holiday.jpg 就是拿它和每一個項目比對直到找到——對只有十個檔案的資料夾沒問題，對有五萬個檔案的就慢到痛苦，因為每次查找都是 O(n)，而且建立檔案前還得先掃過整張清單，確認名稱沒被占用。較好的方案是雜湊表：把名稱雜湊成一個索引，幾乎直接跳到該項目，提供大約 O(1) 的查找，不過需要小心處理碰撞，並在目錄變大時重新調整大小。現代檔案系統對大型目錄使用的方案是平衡樹，通常是 B 樹（或 B+ 樹），以名稱為鍵（常是名稱的雜湊值）：查找、插入、刪除全是 O(log n)，即使有數百萬個項目，樹仍很淺，所以幾次區塊讀取就能找到任何檔案。NTFS 把目錄項目存在 B 樹裡；ext3 與 ext4 在舊的線性清單之上加了 htree（一種類 B 樹的雜湊索引）。

取捨是熟悉的那一種：線性清單極其簡單、對小目錄很棒，而樹與雜湊索引付出額外的複雜度（以及索引在磁碟上的空間），以在目錄變得龐大時保持查找快速。不論用哪種結構，刪除檔案通常只是把它的目錄項目標記為空，而不是實際把清單壓縮，所以目錄可能帶著空格子，直到被清理。