Free-Space List Variants

List-based free-space management 用某種 list-like structure 保存 free blocks / ranges。

Linked Free List

所有 free blocks 串成 linked list，file system 保存 head。

free list head → free block 2 → free block 3 → free block 8 → more free blocks

取單一 block 很快；但找大量 blocks 或 contiguous blocks 可能要 traversal，HDD 上 random I/O 很貴。

第一個 free block 內保存多個 free block addresses，最後一格指向下一組。

free block A contains: [B, C, D, more addresses, next_group]

一次讀到多個 free block numbers，比逐一追 list 快；但仍不擅長找長 contiguous range。

把連續 free range 表成：

(start block, count)

適合 extent-style allocation；需要處理 split、merge，常搭配 tree。