程式師世界 >> 數據庫知識 >> MYSQL數據庫 >> MySQL綜合教程 >> MySQL索引背後的數據結構及算法原理(下)

MySQL索引背後的數據結構及算法原理(下)

編輯：MySQL綜合教程

MySQL索引背後的數據結構及算法原理(下)

為了討論索引策略，需要一個數據量不算小的數據庫作為示例。本文選用MySQL官方文檔中提供的示例數據庫之一：employees。這個數據庫關系復雜度適中，且數據量較大。下圖是這個數據庫的E-R關系圖（引用自MySQL官方手冊）：

下載文件後使用下面的語句將數據庫導入：<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxibG9ja3F1b3RlPg0KCTxwPnRhciAteGpmICRIT01FL0Rvd25sb2Fkcy9lbXBsb3llZXNfZGItZnVsbC0xLjAuNC50YXIuYnoyIC8vveLRucv1o6y9+MjrxL/CvDxiciAvPg0KCWNkIGVtcGxveWVlc19kYi8gLy+1vMjryv2+3b/icm9vdM6q08O7p8P7PGJyIC8+DQoJbXlzcWwgLXQgLXUgcm9vdCAtcCAmbHQ7IGVtcGxveWVlcy5zcWw8L3A+DQo8L2Jsb2NrcXVvdGU+DQo8cD7K/b7dv+K8x8K8tcTK/cG/vLbU2ry4yq7N8rW9vLiw2c3y1/PT0qGjyse49sDtz+u1xL/J08W7r7u3vrOhozwvcD4NCjxoMyBpZD0="最左前綴原理與相關優化">最左前綴原理與相關優化

高效使用索引的首要條件是知道什麼樣的查詢會使用到索引，這個問題和B+Tree中的“最左前綴原理”有關，下面通過例子說明最左前綴原理。

這裡先說一下聯合索引的概念。在上文中，我們都是假設索引只引用了單個的列，實際上，MySQL中的索引可以以一定順序引用多個列，這種索引叫做聯合索引，一般的，一個聯合索引是一個有序元組，其中各個元素均為數據表的一列，實際上要嚴格定義索引需要用到關系代數，但是這裡我不想討論太多關系代數的話題，因為那樣會顯得很枯燥，所以這裡就不再做嚴格定義。另外，單列索引可以看成聯合索引元素數為1的特例。

以employees.titles表為例，下面先查看其上都有哪些索引：

SHOW INDEX FROM employees.titles;
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
| Table  | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
| titles |          0 | PRIMARY  |            1 | emp_no      | A         |        NULL |      | BTREE      |
| titles |          0 | PRIMARY  |            2 | title       | A         |        NULL |      | BTREE      |
| titles |          0 | PRIMARY  |            3 | from_date   | A         |      443308 |      | BTREE      |
| titles |          1 | emp_no   |            1 | emp_no      | A         |      443308 |      | BTREE      |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+

從結果中可以到titles表的主索引為，還有一個輔助索引。為了避免多個索引使事情變復雜（MySQL的SQL優化器在多索引時行為比較復雜），這裡我們將輔助索引drop掉：

ALTER TABLE employees.titles DROP INDEX emp_no;

443308條記錄受影響。這樣就可以專心分析索引PRIMARY的行為了。

`情況一：全列匹配。`

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';

+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref               | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
|  1 | SIMPLE      | titles | const | PRIMARY       | PRIMARY | 59      | const,const,const |    1 |       |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

explain執行的是計劃任務，是對查詢語句進行執行計劃。

很明顯，當按照索引中所有列進行精確匹配（這裡精確匹配指“=”或“IN”匹配）時，索引可以被用到。這裡有一點需要注意，理論上索引對順序是敏感的，但是由於MySQL的查詢優化器會自動調整where子句的條件順序以使用適合的索引，例如我們將where中的條件順序顛倒：

EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26' AND emp_no='10001' AND title='Senior Engineer';
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref               | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
|  1 | SIMPLE      | titles | const | PRIMARY       | PRIMARY | 59      | const,const,const |    1 |       |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

對上述列中的含義進行解讀：

