MySQL索引背後的資料結構與演算法原理詳解
- 高洛峰原創
- 2017-01-16 15:12:231018瀏覽
摘要
本文以MySQL資料庫為研究對象，討論與資料庫索引相關的一些主題。特別需要說明的是，MySQL支援許多儲存引擎，而各種儲存引擎對索引的支援也各不相同，因此MySQL資料庫支援多種索引類型，如BTree索引，雜湊索引，全文索引等等。為了避免混亂，本文將只關注BTree索引，因為這是平常使用MySQL時主要打交道的索引，至於雜湊索引和全文索引本文暫不討論。
文章主要內容分為三個部分。
第一部分主要從資料結構及演算法理論層面討論MySQL資料庫索引的數理基礎。
第二部分結合MySQL資料庫中MyISAM和InnoDB資料儲存引擎中索引的架構實現討論聚集索引、非聚集索引及覆蓋索引等主題。
第三部分根據上面的理論基礎，討論MySQL中高效能使用索引的策略。
資料結構及演算法基礎
索引的本質
MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效取得資料的資料結構。提取句子主幹，就可以得到索引的本質：索引是資料結構。
我們知道，資料庫查詢是資料庫最主要的功能之一。我們都希望查詢資料的速度能盡可能的快，因此資料庫系統的設計者會從查詢演算法的角度來優化。最基本的查詢演算法當然是順序查找（linear search），這種複雜度為O(n)的演算法在資料量大時顯然是糟糕的，好在電腦科學的發展提供了很多更優秀的查找演算法，例如二分查找（binary search）、二元樹查找（binary tree search）等。如果稍微分析一下會發現，每種查找演算法都只能應用於特定的資料結構之上，例如二分查找要求被檢索資料有序，而二叉樹查找只能應用於二叉查找樹上，但是資料本身的組織結構不可能完全滿足各種資料結構（例如，理論上不可能同時將兩列都按順序進行組織），所以，在資料之外，資料庫系統還維護著滿足特定查找演算法的資料結構，這些資料結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找演算法。這種資料結構，就是索引。
看一個例子：
圖1
圖1展示了一種可能的索引方式。左邊是資料表，一共有兩列七筆記錄，最左邊的是資料記錄的實體位址（注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二元查找樹，每個節點分別包含索引鍵值和一個指向對應資料記錄物理位址的指針，這樣就可以運用二叉查找在O(log2n)的複雜度內取得到對應資料。
雖然這是一個貨真價實的索引，但是實際的資料庫系統幾乎沒有使用二元查找樹或其進化品種紅黑樹（red-black tree）實現的，原因會在下文介紹。
B-Tree和B+Tree
目前大部分資料庫系統及檔案系統都採用B-Tree或其變種B+Tree作為索引結構，在本文的下一節會結合記憶體原理及電腦存取原理討論為什麼B-Tree和B+Tree在被如此廣泛用於索引，這一節先單純地從資料結構角度描述它們。
B-Tree
為了描述B-Tree，首先定義一條數據記錄為一個二元組[key, data]，key為記錄的鍵值，對於不同數據記錄，key是互不相同的；data為數據記錄除key外的數據。則B-Tree是滿足下列條件的資料結構：
1. d為大於1的一個正整數，稱為B-Tree的度數。
2. h為一個正整數，稱為B-Tree的高度。
3. 每個非葉節點由n-1個key和n個指標組成，其中d
4. 每個葉子節點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節點的指針均為null 。
5. 所有葉節點具有相同的深度，等於樹高h。
6. key和指標互相間隔，節點兩端是指標。
7. 一個節點中的key從左到右非遞減排列。
8. 所有節點組成樹結構。
9. 每個指標要麼為null，要麼指向另外一個節點。
10. 如果某個指標在節點node最左邊且不為null，則其指向節點的所有key小於v(key1)，其中v(key1)為node的第一個key的值。
11. 如果某個指標在節點node最右邊且不為null，則其指向節點的所有key大於v(keym)，其中v(keym)為node的最後一個key的值。
12. 如果某個指標在節點node的左右相鄰key分別是keyi和keyi+1且不為null，則其指向節點的所有key小於v(keyi+1)且大於v(keyi)。
圖2是一個d=2的B-Tree示意圖。
圖2
由於B-Tree的特性，在B-Tree中按key檢索資料的演算法非常直觀：先從根節點進行二分查找，如果找到則傳回對應節點的data，否則對應區間的指針指向的節點遞歸進行查找，直到找到節點或找到null指針，前者查找成功，後者查找失敗。在B-Tree上尋找演算法的偽代碼如下：
BTree_Search(node, key)
{
if(node == null) return null;
foreach(node.key)
{
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);關於B-Tree有一系列有趣的性質，例如一個度為d的B-Tree，設其索引N個key，則其樹高h的上限為logd ((N+1)/2)，檢索一個key，其找出節點個數的漸進複雜度為O(logdN)。從這點可以看出，B-Tree是一個非常有效率的索引資料結構。
另外，由於插入刪除新的資料記錄會破壞B-Tree的性質，因此在插入刪除時，需要對樹進行一個分裂、合併、轉移等操作以保持B-Tree性質，本文不打算完整討論B -Tree這些內容，因為已經有許多資料詳細說明了B-Tree的數學性質及插入刪除演算法，有興趣的朋友可以在本文末的參考文獻一欄找到相應的資料進行閱讀。
B+Tree
B-Tree有許多變種，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實現其索引結構。
與B-Tree相比，B+Tree有以下不同點：
1. 每個節點的指標上限為2d而不是2d+1。
2. 內節點不儲存data，只儲存key；葉子節點不儲存指標。
圖3是一個簡單的B+Tree示意。
圖3
由於並不是所有節點都具有相同的域，因此B+Tree中葉節點和內節點一般大小不同。這點與B-Tree不同，雖然B-Tree中不同節點存放的key和指標可能數量不一致，但是每個節點的域和上限是一致的，所以在實現中B-Tree往往對每個節點申請同等大小的空間。
一般來說，B+Tree比B-Tree更適合實現外部儲存索引結構，具體原因與外部記憶體原理及電腦存取原理有關，將在下面討論。
帶有順序存取指標的B+Tree
一般在資料庫系統或檔案系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了最佳化，增加了順序存取指標。
圖4
如圖4所示，在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優化的目的是為了提高區間訪問的性能，例如圖4中如果要查詢key為從18到49的所有數據記錄，當找到18後，只需順著節點和指針順序遍歷就可以一次性訪問到所有資料節點，極大提到了區間查詢效率。
這一節對B-Tree和B+Tree進行了一個簡單的介紹，下一節結合記憶體存取原理介紹為什麼目前B+Tree是資料庫系統實作索引的首選資料結構。
為什麼要使用B-Tree（B+Tree）
上文說過，紅黑樹等資料結構也可以用來實現索引，但是檔案系統及資料庫系統普遍採用B-/+Tree作為索引結構，這一節將結合電腦組成原理相關知識討論B-/+Tree作為索引的理論基礎。
一般來說，索引本身也很大，不可能全部儲存在記憶體中，因此索引往往以索引檔案的形式儲存的磁碟上。這樣的話，索引查找過程中就要產生磁碟I/O消耗，相對於記憶體存取，I/O存取的消耗要高幾個數量級，所以評價一個資料結構作為索引的優劣最重要的指標就是在查找過程中磁碟I/O操作次數的漸進複雜度。換句話說，索引的結構組織要盡量減少查找過程中磁碟I/O的存取次數。以下先介紹記憶體和磁碟存取原理，然後再結合這些原理分析B-/+Tree作為索引的效率。
主存存取原理
目前電腦使用的主存基本上都是隨機讀寫記憶體（RAM），現代RAM的結構和存取原理比較複雜，這裡本文拋卻具體差別，抽像出一個十分簡單的存取模型來說明RAM的工作原理。
圖5
從抽象角度看，主記憶體是一系列的儲存單元所組成的矩陣，每個儲存單元儲存固定大小的資料。每個儲存單元有唯一的位址，現代主存的編址規則比較複雜，這裡將其簡化成一個二維位址：透過一個行位址和一個欄位位址可以唯一定位到一個儲存單元。圖5展示了一個4 x 4的主存模型。
主存的存取過程如下：
當系統需要讀取主記憶體時，則將位址訊號放到位址匯流排上傳給主存，主存讀到位址訊號後，解析訊號並定位到指定儲存單元，然後將此儲存單元資料放到資料匯流排上，供其它元件讀取。
寫入主記憶體的過程類似，系統將要寫入單元位址和資料分別放在位址匯流排和資料匯流排上，主記憶體讀取兩個匯流排的內容，做對應的寫入作業。
這裡可以看出，主記憶體訪問的時間僅與訪問次數呈線性關係，因為不存在機械操作，兩次訪問的資料的「距離」不會對時間有任何影響，例如，先取A0再取A1和先取A0再取D3的時間消耗是一樣的。
磁碟存取原理
上文說過，索引一般以檔案形式儲存在磁碟上，索引檢索需要磁碟I/O操作。與主記憶體不同，磁碟I/O存在機械運動耗費，因此磁碟I/O的時間消耗是巨大的。
圖6是磁碟的整體結構示意圖。
圖6
一個磁碟由大小相同且同軸的圓形磁碟片組成，磁碟可以轉動（各個磁碟必須同步轉動）。在磁碟的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁碟的內容。磁頭不能轉動，但是可以沿著磁碟半徑方向運動（實際上是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。
圖7是磁碟結構的示意圖。
圖7
盤片被分割成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁軌組成一個柱面。磁軌被沿著半徑線劃分成一個小的段，每個段叫做一個扇區，每個扇區是磁碟的最小儲存單元。為了簡單起見，我們下面假設磁碟只有一個碟片和一個磁頭。
當需要從磁碟讀取資料時，系統會將資料邏輯位址傳給磁碟，磁碟的控制電路會依照定址邏輯將邏輯位址翻譯成實體位址，即確定要讀取的資料在哪個磁道，哪個磁區。為了讀取這個磁區的數據，需要將磁頭放到這個磁區上方，為了實現這一點，磁頭需要移動對準相應磁軌，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁碟旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
局部性原理與磁碟預讀
由於儲存媒體的特性，磁碟本身存取就比主存慢很多，再加上機械運動耗費，磁碟的存取速度往往是主存的百分之分之一，因此為了提高效率，要盡量減少磁碟I/O。為了達到這個目的，磁碟往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁碟也會從這個位置開始，順序向後讀取一定長度的資料放入記憶體。這樣做的理論依據是電腦科學中著名的局部性原理：
當一個資料被用到時，其附近的資料也通常會馬上被使用。
程式運作期間所需的資料通常比較集中。
由於磁碟順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對於具有局部性的程式來說，預讀可以提高I/O效率。
預讀的長度一般為頁（page）的整數倍。頁是電腦管理記憶體的邏輯區塊，硬體及作業系統往往將主記憶體和磁碟儲存區分割為連續的大小相等的區塊，每個儲存區塊稱為一頁（在許多作業系統中，頁得大小通常為4k），主存和磁碟以頁為單位交換資料。當程式要讀取的資料不在主記憶體時，會觸發一個缺頁異常，此時系統會向磁碟發出讀盤訊號，磁碟會找到資料的起始位置並向後連續讀取一頁或幾頁載入記憶體中，然後異常返回，程式繼續運行。
B-/+Tree索引的效能分析
到這裡終於可以分析B-/+Tree索引的效能了。
上文說過一般使用磁碟I/O次數評估索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要存取h個節點。資料庫系統的設計者巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B-Tree還需要使用以下技巧：
每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁裡，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O（根節點常駐記憶體），漸進複雜度為O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小（通常不超過3）。
綜上所述，以B-Tree作為索引結構效率是非常高的。
而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點（父子）物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進複雜度也為O(h)，效率明顯比B-Tree差很多。
上文也說過，B+Tree比較適合外存索引，原因和內節點出度d有關。從上面分析可以看到，d越大索引的效能越好，而出度的上限取決於節點內key和data的大小：
dmax = floor(pagesize / (keysize + datasize + pointsize)) (pagesize – dmax >= pointsize)
或
dmax = floor(pagesize / (keysize + datasize + pointsize)) – 1 (pagesize – dmax
floor表示向下取整。由於B+Tree內節點去掉了data域，因此可以擁有更大的出度，並且有更好的效能。
這一章從理論角度討論了與索引相關的資料結構與演算法問題，下一章將討論B+Tree是如何具體實現為MySQL中索引，同時將結合MyISAM和InnDB儲存引擎介紹非聚集索引和聚集索引兩種不同的索引實作形式。
MySQL索引實作
在MySQL中，索引屬於儲存引擎層級的概念，不同儲存引擎對索引的實作方式是不同的，本文主要討論MyISAM和InnoDB兩個儲存引擎的索引實作方式。
MyISAM索引實作
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是資料記錄的位址。下圖為MyISAM索引的原理圖：
圖8
這裡設表一共有三列，假設我們以Col1為主鍵，則圖8是一個MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引檔案僅保存資料記錄的位址。在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何區別，只是主索引要求key是唯一的，而輔助索引的key可以重複。如果我們在Col2上建立一個輔助索引，則此索引的結構如下圖所示：
圖9
同樣也是一顆B+Tree，data域保存資料記錄的位址。因此，MyISAM中索引檢索的演算法為先依照B+Tree搜尋演算法搜尋索引，若指定的Key存在，則取出其data域的值，然後以data域的值為位址，讀取對應資料記錄。
MyISAM的索引方式也叫做「非聚集」的，之所以這麼稱呼是為了與InnoDB的聚集索引區分。
InnoDB索引實現
雖然InnoDB也使用B+Tree作為索引結構，但具體實現方式卻與MyISAM截然不同。
第一個重大差異是InnoDB的資料檔本身就是索引檔。從上文知道，MyISAM索引檔案和資料檔案是分離的，索引檔案僅保存資料記錄的位址。而在InnoDB中，表格資料檔案本身就是依照B+Tree組織的索引結構，這棵樹的葉節點data域保存了完整的資料記錄。這個索引的key是資料表的主鍵，因此InnoDB表資料檔本身就是主索引。
圖10
图10是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：
图11
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
下一章将具体讨论这些与索引有关的优化策略。
索引使用策略及优化
MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础，实际上一旦理解了索引背后的机制，那么选择高性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。
示例数据库
为了讨论索引策略，需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一：employees。这个数据库关系复杂度适中，且数据量较大。下图是这个数据库的E-R关系图（引用自MySQL官方手册）：
图12
MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库，并提供了下载地址和导入方法，如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。
最左前缀原理与相关优化
高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关，下面通过例子说明最左前缀原理。
这里先说一下联合索引的概念。在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组
以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表的主索引为
ALTER TABLE employees.titles DROP INDEX emp_no;
这样就可以专心分析索引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 | | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
很明显，当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“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 | | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
效果是一样的。
情况二：最左前缀匹配。
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 | | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
当查询条件精确匹配索引的左边连续一个或几个列时，如
情况三：查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。
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过滤，可以增加一个辅助索引
首先我们看下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 | +-------------+
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權威指南（MySQL5權威指導The Definitive Guide to MySQL5）；人民郵電出版社，2006
[3] 姜承堯著；MySQL技術內幕-InnoDB儲存引擎；機械工業出版社，2011
[4] D Comer, Ubiquitous B-tree; ACM Computinging 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參考手冊– http://dev.mysql.com/doc/refman/5.1/zh/index.html
更多MySQL索引背後的資料結構及演算法原理詳解相關文章請注意相關文章請關注PHP中文網！