MySQL 索引背後的資料結構及演演算法原理（下）

作者：張洋

網址：http://blog.codinglabs.org/articles/theory-of-mysql-index.html

點選“閱讀原文”可檢視本文網頁版

索引選擇性與字首索引

既然索引可以加快查詢速度，那麼是不是隻要是查詢陳述句需要，就建上索引？答案是否定的。因為索引雖然加快了查詢速度，但索引也是有代價的：索引檔案本身要消耗儲存空間，同時索引會加重插入、刪除和修改記錄時的負擔，另外，MySQL在執行時也要消耗資源維護索引，因此索引並不是越多越好。一般兩種情況下不建議建索引。

第一種情況是表記錄比較少，例如一兩千條甚至只有幾百條記錄的表，沒必要建索引，讓查詢做全表掃描就好了。至於多少條記錄才算多，這個個人有個人的看法，我個人的經驗是以2000作為分界線，記錄數不超過 2000可以考慮不建索引，超過2000條可以酌情考慮索引。

另一種不建議建索引的情況是索引的選擇性較低。所謂索引的選擇性（Selectivity），是指不重覆的索引值（也叫基數，Cardinality）與表記錄數（#T）的比值：

Index Selectivity = Cardinality / #T

顯然選擇性的取值範圍為(0, 1]，選擇性越高的索引價值越大，這是由B+Tree的性質決定的。例如，上文用到的employees.titles表，如果title欄位經常被單獨查詢，是否需要建索引，我們看一下它的選擇性：

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;

+-------------+

| Selectivity |

+-------------+

| 0.0000 |

+-------------+

title的選擇性不足0.0001（精確值為0.00001579），所以實在沒有什麼必要為其單獨建索引。

有一種與索引選擇性有關的索引最佳化策略叫做字首索引，就是用列的字首代替整個列作為索引key，當字首長度合適時，可以做到既使得字首索引的選擇性接近全列索引，同時因為索引key變短而減少了索引檔案的大小和維護開銷。下麵以employees.employees表為例介紹字首索引的選擇和使用。

從圖12可以看到employees表只有一個索引，那麼如果我們想按名字搜尋一個人，就只能全表掃描了：

EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido';

+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |

+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

| 1 | SIMPLE | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where |

+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

如果頻繁按名字搜尋員工，這樣顯然效率很低，因此我們可以考慮建索引。有兩種選擇，建或，看下兩個索引的選擇性：

SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;

+-------------+

| Selectivity |

+-------------+

| 0.0042 |

+-------------+

SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;

+-------------+

| Selectivity |

+-------------+

| 0.9313 |

+-------------+

顯然選擇性太低，選擇性很好，但是first_name和last_name加起來長度為30，有沒有兼顧長度和選擇性的辦法？可以考慮用first_name和last_name的前幾個字元建立索引，例如，看看其選擇性：

SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;

+-------------+

| Selectivity |

+-------------+

| 0.7879 |

+-------------+

選擇性還不錯，但離0.9313還是有點距離，那麼把last_name字首加到4：

SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;

+-------------+

| Selectivity |

+-------------+

| 0.9007 |

+-------------+

這時選擇性已經很理想了，而這個索引的長度只有18，比短了接近一半，我們把這個字首索引建上：

ALTER TABLE employees.employees

ADD INDEX `first_name_last_name4` (first_name, last_name(4));

此時再執行一遍按名字查詢，比較分析一下與建索引前的結果：

SHOW PROFILES;

+----------+------------+---------------------------------------------------------------------------------+

| Query_ID | Duration | Query |

+----------+------------+---------------------------------------------------------------------------------+

| 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |

| 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |

+----------+------------+---------------------------------------------------------------------------------+

效能的提升是顯著的，查詢速度提高了120多倍。

字首索引兼顧索引大小和查詢速度，但是其缺點是不能用於ORDER BY和GROUP BY操作，也不能用於Covering index（即當索引本身包含查詢所需全部資料時，不再訪問資料檔案本身）。

