（一）關(guān)于存儲引擎      

創(chuàng)建合適的索引是SQL性能調(diào)優(yōu)中最重要的技術(shù)之一。在學習創(chuàng)建索引之前，要先了解MySql的架構(gòu)細節(jié)，包括在硬盤上面如何組織的，索引和內(nèi)存用法和操作方式，以及存儲引擎的差異如何影響到索引的選擇。

MySQL有很多種衍生版本，這些衍生版本支持更多不同種類的存儲引擎。本文主要討論三種MySQL引擎。

MyISAM 一種非事務性的存儲引擎，是MySQL 5.5之前版本默認的存儲引擎。

InnoDB  ***的事務性存儲引擎，從5.5版開始成為MySQL默認的引擎。

Memory 基于內(nèi)存的，非事務性的以及非持久性的存儲引擎。

注意：

從5.5版本開始，MySQL表的默認存儲引擎從MyISAM換成InnoDB，將會使用戶安裝那些依賴默認設(shè)置或者專門為MyISAM編寫的軟件包時帶來很大的影響。

（二）MySQL索引類型

MySQL支持在所有關(guān)系數(shù)據(jù)庫表中創(chuàng)建主鍵、唯一鍵、不唯一的非主碼索引等多種類型的索引。此外MySQL還支持純文本和空間索引類型。

MySQL內(nèi)置的存儲引擎對各種索引技術(shù)有不同的實現(xiàn)方式，包括：B-樹，B+樹，R-樹以及散列類型。

索引數(shù)據(jù)結(jié)構(gòu)理論：

 1.B-樹

B-樹中有兩種節(jié)點類型：索引節(jié)點和葉子節(jié)點。葉子節(jié)點是用來存儲數(shù)據(jù)的，而索引節(jié)點則用來告訴用戶存儲在葉子節(jié)點中的數(shù)據(jù)順序，并幫助用戶找到相應的數(shù)據(jù)。

B-樹的搜索，從根節(jié)點開始，對節(jié)點內(nèi)的關(guān)鍵字有序進行二分查找，如果***則結(jié)束，否則進入查詢關(guān)鍵字所屬范圍的兒子節(jié)點，重復。直到所對應的兒子指針為空，或已經(jīng)是葉子節(jié)點。

B-樹是一種多路搜索樹：

 (1). 定義任意非葉子節(jié)點最多有M個兒子，且M>2;

 (2). 根節(jié)點的兒子數(shù)為[2,M];

 (3). 除根節(jié)點以外的非葉子節(jié)點的兒子數(shù)為[M/2,M];

 (4). 每個節(jié)點存放至少M/2-1(取上整)和至多M-1個關(guān)鍵字;

 (5). 非葉子節(jié)點的關(guān)鍵字個數(shù)=指向兒子節(jié)點的指針的個數(shù)-1;  

 (6). 非葉子節(jié)點的關(guān)鍵字：k[i]<k[i+1];

 (7). 非葉子節(jié)點的指針：p[1]，p[2]，·····，p[M]；其中p[1]指向的關(guān)鍵字小于k[1]的子樹，p[M]指向的關(guān)鍵字大于K[m-1]的子樹;

 (8). 所有的葉子節(jié)點位于同一層; 

2.B+樹

B+樹數(shù)據(jù)結(jié)構(gòu)是B-樹實現(xiàn)的增強版本。盡管B+樹支持B-樹索引的所有特性，它們之間最顯著的不同點在于B+樹中底層數(shù)據(jù)是根據(jù)被提及的索引列進行排序的。B+樹還通過葉子節(jié)點之間的附加引用來優(yōu)化掃描性能。

B+搜索和B-搜索不同，區(qū)別是B+樹只有達到葉子節(jié)點才***（B-樹可以在非葉子節(jié)點***），其性能等價于關(guān)鍵字全集做一次二分搜索。

B+樹的特性：

（1）所有關(guān)鍵字都出現(xiàn)在葉子節(jié)點的鏈表中，葉子節(jié)點相當于存儲數(shù)據(jù)的數(shù)據(jù)層。

（2）不可能在非葉子節(jié)點上***。

（3）非葉子節(jié)點相當于是葉子節(jié)點的索引，葉子節(jié)點相當于數(shù)據(jù)層。

3.散列

散列表數(shù)據(jù)結(jié)構(gòu)是一種很簡單的概念，它將一種算法應用到給定值中以在底層數(shù)據(jù)存儲系統(tǒng)中返回一個唯一的指針或位置。散列表的優(yōu)點是始終以線性時間復雜度找到需要讀取的行的位置，而不像B-樹那樣需要橫跨多層節(jié)點來確定位置。

4.通信R-樹

R-樹數(shù)據(jù)結(jié)構(gòu)支持基于數(shù)據(jù)類型對幾何數(shù)據(jù)進行管理。目前只有MyISAM使用R-樹實現(xiàn)支持空間索引，使用空間索引也有很多限制，比如只支持唯一的NOT NULL列等。

5.全文本

全文本結(jié)構(gòu)也是一種MySQL采用的基本數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)目前只有當前版本MySQL中的MyISAM存儲引擎支持。5.6版本將要在InnoDB存儲引擎中加入全文本功能。全文本索引在大型系統(tǒng)中并沒有什么實用的價值，因為大規(guī)模系統(tǒng)有很多專門的文件檢索產(chǎn)品。所以不用在介紹。