(1)id :select查詢的序列號
(2)select_type:select查詢的類型，主要是區別普通查詢和聯合查詢、子查詢之類的復雜查詢
a.SIMPLE：查詢中不包含子查詢或者UNION
b.查詢中若包含任何復雜的子部分，最外層查詢則被標記為：PRIMARY
c.在SELECT或WHERE列表中包含了子查詢，該子查詢被標記為：SUBQUERY
d.在FROM列表中包含的子查詢被標記為：DERIVED（衍生）
e.若第二個SELECT出現在UNION之後，則被標記為UNION；若UNION包含在FROM子句的子查詢中，外層SELECT將被標記為：DERIVED
f.從UNION表獲取結果的SELECT被標記為：UNION RESULT

(3)table :輸出的行所引用的表。 
(4)type :聯合查詢所使用的類型，表示MySQL在表中找到所需行的方式，又稱“訪問類型”。
type顯示的是訪問類型，是較為重要的一個指標，結果值從好到壞依次是：
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL ，一般來說，得保證查詢至少達到range級別，最好能達到ref。
ALL: 掃描全表
index: 掃描全部索引樹
range: 掃描部分索引，索引范圍掃描，對索引的掃描開始於某一點，返回匹配值域的行，常見於between、<、>等的查詢
ref: 非唯一性索引掃描，返回匹配某個單獨值的所有行。常見於使用非唯一索引即唯一索引的非唯一前綴進行的查找

eq_ref：唯一性索引掃描，對於每個索引鍵，表中只有一條記錄與之匹配。常見於主鍵或唯一索引掃描
const, system: 當MySQL對查詢某部分進行優化，並轉換為一個常量時，使用這些類型訪問。如將主鍵置於where列表中，MySQL就能將該查詢轉換為一個常量。system是const類型的特例，當查詢的表只有一行的情況下， 使用system。
NULL: MySQL在優化過程中分解語句，執行時甚至不用訪問表或索引。

(5)possible_keys:指出MySQL能使用哪個索引在該表中找到行。查詢涉及到的字段上若存在索引，則該索引將被列出，但不一定被查詢使用。如果是空的，沒有相關的索引。這時要提高性能，可通過檢驗WHERE子句，看是否引用某些字段，或者檢查字段不是適合索引。 

(6)key :顯示MySQL實際決定使用的鍵。如果沒有索引被選擇，鍵是NULL。

(7) key_len:顯示MySQL決定使用的鍵長度。表示索引中使用的字節數，可通過該列計算查詢中使用的索引的長度。如果鍵是NULL，長度就是NULL。文檔提示特別注意這個值可以得出一個多重主鍵裡mysql實際使用了哪一部分。

 注：key_len顯示的值為索引字段的最大可能長度，並非實際使用長度，即key_len是根據表定義計算而得，不是通過表內檢索出的。

(8)ref:顯示哪個字段或常數與key一起被使用。

 (9)rows:這個數表示mysql要遍歷多少數據才能找到，表示MySQL根據表統計信息及索引選用情況，估算的找到所需的記錄所需要讀取的行數，在innodb上可能是不准確的。

 (10)Extra:包含不適合在其他列中顯示但十分重要的額外信息。

Only index，這意味著信息只用索引樹中的信息檢索出的，這比掃描整個表要快。 


using where是使用上了where限制，表示MySQL服務器在存儲引擎受到記錄後進行“後過濾”（Post-filter），如果查詢未能使用索引，Using where的作用只是提醒我們MySQL將用where子句來過濾結果集。


impossible where 表示用不著where，一般就是沒查出來啥。 


Using filesort（MySQL中無法利用索引完成的排序操作稱為“文件排序”）當我們試圖對一個沒有索引的字段進行排序時，就是filesoft。它跟文件沒有任何關系，實際上是內部的一個快速排序。 


Using temporary（表示MySQL需要使用臨時表來存儲結果集，常見於排序和分組查詢），使用filesort和temporary的話會很吃力，WHERE和ORDER BY的索引經常無法兼顧，如果按照WHERE來確定索引，那麼在ORDER BY時，就必然會引起Using filesort，這就要看是先過濾再排序劃算，還是先排序再過濾劃算。

