儲存引擎與頁面佈局

為什麼要先懂磁碟

資料庫是「以磁碟為導向（disk-oriented）」的系統：資料的主要住所是非揮發性儲存裝置， 記憶體只是暫存。因此所有資料結構的設計目標都是減少磁碟 I/O 次數，而非減少 CPU 指令數。 要理解這一點，先看各層儲存的延遲差距：

HDD、SSD 與 NVMe

• HDD：機械臂移動（seek，約 4–10 ms）加上碟片旋轉等待，隨機 I/O 每秒只有約 100–200 次（IOPS）， 但循序讀寫可達 100–250 MB/s。「隨機比循序慢兩個數量級」是傳統 B+Tree、WAL、循序掃描設計的根源。

• SATA SSD：無機械部件，隨機讀 IOPS 達數萬；但 NAND flash 的寫入必須先抹除（以較大的 block 為單位）， 造成寫入放大（write amplification）與磨損；FTL（flash translation layer）在內部做了類似 LSM 的日誌式寫入。

• NVMe SSD：走 PCIe 通道、多達 64K 個佇列，隨機 IOPS 達數十萬到百萬，延遲降到 10 \(\mu\)s 等級。 隨機與循序的差距縮小到數倍，使得 等成本參數需要重新調整（第 6 章）。

區塊與頁面

作業系統以區塊（block）（通常 4 KB）為單位與儲存裝置溝通；資料庫在其上定義自己的頁面（page）：

頁面是三件事的共同單位：磁碟 I/O 的單位、緩衝池配置的單位（第 4 章）、 鎖定與 WAL 記錄定址的單位（第 8 章）。頁面太小會讓 B+Tree 變高、標頭開銷比例上升； 太大則浪費記憶體與 I/O 頻寬在不需要的資料上，也增加寫入放大。

檔案組織：Heap File

資料庫把一張表存成一個或多個檔案，檔案由頁面組成。最常見的組織是 heap file： 頁面之間沒有順序，一筆記錄可以放在任何有空間的頁面。相對的還有依鍵排序的 sorted file （更新代價高，實務上以叢集索引取代）與以雜湊分桶的 hashed file。

要在 heap file 中快速找到「哪一頁還有空間」，有兩種作法：

1. 頁面鏈結串列：標頭頁維護「有空間的頁面」與「已滿頁面」兩條串列，找空間可能需要走訪多頁。

2. 頁面目錄（page directory）：專門的目錄頁記錄每個資料頁的可用空間——PostgreSQL 的 Free Space Map 即屬此類。

SELECT pg_relation_filepath('employees');          -- base/16384/16399
SELECT pg_relation_size('employees', 'main'),
       pg_relation_size('employees', 'fsm'),
       pg_relation_size('employees', 'vm');

頁面佈局：Slotted Page

資料庫頁面幾乎都採用 slotted page（又稱 slot array 或 line pointer array）佈局：

• 標頭記錄頁面的元資料：可用空間的起訖位移、校驗和、最後修改此頁的 WAL 位置（LSN）等。

• slot 陣列從頁首向後成長，每個 slot 存放一筆記錄的（位移、長度、狀態）。

• 記錄從頁尾向前成長。兩者中間就是可用空間，當 追上 頁面就滿了。

記錄佈局

一筆記錄在頁面內的典型結構為：記錄標頭 \(\to\) NULL 位元圖 \(\to\) 對齊填補 \(\to\) 欄位資料。

• 定長欄位（、、）直接依型別長度存放。

• 變長欄位（、、、）以長度前綴（PostgreSQL 稱 varlena 標頭，1 或 4 bytes）帶出實際內容。

• NULL 不佔資料空間，只在 NULL 位元圖中設一個 bit；若整列沒有 NULL，位元圖可以省略。

• 對齊：為了讓 CPU 直接讀取，8-byte 型別通常要對齊到 8 的倍數（PostgreSQL 的 ）， 因此欄位順序會影響填補量—— 比 多浪費 14 bytes。

