第三章：叢集與非叢集索引 — 數據的物理地圖

1. 定義

叢集索引 (Clustered Index)：一種存儲結構，其 B+Tree 的葉子節點直接存儲了整行數據。一張表只能有一個叢集索引（通常是主鍵），因為數據只能以一種物理順序存儲。

非叢集索引 (Non-Clustered Index)（又稱二級索引 Secondary Index）：葉子節點不存儲行數據，而是存儲指向數據的指標。在 MySQL InnoDB 中，這個指標是主鍵值；在 MyISAM 中它通常是物理檔案偏移量，而 PostgreSQL 則使用 Tuple ID (CTID)。

2. 技術深度：回表查詢 (Double Lookup)

在 InnoDB 中，如果你透過二級索引查找數據，實際上會發生兩次 B+Tree 查找。

1. 第一跳：在二級索引樹中查找，找到葉子節點存儲的主鍵值（如 ID=55）。
2. 第二跳（回表）：拿著 ID=55 到叢集索引樹中查找，獲取完整的行數據。

這種「回表」會產生額外的隨機 I/O，是查詢效能的頭號殺手。

3. 可視化：InnoDB 索引結構對比

flowchart TD
    subgraph Secondary [二級索引 (按 Name)]
        IndexLeaf[葉子節點: Key='Alice', PK=101]
    end

    subgraph Clustered [叢集索引 (按 PK)]
        DataLeaf[葉子節點: PK=101, RowData={Alice, 25, NYC}]
    end

    Query[查詢: SELECT * FROM users WHERE Name='Alice']
    
    Query -->|1. 查找 Name| Secondary
    Secondary --"獲得 PK=101"--> Query
    Query -->|2. 回表查找 PK| Clustered
    Clustered -->|回傳行數據| Query

4. 真實案例：Uber 的 Postgres 到 MySQL 遷移 (2013-2016)

背景：Uber 早期大量使用 PostgreSQL。Postgres 預設使用「堆表 (Heap Table)」模型，所有的索引（包括主鍵）都是二級索引，指向 Heap 中的 CTID（行物理位置）。

挑戰：寫入放大 (Write Amplification)

• Postgres 使用 MVCC，更新一行數據通常會生成一個新的行版本（新的 CTID）。
• 這意味著所有指向該行的索引都需要更新其 CTID 指標。
• 對於像 Uber 這樣擁有數十個索引的大表，更新一次用戶狀態可能導致十幾次索引寫入。

技術選型：Uber 遷移到了 MySQL (InnoDB)。

• InnoDB 優勢：在 InnoDB 中，二級索引指向主鍵值。當行數據更新位置（或頁分裂）時，只要主鍵不變，二級索引就不需要修改。
• 這極大降低了更新操作的 I/O 成本，尤其是在從庫複製（Replication）場景下。

注意：Postgres 後續透過 HOT (Heap-Only Tuples) 技術部分緩解了此問題，但 Uber 的案例仍是理解索引架構差異的經典教材。

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

A. 覆蓋索引 (Covering Index)

消除回表的終極手段。

• 技巧：如果查詢是 SELECT age FROM users WHERE name = 'Alice'，可以創建一個聯合索引 (name, age)。
• 效果：數據在二級索引樹的葉子節點中已經存在（Key='Alice', age=25, PK=101），引擎直接回傳，無需回表。

B. 主鍵的選擇

• 短小：由於所有二級索引都包含主鍵，主鍵越長（如 UUID），二級索引就越膨脹。
• 靜態：主鍵一旦確立，絕不應更新。更新主鍵意味著要重寫叢集索引和所有二級索引。

C. 索引選擇性 (Selectivity)

• 不要為低選擇性的欄位（如 Gender：男/女）建立單列非叢集索引。最佳化器會認為全表掃描比「透過索引查找一半的主鍵再回表」更快，從而忽略該索引。

6. 參考資料

• Uber Engineering: Why We Moved from Postgres to MySQL
• MySQL Reference: Clustered and Secondary Indexes
• PostgreSQL Documentation: Index Types