Directory Implementation

Directory 是 file name → FCB / inode / MFT record 的 lookup table。資料結構會影響 pathname lookup、create/delete、ls 與 recovery。

Linear List

每個 entry 保存 file name 與 FCB identifier。Create 時線性搜尋確認無同名，再插入 entry；delete 時搜尋後把 entry 標成 unused、接到 free-entry list，或用最後一筆覆蓋。

優點：簡單、metadata 小、容易 recovery。
缺點：lookup O(n)；大型 directory 很慢。
若保持 sorted，可 binary search，但 insert/delete 要搬 entries。

Hash Table

用 file name hash 到 bucket，再找 bucket 內 entry。

file name → hash → bucket → directory entry

優點：lookup / insert / delete 通常比 linear list 快。
代價：collision handling、rehash、metadata 損壞時 recovery 較複雜。

小 directory 用 linear list 加 cache 通常夠；大型 source tree、maildir、package cache 常需要 hash/tree/indexed directory。