頁面佈局與分槽頁面 (Page Layout & Slotted Pages)

• 最原始的佈局：一頁就是 (key, value, child pointer) 三元組的串接。
• 兩個致命傷：非最右端插入時得整批搬移後面的元素；而且無法高效處理變長記錄。
• 變長記錄真正的難題是空閒空間管理：把大小 n 的新記錄塞進原本 m 的空位，除非剛好 m == n，否則不是塞不下就是留下用不掉的零頭。

• 一頁拆成三塊，指標與資料從兩端相向生長：

┌──────────┬──────────────────────────────────────────┐
│  header  │→ cell 指標(offset) 陣列  ...   free ...  ←│ cell₂ │ cell₁ │ cell₀
└──────────┴──────────────────────────────────────────┘
   固定大小         由左向右長          中間空位     由右端向左追加

• header（固定大小）存這一頁與 cell 的關鍵資訊；cell 大小不一，存 key、指標或資料記錄；cell 指標陣列存每個 cell 的 offset。
• 這個佈局一次滿足三項需求：以最小開銷（只多存一個指標陣列）放變長記錄、能回收刪掉的空間、外部不需知道確切位置就能參照記錄。

• 頁面外部只用 slot ID 參照一筆記錄，「它實際躺在頁內哪個 offset」是頁面內部的事。
• 好處：邏輯排序不靠搬動 cell，只靠對 offset 指標陣列按 key 排序來維護。插入時 cell 直接追加在 free space 邊界（工作量最小），只有那一小段 offset 指標需要右移騰位——插入、更新、刪除都不必搬動 cell 本身。

• 刪除不真的移除 cell，而是把它標記為已刪除，並在記憶體的可用性清單 (availability list) 記下釋放出的大小與位置（SQLite 稱這些空段為 freeblock，並在 header 存指向第一個 freeblock 的指標與可用位元組總量）。
• 插入時先查 availability list 有沒有合適空段：首次適配 (first fit) 拿第一個夠大的（可能留下太小的零頭）、最佳適配 (best fit) 挑剩餘最少的。
• 若連續空間不夠但碎片總量夠，就重整頁面 (defragment) 把 cell 壓實回收空間；重整後仍不夠才建溢位頁面 (overflow page)。

• 同一頁的 cell 假設是同質的（全是 key，或全是 key-value），描述 cell 的 metadata 只需在頁層級存一次。
• Key cell（非葉節點用）：| key_size | child_page_id | key bytes |——存的是指向子頁的 page ID。
• Key-value cell（葉節點用）：| flags | key_size | value_size | key bytes | data_record |——存的是資料記錄。
• 固定大小欄位放前、變長的 key / value 放後：定位 key＝跳過 header 讀 key_size 位元組；定位 value＝再跳過 key_size 讀 value_size 位元組。長度前綴讓變長資料也能 O(1) 定位（同 Pascal 字串「先長度、後資料」的思路）。

• 版本：儲存引擎通常要同時支援當前與舊版格式以維持向後相容。做法有把版本編進檔名前綴（Cassandra）、放獨立版本檔（PostgreSQL 的 PG_VERSION），或寫進索引檔 header、甚至用魔術數字 (magic number) 辨識。
• 校驗和：檔案可能因軟體 bug 或硬體故障損壞。通常對每一頁各算一份 checksum 放進該頁 header（而非整檔算一次），這樣損壞能被限制在單一頁面、也更精確。CRC 能抓連續多位元的突發錯誤 (burst error)；要防惡意竄改則需密碼學雜湊——CRC 只保證「非蓄意的偶發變更」沒發生。