舉例如下：

第一行：id列為1，表示第一個select，select_type列的primary表示該查詢為外層查詢，table列被標記為，表示查詢結果來自一個衍生表，其中3代表該查詢衍生自第三個select查詢，即id為3的select。[select d1.name......]
第二行：id為3，表示該查詢的執行次序為2（4→3），是整個查詢中第三個select的一部分。因查詢包含在from中，所以為derived。[select id,name from t1 where other_column='']
第三行：select列表中的子查詢，select_type為subquery，為整個查詢中的第二個select。[select id from t3]
第四行：select_type為union，說明第四個select是union裡的第二個select，最先執行。[select name,id from t2]
第五行：代表從union的臨時表中讀取行的階段，table列的表示用第一個和第四個select的結果進行union操作。[兩個結果union操作]



關於MySQL執行計劃的局限性：

EXPLAIN不會告訴你關於觸發器、存儲過程的信息或用戶自定義函數對查詢的影響情況
EXPLAIN不考慮各種Cache
EXPLAIN不能顯示MySQL在執行查詢時所作的優化工作
部分統計信息是估算的，並非精確值
EXPALIN只能解釋SELECT操作，其他操作要重寫為SELECT後查看。


備注：

filesort是通過相應的排序算法,將取得的數據在內存中進行排序。


MySQL需要將數據在內存中進行排序，所使用的內存區域也就是我們通過sort_buffer_size 系統變量所設置的排序區。這個排序區是每個Thread 獨享的，所以說可能在同一時刻在MySQL 中可能存在多個 sort buffer 內存區域。


在MySQL中filesort 的實現算法實際上是有兩種：

雙路排序：是首先根據相應的條件取出相應的排序字段和可以直接定位行數據的行指針信息，然後在sort buffer 中進行排序。
單路排序：是一次性取出滿足條件行的所有字段，然後在sort buffer中進行排序。


在MySQL4.1版本之前只有第一種排序算法雙路排序，第二種算法是從MySQL4.1開始的改進算法，主要目的是為了減少第一次算法中需要兩次訪問表數據的IO操作，將兩次變成了一次，但相應也會耗用更多的sortbuffer 空間。當然，MySQL4.1開始的以後所有版本同時也支持第一種算法。
MySQL主要通過比較我們所設定的系統參數 max_length_for_sort_data的大小和Query 語句所取出的字段類型大小總和來判定需要使用哪一種排序算法。如果 max_length_for_sort_data更大，則使用第二種優化後的算法，反之使用第一種算法。所以如果希望 ORDER BY 操作的效率盡可能的高，一定要注意max_length_for_sort_data 參數的設置。如果filesort過程中，由於排序緩存的大小不夠大，那麼就可能會導致臨時表的使用。


max_length_for_sort_data的默認值是1024。

`對explain的解讀到此結束`

`情況二：最左前綴匹配。`

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 |       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+

當查詢條件精確匹配索引的左邊連續一個或幾個列時，如或，所以可以被用到，但是只能用到一部分，即條件所組成的最左前綴。上面的查詢從分析結果看用到了PRIMARY索引，但是key_len為4，說明只用到了索引的第一列前綴。

`情況三：查詢條件用到了索引中列的精確匹配，但是中間某個條件未提供。`

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

此時索引使用情況和情況二相同，因為title未提供，所以查詢只用到了索引的第一列，而後面的from_date雖然也在索引中，但是由於title不存在而無法和左前綴連接，因此需要對結果進行掃描過濾from_date（這裡由於emp_no唯一，所以不存在掃描）。如果想讓from_date也使用索引而不是where過濾，可以增加一個輔助索引，此時上面的查詢會使用這個索引。除此之外，還可以使用一種稱之為“隔離列”的優化方法，將emp_no與from_date之間的“坑”填上。

首先我們看下title一共有幾種不同的值：

SELECT DISTINCT(title) FROM employees.titles;
+--------------------+
| title              |
+--------------------+
| Senior Engineer    |
| Staff              |
| Engineer           |
| Senior Staff       |
| Assistant Engineer |
| Technique Leader   |
| Manager            |
+--------------------+

