淺談 InnoDB 的 Cluster Index 和 Secondary Index

Clustered Index (primary Index)

clustered index 與其說是 index， 不如說是 InnoDB 用來儲存資料的結構更恰當。

Clustered Index 採用 B-Tree 資料結構，每個 node 都是一個 page (InnoDB 存資料的最小單位)； node 存 key 的值和指向 child node 的指標，leaf node 則存 row data 和指向鄰近 node 的指標，下面是一個簡單的示意圖：

資料會依照 clustered index 的 key 值排序，鄰近的 node 彼此透過 pointer 連接，這樣有兩個好處：

1. 關係相近的資料會被集中在同一個 page，讀取相關資料的時候只 load 幾個 page 就好。例如上圖若要讀取 key 5 和 key 6 的資料，只要 load page 5 就好。
2. 執行 range query 時不用整棵樹都掃描過一遍，只要找到最小的 key 值所在的 page，一直往後讀即可。例如上圖查詢 key 值在 5~10 的資料，只要找到 key 5 所在的 page 5，然後一直往後讀值到 key 10 所在的 page 7 為止。

相對的排序好的資料也有額外的風險，就是塞資料順序如果和 key 的順序不一致時容易造成效能問題。例如上圖如果塞一筆 key 為 13 的資料時，會直接塞到 page 8；但若是塞一筆 key 為 9 的資料時會導致 page 7 產生 page split，這情況下 MySQL 會在 page 間搬動資料，連帶影響效能。

MySQL 塞資料到時不會把全部的 page 空間用完，會保留一部分空間做日後新增或更新使用，如上圖的 page 6。根據 MySQL 5.7 Reference Manual：

If index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full.

如果 index 的紀錄是循序插入，index page 會維持在 15/16 滿左右，但若是亂序插入的話，index pagee 會維持 1/2 到 15/16 滿。

由上述原因可以知道 clustered index 的 key 值會影響 range query 、塞資料的效能和 page 空間的使用率，所以一個洽當的 clustered key 很重要。MySQL 選擇 clustered key 的規則如下：

1. 有 primary key，選 primary key 。
2. 沒有 primary key，選第一個 NOT NULL 的 UNIQUE key 。
3. 若都沒有，產生一個 auto increment 的隱藏欄位做 clustered key。

Secondary Index

secondary index 一樣也是用 B-Tree 資料結構，不同的是 leaf node 只存 key 值和 clustered key 值 (通常是 primary key)，用以去 clustered index 找 row data：

由上圖可以看到用 secondary index 做 range query 存取row data 時不一定是循序讀，因為 row data 是依照 clustered index 的 key 排序。因此用 secondary index 做 range query 抓 row data 的效能通常不如 clustered index。同時因為 leaf node 會儲存 clustered key 的值，因此 clustered key 的大小也會影響 secondary index 的大小，在挑選 clustered key 時要注意這點。

另外當 SELECT 的欄位被 secondary index 覆蓋的話，MySQL 不會再去 row data 取值，會直接取從 leaf node 取值，執行速度比較快。例如下面的 table：

CREATE TABLE `test_table` (
  `primary_key` int(11) NOT NULL,
  `secondary_key` int(11) DEFAULT NULL,
  `other_key` int(11) DEFAULT NULL,
  PRIMARY KEY (`primary_key`),
  KEY `SECONDARY` (`secondary_key`)
)

用 explain 指令觀察僅 SELECT primary_key 和 secondary_key 的 SQL，extra 欄位顯示 using index，即是 MySQL 執行這個語法時直接從索引拿值。

反之，則會看到 extra 欄位出現 using index condition，即是最後還是會去取 row data 的值。

小結

索引是個極度複雜的主題，但透過瞭解索引底層的運作原理可以幫助我們更精準的設計符合使用情境的索引，基本原則：

1. InnoDB 讀資料是以 page 為單位，load 一個 page 只為讀一筆資料是很浪費效能的行為。挑選好 primary key，讓關聯資料集中在幾個 page 裡面，這樣 InnoDB 可以 load 一個 page 讀到多筆資料。
2. Secondary index 去抓 row data 會需要多一次 lookup 動作，而且如同第一點提到的，單一筆資料的存取會浪費效能。因此讓 secondary index 涵蓋所有需要的欄位對效能會有顯著提升。