索引原理與最佳化#

索引是資料庫系統裡面最重要的概念之一。簡單來說，索引的出現是為了提高資料查詢的效率，就像書的目錄一樣。

索引的常見模型#

可以用於提高讀寫效率的資料結構很多，這裡介紹三種常見模型：

雜湊表#

雜湊表是一種以鍵-值（key-value）儲存資料的結構，透過雜湊函式把 key 換算成陣列位置。

flowchart LR
    H1["ID_card_n1"] -->|hash| U1["User1"]
    H2["ID_card_n2"] -->|hash| U2["User2"] --> U4["User4"]
    H3["ID_card_n3"] -->|hash| U3["User3"]

    style U4 fill:#fff3e0

雜湊衝突時使用鏈結串列解決

特點：

• 新增記錄很快，只需往後追加
• 不適合範圍查詢（必須全表掃描）

雜湊表適用於只有等值查詢的場景，比如 Memcached 及其他 NoSQL 引擎。

有序陣列#

flowchart LR
    subgraph Array["有序陣列"]
        direction LR
        I1["ID1"] --- I2["ID2"] --- I3["ID3"] --- I4["ID4"] --- I5["ID5"] --- I6["ID6"]
    end

    BS["二分搜尋<br/>O(log N)"] -.-> I1

    style BS fill:#e3f2fd

特點：

• 等值查詢和範圍查詢效能都優秀
• 插入成本太高（需要挪動後面所有記錄）

有序陣列只適用於靜態儲存引擎，比如歷史資料歸檔。

N 元樹（B+ 樹）#

二元樹查詢效率高 $O(\log N)$，但 100 萬節點的平衡二元樹，樹高 20，每次查詢要存取 20 個資料區塊。

為什麼用 N 元樹？

flowchart TD
    A[根節點<br/>常駐記憶體] --> B[分支]
    A --> C[分支]
    A --> D[分支]

    B --> E[葉子<br/>實際資料]
    B --> F[葉子<br/>實際資料]
    B --> G[葉子<br/>實際資料]

• InnoDB 的整數索引 N 約等於 1200
• 樹高 4 時，可存 $1200^3 = 17$ 億條記錄
• 查找一個值最多存取 3-4 次磁碟

N 元樹（B+ 樹）由於適配磁碟的存取模式，已被廣泛應用在資料庫引擎中。

InnoDB 的索引模型#

在 InnoDB 中，資料表都是根據主鍵順序以索引的形式存放的，這種儲存方式的資料表稱為索引組織表。

兩種索引類型#

CREATE TABLE T (
  id INT PRIMARY KEY,
  k INT NOT NULL,
  name VARCHAR(16),
  INDEX (k)
) ENGINE=InnoDB;

回表#

查詢：SELECT * FROM T WHERE k=5

步驟 1: 搜尋 k 索引樹，找到 k=5，得到 ID=500
步驟 2: 搜尋 ID 索引樹，找到 ID=500 的完整記錄  ← 這就是「回表」

基於非主鍵索引的查詢需要多掃描一棵索引樹，因此應用中應該盡量使用主鍵查詢。

索引維護#

頁分裂與頁合併#

B+ 樹為了維護索引有序性，在插入新值時需要做必要的維護：

為什麼推薦自增主鍵#

效能角度：

• 自增主鍵的插入模式是追加操作
• 不涉及挪動其他記錄
• 不會觸發葉子節點的分裂

儲存角度：

• 每個二級索引的葉子節點都存主鍵值
• 主鍵越小，二級索引佔用空間越小

適合用業務欄位做主鍵的場景：只有一個索引，且必須是唯一索引（典型的 KV 場景）。

索引最佳化技術#

覆蓋索引#

如果查詢的欄位已經在索引中，就不需要回表。

-- 需要回表
SELECT * FROM T WHERE k BETWEEN 3 AND 5;

-- 覆蓋索引，不需要回表
SELECT ID FROM T WHERE k BETWEEN 3 AND 5;

覆蓋索引可以減少樹的搜尋次數，顯著提升查詢效能，是常用的效能最佳化手段。後續「06 效能調優」章節在討論查詢最佳化時也會引用此概念。

最左前綴原則#

B+ 樹索引可以利用索引的「最左前綴」來定位記錄。

-- 聯合索引 (name, age)
-- 索引項按 name 排序，name 相同時按 age 排序

-- 可以用上索引
WHERE name = '張三'
WHERE name LIKE '張%'

-- 無法使用索引
WHERE age = 10

聯合索引的欄位順序原則：

1. 複用原則：如果透過調整順序可以少維護一個索引，優先採用
2. 空間原則：如果 a 和 b 都需要單獨索引，把大欄位放聯合索引，小欄位單獨建索引

索引下推 (Index Condition Pushdown)#

MySQL 5.6 引入的最佳化，在索引走訪過程中對索引中包含的欄位先做判斷，減少回表次數。

-- 聯合索引 (name, age)
SELECT * FROM tuser WHERE name LIKE '張%' AND age = 10;

索引設計原則#

建索引的考量#

重建索引#

索引可能因為刪除或頁分裂導致資料頁有空洞，重建索引可以讓索引更緊湊。

-- 重建二級索引（可以）
ALTER TABLE T DROP INDEX k;
ALTER TABLE T ADD INDEX(k);

-- 重建主鍵索引（不合理，會重建整個資料表兩次）
ALTER TABLE T DROP PRIMARY KEY;
ALTER TABLE T ADD PRIMARY KEY(id);

-- 正確做法：重建表
ALTER TABLE T ENGINE=InnoDB;

本章小結#

設計建議：一般情況下使用自增主鍵；利用覆蓋索引減少回表；聯合索引注意欄位順序；定期評估索引使用情況。