只有7種。在這種成為“坑”的列值比較少的情況下，可以考慮用“IN”來填補這個“坑”從而形成最左前綴：

EXPLAIN SELECT * FROM employees.titles
WHERE emp_no='10001'
AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager')
AND from_date='1986-06-26';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 59      | NULL |    7 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

這次key_len為59，說明索引被用全了，但是從type和rows看出IN實際上執行了一個range查詢，這裡檢查了7個key。看下兩種查詢的性能比較：

SHOW PROFILES;
+----------+------------+-------------------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                         |
+----------+------------+-------------------------------------------------------------------------------+
|       10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'|
|       11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ...          |
+----------+------------+-------------------------------------------------------------------------------+

“填坑”後性能提升了一點。如果經過emp_no篩選後余下很多數據，則後者性能優勢會更加明顯。當然，如果title的值很多，用填坑就不合適了，必須建立輔助索引。

在這裡引出輔助索引的概念和作用

`情況四：查詢條件沒有指定索引第一列。`

EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26';
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | titles | ALL  | NULL          | NULL | NULL    | NULL | 443308 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

由於不是最左前綴，索引這樣的查詢顯然用不到索引。

`情況五：匹配某列的前綴字符串。`

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 56      | NULL |    1 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

此時可以用到索引,如果通配符%不出現在開頭，則可以用到索引，但根據具體情況不同可能只會用其中一個前綴。

`情況六：范圍查詢`

EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 4       | NULL |   16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

范圍列可以用到索引（必須是最左前綴），但是范圍列後面的列無法用到索引。同時，索引最多用於一個范圍列，因此如果查詢條件中有兩個范圍列則無法全用到索引。

EXPLAIN SELECT * FROM employees.titles
WHERE emp_no < 10010'
AND title='Senior Engineer'
AND from_date BETWEEN '1986-01-01' AND '1986-12-31';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 4       | NULL |   16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

可以看到索引對第二個范圍索引無能為力。這裡特別要說明MySQL一個有意思的地方，那就是僅用explain可能無法區分范圍索引和多值匹配，因為在type中這兩者都顯示為range。同時，用了“between”並不意味著就是范圍查詢，例如下面的查詢：

EXPLAIN SELECT * FROM employees.titles
WHERE emp_no BETWEEN '10001' AND '10010'
AND title='Senior Engineer'
AND from_date BETWEEN '1986-01-01' AND '1986-12-31';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 59      | NULL |   16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

看起來是用了兩個范圍查詢，但作用於emp_no上的“BETWEEN”實際上相當於“IN”，也就是說emp_no實際是多值精確匹配。可以看到這個查詢用到了索引全部三個列。因此在MySQL中要謹慎地區分多值匹配和范圍匹配，否則會對MySQL的行為產生困惑。

`情況七：查詢條件中含有函數或表達式。`

很不幸，如果查詢條件中含有函數或表達式，則MySQL不會為這列使用索引（雖然某些在數學意義上可以使用）。例如：

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

雖然這個查詢和情況五中功能相同，但是由於使用了函數left，則無法為title列應用索引，而情況五中用LIKE則可以。再如：

EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000';
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | titles | ALL  | NULL          | NULL | NULL    | NULL | 443308 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

顯然這個查詢等價於查詢emp_no為10001的函數，但是由於查詢條件是一個表達式，MySQL無法為其使用索引。看來MySQL還沒有智能到自動優化常量表達式的程度，因此在寫查詢語句時盡量避免表達式出現在查詢中，而是先手工私下代數運算，轉換為無表達式的查詢語句。

`索引選擇性與前綴索引`

既然索引可以加快查詢速度，那麼是不是只要是查詢語句需要，就建上索引？答案是否定的。因為索引雖然加快了查詢速度，但索引也是有代價的：索引文件本身要消耗存儲空間，同時索引會加重插入、刪除和修改記錄時的負擔，另外，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），則開辟一個新的頁（節點）。

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

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

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

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

因此，只要可以，請盡量在InnoDB上采用自增字段做主鍵。

`後記`

。

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

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