B-Tree、B+Tree 與索引

從二元搜尋樹到 B-Tree

在記憶體中，二元搜尋樹（BST）與其平衡版本（AVL、紅黑樹）是很好的有序索引。但一旦資料在磁碟上：

• 每個節點只有一個鍵，樹高 \(\log_2 N\)；\(N = 10^9\) 時高度約 30，意味著一次查詢可能要 30 次隨機 I/O。

• 節點很小（幾十 bytes），而 I/O 單位是 8 KB 的頁面——每次讀入一頁卻只用其中一個鍵，浪費 99%。

• 平衡操作（旋轉）牽動多個節點，每次都是額外的頁面寫入。

Bayer 與 McCreight 在 1972 年提出的 B-Tree 把「節點」放大成「一整個頁面」： 每個節點放數百個鍵，樹高降為 \(\log_f N\)（\(f\) 是扇出）。\(f = 400\)、\(N = 10^9\) 時高度只有 4。

B-Tree 與 B+Tree

• B-Tree：每個節點（含內部節點）都存放鍵與對應的值（或記錄指標）。查詢可能在內部節點就結束。

• B+Tree：內部節點只存分隔鍵（separator key）與子節點指標，所有值都在葉節點； 葉節點之間以雙向鏈結串起來。

B+Tree 的優勢使它成為事實標準（PostgreSQL、InnoDB、SQLite、Oracle、SQL Server 都是 B+Tree，即使文件稱之為 B-tree）：

1. 內部節點不存值，能塞更多分隔鍵，扇出更大、樹更矮。

2. 範圍掃描只需找到起點葉頁，然後沿兄弟鏈結走，不必回到上層。

3. 所有查詢路徑長度相同（都到葉），成本可預測。

4. 分隔鍵可以是截斷後的最短前綴（suffix truncation），進一步提高扇出。

節點結構、扇出與樹高

節點內容

• 內部節點：\(\langle p_0, k_1, p_1, k_2, p_2, \ldots, k_m, p_m \rangle\)。子樹 \(p_i\) 中所有鍵滿足 \(k_i \le key < k_{i+1}\)。

• 葉節點：\(\langle (k_1, v_1), (k_2, v_2), \ldots \rangle\) 加上左右兄弟指標。 值 \(v_i\) 依索引類型是 TID（PostgreSQL 的 secondary index）、主鍵值（InnoDB secondary index）或整列（叢集索引葉頁）。

• 節點本身就是第 2 章的 slotted page：鍵以 slot 排序，支援頁內二分搜尋。PostgreSQL 把兄弟頁號與層級放在 special space。

扇出與高度估算

以 PostgreSQL 的 8 KB 頁面、 鍵為例：每個索引項 = 8 bytes 索引 tuple 標頭（含 6 bytes TID） + 8 bytes 鍵 + 4 bytes slot \(\approx\) 20 bytes，扣掉頁標頭與 special space 後約可放 \(f \approx 400\) 項 （預設 fillfactor 90% 時約 360）。高度 \(h\) 與可索引筆數 \(N\) 的關係： \[N \approx f^{\,h} \quad\Longrightarrow\quad h = \lceil \log_f N \rceil\]

搜尋、插入、分裂、刪除與合併

搜尋

search(key):
  page = root
  while page 不是葉頁:
    i = 頁內二分搜尋，找最大的 i 使得 k_i <= key   （找不到則 i = 0）
    page = read(p_i)                             -- 透過緩衝池
  在葉頁二分搜尋 key，回傳對應的值（或「不存在」）
範圍掃描 [lo, hi]：search(lo) 到達葉頁後，沿右兄弟指標前進直到鍵 > hi

插入與分裂

1. 搜尋到應放入的葉頁 \(L\)。若 \(L\) 有空間，插入並維持排序即可（寫 1 頁）。