typedef struct HeapTupleFields {
    TransactionId t_xmin;        /* 插入此版本的交易 ID */
    TransactionId t_xmax;        /* 刪除或鎖定此版本的交易 ID（0 表示仍有效） */
    union {
        CommandId     t_cid;     /* 交易內的命令序號 */
        TransactionId t_xvac;    /* 舊式 VACUUM FULL 使用 */
    } t_field3;
} HeapTupleFields;

struct HeapTupleHeaderData {
    union { HeapTupleFields t_heap; DatumTupleFields t_datum; } t_choice;
    ItemPointerData t_ctid;      /* 此版本或更新版本的 TID (block, offset) */
    uint16  t_infomask2;         /* 欄位數 + 旗標 */
    uint16  t_infomask;          /* 旗標：有 NULL、有變長欄、xmin/xmax 已提交提示位元… */
    uint8   t_hoff;              /* 使用者資料起始位移（含 NULL 位元圖與對齊） */
    /* ^ 以上固定 23 bytes ^ */
    bits8   t_bits[FLEXIBLE_ARRAY_MEMBER];   /* NULL 位元圖（變長） */
    /* 之後接欄位資料 */
};

標頭中的 、、 正是 MVCC（第 9 章）的基礎——PostgreSQL 把版本資訊直接放在每一列裡， 這是它與 InnoDB（版本放在 undo log）最根本的差異之一。

可用空間管理與插入流程

當執行 時，儲存引擎需要回答「這筆記錄該放哪一頁？」：

PostgreSQL 的 （）流程：

1. 先試上次插入的那一頁（有空間的機率高，且維持局部性）。

2. 否則查 FSM 找一頁可用空間 \(\geq\) tuple 長度（加上 預留的空間）。

3. 找不到就延伸檔案一頁（並在 FSM 登記）。

4. 透過緩衝池取得頁面並加排他鎖，呼叫 寫入 slot 與資料，更新 /。

5. 把頁面標為 dirty，寫出 WAL 記錄（），把頁面的 設為該記錄的 LSN。

6. 此時資料頁還在記憶體；它會在 checkpoint、background writer 或緩衝池淘汰時才真正寫回磁碟（第 4、8 章）。

其他儲存模型：NSM、DSM 與 PAX

本章描述的「一列的所有欄位連續存放」稱為 NSM（N-ary Storage Model，列式）。 另外兩種模型會在第 13 章深入：

• DSM（Decomposition Storage Model，行式）：每個欄位獨立成檔，OLAP 掃描只讀需要的欄位。

• PAX（Partition Attributes Across，Ailamaki et al. 2001）：頁面層級仍是列式（一頁內含整列）， 但頁內依欄位分組存放（mini-page），兼顧 I/O 局部性與 CPU 快取效率。Parquet、ORC 的 row group 正是這種思路。

動手觀察：pageinspect

CREATE TABLE t (id int, name text);
INSERT INTO t SELECT g, 'name_' || g FROM generate_series(1, 5) g;

-- 頁面標頭
SELECT lsn, checksum, flags, lower, upper, special, pagesize, version, prune_xid
FROM   page_header(get_raw_page('t', 0));
--   lsn    | lower | upper | special | pagesize
-- 0/1A3F2B8|   44  |  8032 |  8192   |  8192      -- 24 B 標頭 + 5 個 4 B slot = 44

-- 每個 slot 與 tuple 標頭
SELECT lp, lp_off, lp_len, t_xmin, t_xmax, t_ctid, t_infomask2, t_hoff
FROM   heap_page_items(get_raw_page('t', 0));
--  lp | lp_off | lp_len | t_xmin | t_xmax | t_ctid | t_hoff
--   1 |   8160 |     32 |   7421 |      0 | (0,1)  |   24
--   2 |   8128 |     32 |   7421 |      0 | (0,2)  |   24

-- 每一列的實體位置 (block, slot)
SELECT ctid, * FROM t;

觀察重點：tuple 從 8160 往前排（ 遞減）；=24 表示 23 bytes 標頭對齊到 24； 指向自己，表示這是最新版本。執行一次 再查， 會看到舊版本的 被填上、 指向新版本的 slot——這就是第 9 章的起點。