InnoDB的主鍵選擇與插入最佳化

在使用InnoDB儲存引擎時，如果沒有特別的需要，請永遠使用一個與業務無關的自增欄位作為主鍵。

經常看到有帖子或部落格討論主鍵選擇問題，有人建議使用業務無關的自增主鍵，有人覺得沒有必要，完全可以使用如學號或身份證號這種唯一欄位作為主鍵。不論支援哪種論點，大多數論據都是業務層面的。如果從資料庫索引最佳化角度看，使用InnoDB引擎而不使用自增主鍵絕對是一個糟糕的主意。

上文討論過InnoDB的索引實現，InnoDB使用聚集索引，資料記錄本身被存於主索引（一顆B+Tree）的葉子節點上。這就要求同一個葉子節點內（大小為一個記憶體頁或磁碟頁）的各條資料記錄按主鍵順序存放，因此每當有一條新的記錄插入時，MySQL會根據其主鍵將其插入適當的節點和位置，如果頁面達到裝載因子（InnoDB預設為15/16），則開闢一個新的頁（節點）。

如果表使用自增主鍵，那麼每次插入新的記錄，記錄就會順序新增到當前索引節點的後續位置，當一頁寫滿，就會自動開闢一個新的頁。如下圖所示：

圖13

這樣就會形成一個緊湊的索引結構，近似順序填滿。由於每次插入時也不需要移動已有資料，因此效率很高，也不會增加很多開銷在維護索引上。

如果使用非自增主鍵（如果身份證號或學號等），由於每次插入主鍵的值近似於隨機，因此每次新紀錄都要被插到現有索引頁得中間某個位置：

圖14

此時MySQL不得不為了將新記錄插到合適位置而行動資料，甚至標的頁面可能已經被回寫到磁碟上而從快取中清掉，此時又要從磁碟上讀回來，這增加了很多開銷，同時頻繁的移動、分頁操作造成了大量的碎片，得到了不夠緊湊的索引結構，後續不得不透過OPTIMIZE TABLE來重建表並最佳化填充頁面。

因此，只要可以，請儘量在InnoDB上採用自增欄位做主鍵。

後記

這篇文章斷斷續續寫了半個月，主要內容就是上面這些了。不可否認，這篇文章在一定程度上有紙上談兵之嫌，因為我本人對MySQL的使用屬於菜鳥級別，更沒有太多資料庫調優的經驗，在這裡大談資料庫索引調優有點大言不慚。就當是我個人的一篇學習筆記了。

其實資料庫索引調優是一項技術活，不能僅僅靠理論，因為實際情況千變萬化，而且MySQL本身存在很複雜的機制，如查詢最佳化策略和各種引擎的實現差異等都會使情況變得更加複雜。但同時這些理論是索引調優的基礎，只有在明白理論的基礎上，才能對調優策略進行合理推斷並瞭解其背後的機制，然後結合實踐中不斷的實驗和摸索，從而真正達到高效使用MySQL索引的目的。

另外，MySQL索引及其最佳化涵蓋範圍非常廣，本文只是涉及到其中一部分。如與排序（ORDER BY）相關的索引最佳化及改寫索引（Covering index）的話題本文並未涉及，同時除B-Tree索引外MySQL還根據不同引擎支援的雜湊索引、全文索引等等本文也並未涉及。如果有機會，希望再對本文未涉及的部分進行補充吧。

參考文獻

[1] Baron Scbwartz等 著，王小東等 譯；高效能MySQL（High Performance MySQL）；電子工業出版社，2010

[2] Michael Kofler 著，楊曉雲等 譯；MySQL5權威指南（The Definitive Guide to MySQL5）；人民郵電出版社，2006

[3] 薑承堯 著；MySQL技術內幕-InnoDB儲存引擎；機械工業出版社，2011

[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

[5] Codd, E. F. (1970). “A relational model of data for large shared data banks”. Communications of the ACM, , Vol. 13, No. 6, pp. 377-387

[6] MySQL5.1參考手冊