B+ Tree 與 Hash Index：從 Page I/O 看懂索引怎麼選

索引的目的不是少做幾次 comparison，而是讓 query 少讀幾個 page。

B+ Tree 保留順序

                         [40 | 80]          root
                    /        |        \
          [10 20 30] -> [40 50 60] -> [80 90 100]
             leaf          leaf           leaf

Internal node 保存 separator key 與 child pointer；排序後的 index entry 位於 leaf，leaf 之間又互相連接。

Equality lookup 往下走到一個 leaf。Range lookup 先找到 lower bound，再沿 leaf link 讀到超過 upper bound。當排序方向吻合時，同一個順序也能服務 ORDER BY。

白話來說： Internal page 是導覽，leaf 是書架。Range query 找到第一本書後，只要沿書架往右走。

Fanout 讓樹保持很矮

課堂用 4,096-byte page、4-byte key 與 8-byte pointer 做簡化估算：

(2d × 4) + ((2d + 1) × 8) ≤ 4096
d ≈ 170

若預留更新空間，把平均 fanout 估成 133：

133³ ≈   2,352,637 entries
133⁴ ≈ 312,900,700 entries

這是量級估算，不是特定 engine 的精確公式。重點是一個 page 能在大量 child 之間選路，所以樹高成長很慢。

寫入必須維護樹

Leaf 滿了會 split，並把 separator 傳給 parent。Parent 也可能繼續 split；只有 root split 才會增加樹高。刪除後節點太空時，先向 sibling redistribution，無法借 key 才 merge。

因此每多一個 index，insert、update、delete 都多一份維護成本，也會多佔 cache。Read improvement 必須值得這些 write amplification。

Hash 放棄順序

Hash index 計算 h(key) 後直接前往 bucket。分布平均且沒有長 overflow chain 時，equality lookup 可以很有效率。但相鄰原值不一定在相鄰 bucket，所以 hash 無法自然服務 range 或有序輸出。

Static hashing 可能累積 overflow page；extensible hashing 透過 directory split；linear hashing 一次增加一個 bucket。它們改善成長方式，沒有恢復 key order。

白話來說： Hash 知道置物櫃號碼，卻不知道「42 到 90 的所有物品」分散在哪些相鄰位置。

自己驗證差異

CREATE TABLE events AS
SELECT g AS event_no,
       g % 1000 AS topic_id,
       DATE '2020-01-01' + (g % 1825) AS created_at
FROM generate_series(1, 1000000) AS g;

ANALYZE events;
CREATE INDEX events_no_btree ON events USING btree (event_no);

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no BETWEEN 420000 AND 430000;

再單獨測 hash：

DROP INDEX events_no_btree;
CREATE INDEX events_no_hash ON events USING hash (event_no);

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no = 424242;

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT * FROM events WHERE event_no BETWEEN 420000 AND 430000;

Hash 可以服務 equality，無法服務 range。若查詢要讀大部分 table，planner 仍可能正確選擇 sequential scan。

EXPLAIN 依這個順序讀

EXPLAIN ANALYZE 會執行 statement；對 write 使用時要特別小心。

複合索引跟著 query shape

Topic equality 加日期 range 可使用：

CREATE INDEX events_topic_date
ON events (topic_id, created_at);

第一欄先隔離一個 topic，第二欄再縮小其中的日期範圍。Column order 決定資料庫先縮小哪個搜尋空間。

複習卡

• B+ Tree 順序可服務 equality、range 與 sorting。
• Leaf link 讓 range 定位後改成 sequential traversal。
• Fanout 高，所以樹通常很矮。
• Split、redistribution、merge 是 write cost。
• Hash 服務 equality，不服務有序 range。
• Selectivity 低時 sequential scan 可能是正解。
• 用 actual rows 與 buffers 驗證，不只看一次時間。

資料來源

• CS 411 B+ Tree 與 Hash Tables 課堂內容。
• PostgreSQL index types
• PostgreSQL hash indexes