資料庫索引是**以特定演算法 (B+ Tree) 組織的有序資料結構**,將「邏輯鍵值」映射至「物理儲存位置」,使查詢從 **O(N) 全表掃描** 降為 **O(log N) 樹狀遍歷**。本文從儲存引擎視角,深度解析 B+ 樹結構、磁碟 I/O 優化原理、叢集/非叢集索引差異、複合索引最左前綴原理與查詢優化器決策邏輯。

| 特性 | B Tree | B+ Tree | Hash Index |
|---|---|---|---|
| 資料儲存位置 | 所有節點 | **僅葉子節點** | 雜湊桶 |
| 範圍查詢 | 需中序遍歷 | **葉子鏈表 O(1) 移動** | ❌ 不支援 |
| 等值查詢 | O(log N) | O(log N) | **O(1) 最快** |
| 適用場景 | 嵌入式/記憶體資料庫 | **關聯式資料庫標準** | 記憶體表、精確查找 |
| 維度 | 叢集索引 (Clustered Index / IOT) | 非叢集索引 (Non-clustered / Heap + B-tree) |
|---|---|---|
| 資料儲存順序 | **依索引鍵值物理排序** | Heap 無序,新資料追加至末尾 |
| 葉子節點內容 | **完整資料行** | **索引鍵值 + Rowid (物理指標)** |
| 每表數量 | **僅一個** (主鍵預設) | 可多個 |
| 查詢路徑 | 樹遍歷 → 直接得資料 | 樹遍歷 → Rowid → **回表 (Key Lookup / Bookmark Lookup)** |
| 插入效能 | 需維持物理順序,**頁面分裂頻繁** | 追加寫入,**索引維護較輕** |
| 適用場景 | 主鍵查詢佔 90%+、範圍掃描密集、無大幅溢出欄位 | 多維度查詢、高併發寫入、大欄位表 |
複合索引 (col_a, col_b, col_c) 實際為 **單一 B+ Tree,鍵值 = (col_a, col_b, col_c) 元組**,按字典序排序。
WHERE a=1、WHERE a=1 AND b=2、WHERE a=1 AND b=2 AND c=3WHERE b=2、WHERE c=3、WHERE a=1 AND c=3 (中間斷裂)WHERE a=1 OR b=2 通常不走索引 (除非 Index Merge)ORDER BY a, b, c 符合索引順序 → 免 FILESORT| 場景 | 原因與對策 |
|---|---|
LIKE '%abc%' / LIKE '%abc' | 非前綴匹配,B+ Tree 無法定位 → **Full Text Search / Oracle Text / 反轉索引** |
col IS NULL / IS NOT NULL | 單列 B-tree 不存 NULL → **Partial Index / Function-Based Index (CASE WHEN)** |
col <> val / NOT IN / NOT EXISTS | 否定條件難以用索引範圍 → **改寫為 UNION ALL / EXISTS / 檢查約束** |
| 索引列參與運算/函數 | YEAR(date_col)=2023 → **Function-Based Index** 或改寫 date_col BETWEEN '2023-01-01' AND '2023-12-31' |
| 隱含類型轉換 | WHERE num_col = '123' → Oracle 隱含 TO_NUMBER(num_col) 導致索引失效 → **顯式轉換 / 修正應用層參數類型** |
| 統計資訊過期/缺失 | 優化器誤判選擇率 → **DBMS_STATS.GATHER_TABLE_STATS 定期收集** |
| 選擇率過高 (>10-15%) | 優化器判斷 Full Scan 更划算 → **Hint 強制 / 改寫 / 物化視圖** |
EXPLAIN PLAN FOR SELECT ...;
SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY(FORMAT=>'ALL +OUTLINE'));
-- 關鍵觀察:Operation = INDEX RANGE SCAN / UNIQUE SCAN / FULL SCAN / SKIP SCAN
-- Access Predicates vs Filter Predicates (後者表示索引掃描後再過濾,未下推)
掌握 B+ 樹物理結構、叢集/非叢集權衡、最左前綴邏輯與優化器決策邊界,即能從「盲目建索引」進化為「精準索引架構師」。