Slotted Page Layout

假設你在 PostgreSQL 裡面有一張學生資料表：

CREATE TABLE students (
    student_id  CHAR(7),        -- 固定 7 字元，如 '1131456'
    name        VARCHAR(50),    -- 最長 50 字元，實際長度不定
    department  VARCHAR(30)     -- 最長 30 字元，實際長度不定
);

student_id 是 CHAR(7)，固定長度。如果整張 table 的每個欄位都是固定長度，事情就很簡單：每筆 record 大小一樣，你只要把一個 page 切成等大的格子，像 array 一樣用 index 乘以 record size 就能算出任何一筆 record 的位置。

但 name 和 department 是 VARCHAR，長度不固定。'Nini' 佔 4 bytes，'Capoo' 佔 5 bytes，'CS' 佔 2 bytes，'PHYS' 佔 4 bytes。每筆 record 大小不同，你沒辦法用簡單的 array indexing 來定位了。更麻煩的是，這些 record 要塞進一個固定大小（例如 8 KB）的 disk page 裡面，而且你還需要能刪除、更新、回收空間，外部持有的 pointer 不能因為 page 內部搬移而失效。

這就是 slotted page layout 要解決的問題。它是幾乎所有 disk-based database 在 page 層級的標準做法，從教科書到 PostgreSQL、MySQL InnoDB、SQLite，都是同一個核心思路。連檔案系統 (btrfs) 也是這樣設計!!

三層結構：Header、Slot Array、Heap Area

一個 slotted page 把固定大小的空間（例如 8 KB）切成三個區域，兩個區域從兩端朝著彼此成長，中間的空隙就是剩餘可用空間。(老師，撞在一起怎麼辦？)

最前面是 page header，佔固定大小，記錄這個 page 的 metadata。接著是 slot array（也叫 line pointer array），從 header 之後往後成長，每個 slot 是一組 (offset, length)，指向 page 裡某筆 record 的實際位置。最後面是 heap area，record 資料從 page 尾端往前堆疊。

Header 裡面最重要的兩個欄位是 free-space pointer：一個指向 slot array 的末端（下一個 slot 要放的位置），另一個指向 heap area 的前端（下一筆 record 要放的位置）。當這兩個 pointer 撞在一起，page 就滿了。

以 PostgreSQL 為例 (就一個栗子而已，不用背喔！)，它的 page header（叫 PageHeaderData）佔 24 bytes，裡面裝：

• pd_lsn（8 bytes）：最後一筆修改這個 page 的 WAL record 的 LSN，用於 crash recovery
• pd_checksum（2 bytes）：page 層級的 checksum，防止 bit rot
• pd_lower（2 bytes）：指向 free space 的起始位置（slot array 末端）
• pd_upper（2 bytes）：指向 free space 的結束位置（heap area 前端）
• pd_special（2 bytes）：指向 special space 的起始位置，給 index page 用的（普通 heap page 沒有 special space）
• 其餘欄位記錄 page size、版本、flags 等

每個 slot（PostgreSQL 叫 ItemIdData）佔 4 bytes，記錄對應 record 的 byte offset 和長度。所以一個 8192 bytes 的 page，扣掉 24 bytes header，理論上最多能放 (8192 - 24) / 4 = 2042 個 slot，當然實際上 record 本身也要佔空間，所以不可能到這個上限。

Slot Indirection：穩定的 Record 地址

這層 slot array 的存在不只是為了「找到 record 在哪」，更重要的是提供一層 indirection。

外部要引用某筆 record 的時候，用的是 (page ID, slot number) 這個組合。PostgreSQL 把它叫做 CTID（Current Tuple ID），格式是 (blockNumber, itemIndex)。這個 identifier 是穩定的：只要 record 還在同一個 page 裡，不管它在 page 內部被搬到哪個位置，slot number 都不會變，只是 slot 裡面記錄的 offset 會更新。

這很重要喔！因為 B+Tree 的 leaf node 裡存的就是這種 (page ID, slot number) 的 pointer。如果沒有 slot indirection，page 內部做任何 record 搬移（例如 compaction），都要回去更新所有指向這些 record 的 index entry，成本極高。有了 indirection，page 內部搬移 record 只需要更新自己的 slot array，外部的 pointer 完全不受影響。

Insert、Delete、Update 怎麼運作

Insert：在 slot array 末端新增一個 slot（pd_lower 往後推 4 bytes），在 heap area 前端放入 record 資料（pd_upper 往前推 record 長度）。如果 pd_lower 和 pd_upper 之間剩餘空間不夠，這個 page 就放不下了，需要去找別的 page 或申請新 page。

Delete：把對應 slot 標記為 "unused"（PostgreSQL 的做法是把 ItemIdData 的 length 設為 0），但 record 的資料不會立刻被清除，heap area 裡會留下一個 hole。這是因為立刻回收的成本太高，你得把後面的 record 往前搬，還要更新所有受影響的 slot。

