萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 資料庫 >> 資料庫綜合

資料庫索引底層原理:B+ 樹結構、磁碟 I/O 優化與查詢加速機制

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

一、為什麼需要索引?磁碟與記憶體的速度鴻溝

  • CPU L1 Cache:~1 ns、RAM:~100 ns、**SSD 隨機讀:~100 μs、HDD 隨機讀:~10 ms**
  • **核心目標**:將「隨機 I/O 次數」壓縮至 **樹高 (通常 2-4 層)**,避免全表掃描的海量順序/隨機 I/O
  • 索引代價:寫入放大 (Write Amplification) — 每次 DML 需同步更新所有相關索引樹

二、B+ 樹:關聯式資料庫索引的統治者

B+ Tree 示意圖

結構特徵

  • 所有資料僅存於葉子節點,非葉節點僅存 索引鍵值 + 子節點指標
  • 葉子節點雙向鏈表:支援範圍掃描、全序遍歷、ORDER BY 直接輸出
  • 階數 (Order) 大:每節點容納數百鍵值 (取決於 Block Size / Key Size),**樹高極矮** (千萬行資料通常 3 層)
  • 填充因子 / Page Split:插入導致頁面分裂,產生碎片,需定期 Rebuild/Coalesce

對比:B Tree vs B+ Tree vs Hash Index

特性B TreeB+ TreeHash Index
資料儲存位置所有節點**僅葉子節點**雜湊桶
範圍查詢需中序遍歷**葉子鏈表 O(1) 移動**❌ 不支援
等值查詢O(log N)O(log N)**O(1) 最快**
適用場景嵌入式/記憶體資料庫**關聯式資料庫標準**記憶體表、精確查找

三、叢集索引 vs 非叢集索引 (Heap vs Index-Organized)

維度叢集索引 (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=3
    • ❌ WHERE 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+ 樹物理結構、叢集/非叢集權衡、最左前綴邏輯與優化器決策邊界,即能從「盲目建索引」進化為「精準索引架構師」。

copyright © 萬盛學電腦網 all rights reserved