2. 若 \(L\) 已滿：配置新頁 \(L'\)，把 \(L\) 的鍵分成兩半（\(L\) 留前半、\(L'\) 放後半），把 \(L'\) 的最小鍵（或其截斷前綴） 作為新的分隔鍵插入父節點，並更新兄弟鏈結。

3. 父節點若也滿了，遞迴分裂；根分裂時樹高加一——這是 B+Tree 唯一會長高的方式，所以它永遠平衡。

分裂點的選擇很重要：單調遞增的鍵（如 、時間戳）若採 50/50 分裂，左半頁永遠不會再被填滿， 空間利用率只有 50%。PostgreSQL 偵測到「插入到最右葉頁」時改用約 90/10 的分裂（並有 fastpath 直接快取最右葉頁）， InnoDB 也有類似的循序插入最佳化。

刪除與合併

教科書演算法：刪除後若節點少於半滿，向兄弟借一個鍵（重新分配）或與兄弟合併並刪除父節點中的分隔鍵，必要時遞迴。

索引並行控制：Latch Crabbing 與 B-link Tree

多個執行緒同時讀寫同一棵樹時，需要latch（保護記憶體資料結構的短期鎖，與交易層級的 lock 不同，第 10 章）。

• Latch crabbing / coupling：由上而下，取得子節點 latch 後才釋放父節點 latch。寫入時若子節點「安全」 （插入不會滿、刪除不會半空）就可釋放所有祖先的 latch。缺點是根節點成為熱點。

• 樂觀 crabbing：先假設葉頁不會分裂，一路只拿讀 latch，到葉頁才拿寫 latch；猜錯就重來。

• Lehman–Yao B-link tree（1981）：每頁加右兄弟指標與high key（頁內鍵的上界）。 分裂分成兩步（先建右頁並接上右鏈結，再更新父節點），讀者若發現要找的鍵大於 high key， 就「向右移動」一頁——不需要在下降時持有任何祖先的鎖。這是 PostgreSQL 的基礎。

索引的種類

叢集索引與非叢集索引

• 叢集索引（clustered）：表的資料就是按索引鍵排序存放。每張表只能有一個。 依主鍵的範圍查詢極快（相鄰列在相鄰頁）；代價是二級索引必須存主鍵值作為「列指標」，主鍵越長二級索引越肥， 且隨機主鍵插入會造成全樹分裂。InnoDB、SQL Server（預設 PK）、SQLite（ 表）採用此法。

• 非叢集索引（non-clustered / secondary）：索引與資料分離，葉頁存 TID。PostgreSQL 的所有索引都是如此。 命令只是「一次性」依索引重排 heap，之後的寫入不會維持順序。

涵蓋索引與 Index-Only Scan

若查詢需要的所有欄位都在索引中，就不必回表——這稱為 index-only scan，索引稱為涵蓋索引（covering index）。 PostgreSQL 11 起可用 把非鍵欄位附在葉頁：

CREATE INDEX idx_orders_cust ON orders (customer_id) INCLUDE (total, status);
EXPLAIN SELECT total FROM orders WHERE customer_id = 42;
--  Index Only Scan using idx_orders_cust on orders  (cost=0.43..8.45 rows=1 width=8)
--    Heap Fetches: 0

複合索引與最左前綴

索引 的鍵以字典序排列，因此能有效支援 、、， 但不能有效支援 （沒有 a 就無法定位）。 可以用 a 定位、再在範圍內過濾 c。 範圍條件之後的欄位無法再用於定位： 只能用 a。設計複合索引的口訣： 等值欄位在前、範圍欄位在後、排序欄位緊接著範圍欄位。

其他索引型別（PostgreSQL）

索引的代價

每個索引都是寫入放大：一筆 要更新表加上每一個索引（PostgreSQL 的非 HOT 亦同）； 每個索引都佔緩衝池與磁碟空間，並產生 WAL。經驗法則：

• 選擇性低的欄位（如 boolean、性別）單獨建索引通常沒用——最佳化器寧可全表掃描（第 6 章解釋原因）。

• 寫多讀少的表，索引數量要克制；考慮部分索引只涵蓋熱資料。

• 用 找出從未被用過的索引並移除。

• 建索引用 避免長時間鎖表（代價是需掃描兩次且不能在交易內執行）。

B+Tree 變體速覽

• Copy-on-Write B-Tree（LMDB、BoltDB、Build Your Own Database 的範例）：修改不就地覆寫， 而是複製路徑上的頁面到新位置，最後原子地切換根指標。天然提供快照與崩潰安全，不需要 WAL；代價是寫入放大與空間回收。

• Bw-Tree（Microsoft Hekaton）：以 delta record 鏈與 mapping table 實現 lock-free；論文漂亮但實作極難， CMU 的 Peloton 經驗顯示效能未必勝過加鎖的 B+Tree。

• Fractal Tree / B\(^\epsilon\)-tree（TokuDB）：在內部節點放訊息緩衝區，批次下推寫入，是 B+Tree 與 LSM 之間的折衷。

• 前綴壓縮與 suffix truncation：同頁內鍵共享前綴只存一次；分隔鍵只保留足以區分左右的最短前綴。

• 批次建立（bulk loading）： 不是逐筆插入，而是先外部排序所有 (鍵, TID)，再由下而上填滿葉頁、建內部層， 速度快一個數量級且頁面緊密。

動手觀察：pageinspect 與 EXPLAIN

CREATE TABLE big AS SELECT g AS id, md5(g::text) AS payload FROM generate_series(1, 1000000) g;
CREATE INDEX big_id_idx ON big (id);

SELECT * FROM bt_metap('big_id_idx');             -- root 頁號、level（樹高-1）、fastroot
SELECT * FROM bt_page_stats('big_id_idx', 1);      -- 某頁：type (l/i/r)、live_items、free_size
SELECT itemoffset, ctid, data FROM bt_page_items('big_id_idx', 1) LIMIT 5;

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM big WHERE id = 500000;         -- Index Scan
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM big WHERE id BETWEEN 1 AND 50000; -- Bitmap Heap Scan
EXPLAIN (ANALYZE, BUFFERS) SELECT id FROM big WHERE id < 1000;            -- Index Only Scan

會顯示 （緩衝池命中）與 （實際 I/O）的頁數——把它與你用扇出算出的樹高對照。 Bitmap Heap Scan 是 PostgreSQL 的中間策略：先用索引收集所有符合的 TID 做成點陣圖， 依頁號排序後再循序讀 heap，把隨機 I/O 變成近似循序；當符合列數佔表的數個百分比時特別划算。