Luke a Pro

Luke Sun

Developer & Marketer

🇺🇦
EN|简|繁
© 2015–2026 Luke Sun.
All rights reserved.

第一章：B-Tree 與 B+Tree — 索引的數學骨架

| , 2 minutes reading.

1. 定義

B-Tree（平衡多路搜尋樹）是一種自平衡的樹狀資料結構，它維護有序數據並允許以對數時間進行搜尋、順序存取、插入和刪除。它由 Rudolf Bayer 和 Edward M. McCreight 於 1972 年定義。

B+Tree 是 B-Tree 的變體，其特點是：

  1. 非葉子節點不存儲數據：僅存儲鍵（Key）作為索引。
  2. 葉子節點鏈表化：所有數據均存儲在葉子節點，且葉子節點之間透過雙向指標連接，便於範圍掃描（Range Scan）。

2. 技術深度：為什麼是 B+Tree 而不是二元樹？

資料庫索引之所以不使用紅黑樹或 AVL 樹，核心原因在於減少磁碟 I/O 次數。

A. 扇出 (Fan-out) 與樹的高度

在磁碟中，數據是以 Page (頁) 為單位讀取的（InnoDB 預設為 16KB）。

  • 二元樹：每個節點只有 2 個子節點，樹的高度 HH 約為 log⁡2N\log_2 N。對於 1000 萬筆數據，高度約 24 層，意味著最壞情況需要 24 次磁碟 I/O。
  • B+Tree：透過增大扇出（例如每個節點存儲 100 個鍵），樹的高度 HH 大幅降低。同樣 1000 萬筆數據，高度僅需 3-4 層。

B. B+Tree 的磁碟預讀優勢

由於 B+Tree 的非葉子節點不存數據，一個 Page 可以容納更多的鍵（Key），從而進一步提高扇出。同時，葉子節點的鏈表結構使得**範圍查詢（Range Scan）**無需回溯父節點，直接在葉子層水平移動即可。

3. 可視化：Page 分裂 (Page Split) 過程

當一個 Page 已滿（達到填充因子限額）且有新數據插入時，資料庫會觸發一次「不可見」的底層操作：Page Split。

sequenceDiagram
    participant App as 插入請求
    participant Buffer as Buffer Pool (記憶體)
    participant PageA as Page 101 (已滿)
    participant PageB as Page 102 (新申請)

    App->>Buffer: 插入鍵 50
    Buffer->>PageA: 嘗試寫入
    Note over PageA: 數據溢出 (Overflow)
    
    Buffer->>PageB: 申請新空頁
    PageA->>PageB: 遷移一部分記錄 (如鍵 30-49)
    Note over PageA,PageB: 重新平衡節點
    
    Buffer-->>Buffer: 更新父節點索引指標
    Note over Buffer: 磁碟 I/O 放大開始

4. 真實案例：Instagram 的 ID 生成策略 (2011)

背景：2011 年，Instagram 工程團隊在設計其媒體 ID 生成系統時，需要一種能夠跨分片（Shard）唯一且高效能的方案。

技術選型：他們最初考慮了 UUID (Universally Unique Identifier)。 拒絕理由：

  1. 索引大小：UUID 是 128 位元的，而 bigint 只有 64 位元。對於擁有數十億筆記錄的資料表，索引會變得極其臃腫，難以全部裝入記憶體。
  2. B+Tree 效能噩夢：UUID 是完全隨機的。在 B+Tree 索引中，這會導致數據被隨機插入到不同的 Page 中。由於 Page 頻繁分裂（Page Split），磁碟物理存儲變得極其不連續，且每個 Page 的填充率（Fill Factor）極低。這引發了大量的隨機磁碟 I/O，嚴重拖慢了寫入速度並擠壓了 Buffer Pool 空間。

最終方案：Instagram 參考了 Twitter 的 Snowflake 演算法，設計了一種包含 時間戳前綴 的 64 位元邏輯 ID。

  • 優勢：由於 ID 是趨勢遞增的，新記錄大多追加到 B+Tree 的右側葉子節點。這避免了中間節點的頻繁隨機分裂，通常能維持較高的 Page 填充率（取決於具體的分裂策略），並顯著提升了快取命中率與寫入局部性 (Write Locality)。

教訓：在高興能資料庫設計中，索引列的順序性往往比唯一性更具挑戰。高品質的架構師會透過犧牲一定的隨機性來換取 B+Tree 的物理連續性。

5. 深度最佳化與縱深防禦

A. 根本修復：選擇合適的叢集索引 (Clustered Index)

  • 優先使用自增 ID 或趨勢遞增的鍵作為叢集索引。
  • 對於非遞增鍵，考慮降低 FILLFACTOR（填充因子，Postgres 術語）或 innodb_fill_factor（MySQL，依版本/場景生效），為隨機插入預留空間，減少分裂。

B. 縱深防禦：索引覆蓋 (Covering Index)

  • 透過將常用查詢欄位放入二級索引，避免「回表查詢」，降低額外 I/O 成本。

C. 碎片清理

  • 定期執行 OPTIMIZE TABLE (MySQL) 或 REINDEX (Postgres) 以回收物理碎片，重新平衡樹狀結構。

6. 參考資料