Update：對 variable-length record 來說，update 可能改變 record 的大小。如果新的 record 比原來的大，原位放不下。所以很多系統的做法是把 update 當成 delete + insert：舊 record 標記刪除，新 record 插入到 heap area 的新位置，更新 slot 裡的 offset。PostgreSQL 更進一步，舊 record 不會立刻被刪掉。為什麼？因為可能有其他使用者正在讀取這筆資料的舊版本，如果馬上清掉，別人讀到一半就斷了。所以 PostgreSQL 會先留著舊 record，等到確定沒有人再需要它的時候，再由背景的清理程序（叫 VACUUM）統一回收空間。

Compaction：釋放洞洞

經過多次 delete 和 update 之後，heap area 裡面會出現很多 hole。總剩餘空間可能還很多，但沒有一段連續的空間夠大到塞得下新 record。這時候就需要 compaction（有些系統叫 defragmentation）：把 heap area 裡所有存活的 record 重新排列壓緊，把洞洞填滿、整併成一整塊連續的 free space。

Compaction 的好處在於：record 被搬移了，但 slot number 不變。Compaction 只需要更新每個 slot 裡面的 offset 值。所有外部用 (page ID, slot number) 引用這些 record 的 pointer 完全不受影響。這就是 slot indirection 設計最大的好處。

PostgreSQL 在什麼時候做 compaction 呢？當一個 page 的 free space 不夠放新的 record，但 page 裡有已經沒人需要的舊 record 時，PostgreSQL 會順手做一次 page pruning：把這些廢棄 record 清掉並壓縮 heap area，騰出空間給新 record。這個動作是在 INSERT 或 UPDATE 的時候順便觸發的，不用額外等背景清理。

超適合 Variable-Length Record

如果所有 record 長度都一樣（fixed-length），其實不需要 slotted page 這麼複雜的設計。你只要把 page 切成等大的 slot，用 slot number 乘以固定大小就能直接算出 offset，連 slot array 都省了。

但真實世界的資料幾乎都是 variable-length 的：VARCHAR 欄位、TEXT 欄位、nullable column（null 不佔空間 vs. 佔空間的差異）、甚至一張 table 經過 ALTER TABLE ADD COLUMN 之後新舊 row 的長度都不同。

Slotted page 不預設 record 有固定大小。代價是每筆 record 需要額外 4 bytes 的 slot 空間，而且存取 record 要先查 slot array 才能拿到實際位置（多一次 memory access）。對於 fixed-length record 的 workload，這個 overhead 是浪費，但對於 variable-length 的一般場景，這個設計的彈性遠超過 overhead 的代價。

PostgreSQL 的 heap record 本身就是 variable-length 的：每筆 record 有 23 bytes 的 header，接著是 null bitmap（每個 column 1 bit），最後才是實際的 user data。不同 record 的 column 數量和 null pattern 都可能不同，長度自然也不同。

PostgreSQL 的實作細節

PostgreSQL 的 heap page 是 slotted page 的教科書級實作。一個 8 KB page 的結構如下：

1. PageHeaderData（24 bytes）：pd_lsn、pd_checksum、pd_lower、pd_upper、pd_special 等
2. ItemIdData array：每個 4 bytes，從 byte 24 開始往後長
3. Free space：pd_lower 到 pd_upper 之間
4. Heap records：從 page 尾端往前長，每筆 record 包含 23 bytes header + null bitmap + user data
5. Special space：B-Tree index page 會用到（存 sibling page link），普通 heap page 不使用

一個具體的數字感受：假設平均 record 大小是 100 bytes（含 header），一個 8 KB page 扣掉 24 bytes page header，剩 8168 bytes。每筆 record 需要 100 bytes data + 4 bytes slot = 104 bytes。大約能放 8168 / 104 = 78 筆 record。如果 record 更大（例如 500 bytes），一個 page 只能放 8168 / 504 = 16 筆。

PostgreSQL 的 ItemIdData 一旦分配了 slot number，即使 record 被刪除，這個 slot 位置也不會被其他 record 搶走（除非做完整的 page 重建）。這是因為外部可能還有 index entry 或其他 record 的 CTID 指向這個 slot number，貿然重用會導致 dangling pointer。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

1. 為什麼 slotted page 要讓 slot array 和 heap area 從 page 的兩端相向成長，而不是把 slot array 和 record 資料放在一起、依序往同一個方向成長？

2. 假設一個 PostgreSQL 8 KB heap page，page header 佔 24 bytes，每個 slot 佔 4 bytes，平均 record 大小（含 record header）是 200 bytes。這個 page 最多能放幾筆 record？如果其中 20% 的 record 被 delete 但還沒被背景清理程序回收，實際可用的 free space 剩多少？

3. 一個 B+Tree leaf node 裡存了指向 heap page 的 CTID (42, 7)。如果 page 42 做了 compaction，把所有 record 重新排列壓緊，這個 CTID 還能正確找到目標 record 嗎？為什麼？

4. PostgreSQL 在 UPDATE 時不會立刻刪掉舊版本 record（因為可能有其他人還在讀）。從 slotted page 的角度，這對 page 內部的空間利用有什麼影響？為什麼需要一個背景清理程序來回收這些空間？

5. 在什麼樣的 workload 下，fixed-length record 的簡單 page layout 會比 slotted page 更有優勢？請從空間利用率和存取效率兩個角度分析。