Enter your search text in the box above

Select a result to preview

B-Tree 索引 (B-Tree Index)

#database #indexing #b-tree #system-design

什麼是 B-Tree

B-Tree（Balanced Tree，平衡樹） 是最常用的資料庫索引結構，專為 磁碟存取優化。

特性 說明
平衡 所有葉節點到根的距離相同，查詢複雜度穩定 O(log n)
多叉樹 每節點可存多個 key 和多個子節點指標，不是二元樹
磁碟友好 節點大小對齊磁碟頁（通常 4KB / 8KB），一次 I/O 讀一整節點
現代資料庫索引預設就是 B-Tree / B+Tree

MySQL InnoDB、PostgreSQL、Oracle、SQL Server 的主鍵索引、唯一索引、普通索引
大部分都是 B-Tree 或其變體。

B-Tree 結構

                   [ 20 | 40 ]            ← 內部節點
                  /    |     \
                 /     |      \
        [10 | 15]  [25|30|35]  [50|60]    ← 葉節點

查找 30 的過程

[ 20 | 40 ]          ← 30 介於 20 和 40 之間 → 走中間
      |
[ 25 | 30 | 35 ]     ← 找到 30 ✓

B-Tree 的四大支援

能力 說明
等值查詢 WHERE id = 123 → O(log n)
範圍查詢 BETWEEN、<、>、>= → 有序 key 可連續掃描
排序 ORDER BY 可直接利用索引順序，不需額外排序
動態更新 插入 / 刪除後自動重平衡，保持 O(log n) 特性

B-Tree vs B+Tree

生產環境其實大多用 B+Tree（B-Tree 的變體）。

差異點 B-Tree B+Tree
資料存放位置 內部節點和葉節點都能存資料 只有葉節點存資料，內部節點只放索引 key
葉節點連結 無 有 linked list 連接葉節點 → 範圍掃描超快
範圍查詢效率 較差 較好（葉節點橫向走即可，不需回上層）
樹高 稍高 稍低（內部節點可放更多 key）
為什麼 B+Tree 贏

範圍查詢時只要找到起點葉節點，就能 沿著葉節點 linked list 線性走 到結束點；
B-Tree 則要反覆回到上層節點，I/O 次數更多。

常見實作：

實際應用場景

PostgreSQL 自動建立的索引

CREATE TABLE products (
  product_id SERIAL PRIMARY KEY,
  name VARCHAR(255) NOT NULL,
  sku VARCHAR(100) UNIQUE
);

PostgreSQL 自動建立兩個 B-Tree 索引：

  1. Primary Key on product_id
  2. Unique Constraint on sku

這些 B-Tree 維持排序，所以：

其他系統中的 B-Tree

系統 應用
DynamoDB Sort key 是 B-Tree 變體，分區內高效範圍查詢（如「user X 在 Y~Z 日期的所有訂單」）
MongoDB 文件索引用 B+Tree（資料存葉節點）
SQLite 所有索引預設 B-Tree

Simplification-with-exceptions

邊界情況

  • 寫入放大（Write Amplification） — 隨機寫會頻繁更新多個節點 → 高寫入壓力場景考慮 LSM Tree。
  • B-Tree 索引對 LIKE '%abc' 無效 — 前綴 % 打破了排序順序；要用全文索引或函數索引。
  • Hash Index 在等值查詢上更快（O(1) vs O(log n)），但 B-Tree 犧牲一點速度換取
    範圍查詢能力，通常 trade 得值。
  • 樹高很穩定 — 10 億筆資料的 B+Tree 樹高通常只有 3~4 層，因此「O(log n) 的
    實際常數」非常小。

與其他索引的對比

索引 等值查詢 範圍查詢 排序 寫入
B-Tree O(log n) ✅ ✅ 🟡
04-Database-Indexing/04-Hash-Index O(1) ❌ ❌ 🟢
04-Database-Indexing/03-LSM-Tree O(log n)+多層 🟡 ✅ 🟢