MySQL實現(xiàn)

對B-樹，B+樹和散列等數(shù)據(jù)結(jié)構(gòu)的基本概念有了一些了解之后，我們就可以開始討論MySQL通過支持它們的存儲引擎如何實現(xiàn)不同的算法。同時每種實現(xiàn)也對磁盤和內(nèi)存使用情況有不同的影響，這一點在大型數(shù)據(jù)庫系統(tǒng)中是非常重要的考慮因素。

1.MyISAM的B-樹

MyISAM存儲引擎使用B-樹數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)主碼索引、唯一索引以及非主碼索引。在MyISAM實現(xiàn)數(shù)據(jù)目錄和數(shù)據(jù)庫模式子目錄中，用戶可以找到和每個MySQL表對應的.MYD和.MYI文件。數(shù)據(jù)庫表上定義的索引信息就存儲在MYI文件中，該文件的塊大小是1024字節(jié)。這個大小是可以通過myisam-block-size系統(tǒng)變量分配。       

$  ls -1h /var/lib/mysql/book/source_words.MY*  
-rw-rw---- 1 mysql mysql  9.2M 2015-05-07 19:08  
source_words.MYD  
-rw-rw---- 1 mysql mysql  7.8M 2015-05-07 19:08  
source_words.MYI 

這些文件結(jié)構(gòu)的內(nèi)部格式可以從MySQL免費源代碼中找到，也可以查看MySQL內(nèi)部手冊。

在MyISAM中，非主碼索引的B-樹結(jié)構(gòu)存儲索引值和一個指向主碼數(shù)據(jù)的指針，這是MyISAM和InnoDB的一個顯著區(qū)別。這一點導致了兩個存儲引擎的索引的不同工作方式。

MyISAM索引是在內(nèi)存的一個公共緩存中管理的，這個緩存的大小可以通過key_buffer_size或者其他命名鍵緩存來定義。這是根據(jù)統(tǒng)計和規(guī)劃的表索引的大小來設(shè)定緩存大小時主要的考慮因素。

2. InnoDB的B+樹聚簇主碼

InnoDB存儲引擎在它的主碼索引（也被稱為聚簇主碼）中使用了B+樹，這種結(jié)構(gòu)把所有數(shù)據(jù)都和對應的主碼組織在一起，并且在葉子節(jié)點這一層上添加額外的向前和向后的指針，這樣就可以更方便地進行范圍掃描。

在文件系統(tǒng)層面，所有InnoDB數(shù)據(jù)和索引信息都默認在公共InnoDB表空間中管理，否則管理員就通過innodb_data_file_path這個變量指定文件路徑。這是一個叫ibdatal文件。

由于InnoDB用聚簇主碼存儲數(shù)據(jù)，底層信息占用的磁盤空間的大小很大程度上取決于頁面的填充因子。對于按序排列的主碼，InnoDB會用16K頁面的15/16作為填充因子。對于不是按序排列的主碼，默認情況下InnoDB會插入初始數(shù)據(jù)的時候為每一個頁面分配50%作為填充因子。

在改索引的實現(xiàn)方式中B+樹的葉子節(jié)點上是data就是數(shù)據(jù)本身，key為主鍵，如果是一般索引的話，data便會指向?qū)闹魉饕Ｔ贐+樹的每一個葉子節(jié)點上面增加一個指向相鄰葉子節(jié)點的指針，就形成了帶有順序訪問指針的B+樹。其目的是提高區(qū)間訪問的性能。

3.InnoDB的B-樹非主碼

InnoDB中的非主碼索引使用了B-樹數(shù)據(jù)結(jié)構(gòu)，但InnoDB中的B-樹結(jié)構(gòu)實現(xiàn)和MyISAM中并不一樣。在InnoDB中，非主碼索引存儲的是主碼的實際值。而MyISAM中，非主碼索引存儲的包含主碼值的數(shù)據(jù)指針。這一點很重要。首先，當定義很大的主碼的時候，InnoDB的非主碼索引可能回更大，隨著非主碼索引數(shù)量的增加，索引之間大小差別可能會變得很大。另一個不同點在于非主碼索引當前可以包含主鍵的值，并且可以不是索引必須有的部分。

4.內(nèi)存散列索引

在默認MySQL的引擎索引中，只有MEMORY引擎支持散列數(shù)據(jù)結(jié)構(gòu)，散列結(jié)構(gòu)的強度可以表示為直接鍵查找的簡單性，散列索引的相似度模式匹配查詢比直接查詢慢。也可以為MEMORY引擎指定一個B-樹索引實現(xiàn)。

5.內(nèi)存B-樹索引

對于大型MEMORY表來說，使用散列索引進行索引范圍搜索的效率很低，B-樹索引在執(zhí)行直接鍵查詢時確實比使用默認的散列索引快。根據(jù)B-樹的不同深度，B-樹索引在個別操作中的確可能比散列算法快。

6.InnoDB內(nèi)部散列索引

InnoDB存儲引擎在聚簇B+樹索引中存儲主碼：但在InnoDB內(nèi)部還是使用內(nèi)存中的散列表來更高效地進行主碼查詢。這個機制有InnoDB存儲引擎來管理，用戶只能通過innodb_adaptive_hash_index配置項來選擇是否啟用這個唯一的配置選項。