Slotted Page Layout

在 Indexing 單元中，我們要理解 B+Tree 與 LSM-Tree 等 indexing 結構如何在磁碟上高效地組織資料。但在討論這些巨觀結構之前，我們需要先瞭解單一 disk page 內部的資料是怎麼擺放的。

Given 一個固定大小（例如 8 KB）的空白 page。我們要往裡面塞入多筆長度不一的 record，同時滿足三個需求：

1. 能快速找到任一筆 record
2. 刪除或更新 record 後能回收空間
3. 外部持有的 record 參照不會因為 page 內部的搬移而失效。

Slotted page 用一個三層結構同時解決了這三個問題：page header 記錄 page-level metadata（如 free-space offset、slot count），slot array 從 page 前端往後成長，每個 slot 是一組 (offset, length) 指向對應 record 的位置，而 record 資料（heap area）則從 page 尾端往前堆疊。一個向後長，一個向前長，中間的空隙就是可用空間。

這種資料結構，讓外部只需要記住「page ID + slot number」就能找到一筆 record，而 page 內部可以自由搬移 record（例如做 compaction 來消除 fragmentation），只要更新 slot array 中的 offset 即可。瞭解這個機制後，你會發現它在後續的 B+Tree leaf node、heap file、甚至 WAL record 中反覆出現。

💲大抄 貢獻 HackMD 共筆

Key Concepts

我理解 slotted page 的三層結構（header -> slot array -> heap area）以及兩個區域相向成長的空間配置方式

我理解 slot indirection 的設計動機：外部用 (page ID, slot number) 作為穩定的 record identifier，page 內部可以自由搬移 record 而不影響外部參照

我能解釋 insert、delete、update 三種操作如何改變 page 內部的狀態，以及為什麼 delete 不會立刻回收空間（留下 hole），需要 compaction 來整理

我能說明這個 page layout 為什麼天然適合 variable-length record，以及它與 fixed-length record 的 page layout 相比，在空間利用與存取效率上有什麼取捨

（延伸）我知道 PostgreSQL 的 heap page 採用類似的 slotted page 設計，能將課堂概念對應到真實系統的實作

Recommended Resources