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

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

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

MyISAM 一種非事務(wù)性的存儲(chǔ)引擎，是MySQL 5.5之前版本默認(rèn)的存儲(chǔ)引擎。

InnoDB  ***的事務(wù)性存儲(chǔ)引擎，從5.5版開(kāi)始成為MySQL默認(rèn)的引擎。

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

注意：

從5.5版本開(kāi)始，MySQL表的默認(rèn)存儲(chǔ)引擎從MyISAM換成InnoDB，將會(huì)使用戶(hù)安裝那些依賴(lài)默認(rèn)設(shè)置或者專(zhuān)門(mén)為MyISAM編寫(xiě)的軟件包時(shí)帶來(lái)很大的影響。

（二）MySQL索引類(lèi)型

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

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

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

 1.B-樹(shù)

B-樹(shù)中有兩種節(jié)點(diǎn)類(lèi)型：索引節(jié)點(diǎn)和葉子節(jié)點(diǎn)。葉子節(jié)點(diǎn)是用來(lái)存儲(chǔ)數(shù)據(jù)的，而索引節(jié)點(diǎn)則用來(lái)告訴用戶(hù)存儲(chǔ)在葉子節(jié)點(diǎn)中的數(shù)據(jù)順序，并幫助用戶(hù)找到相應(yīng)的數(shù)據(jù)。

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

B-樹(shù)是一種多路搜索樹(shù)：

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

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

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

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

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

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

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

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

2.B+樹(shù)

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

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

B+樹(shù)的特性：

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

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

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

3.散列

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

4.通信R-樹(shù)

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

5.全文本

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

MySQL實(shí)現(xiàn)

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

1.MyISAM的B-樹(shù)

MyISAM存儲(chǔ)引擎使用B-樹(shù)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)主碼索引、唯一索引以及非主碼索引。在MyISAM實(shí)現(xiàn)數(shù)據(jù)目錄和數(shù)據(jù)庫(kù)模式子目錄中，用戶(hù)可以找到和每個(gè)MySQL表對(duì)應(yīng)的.MYD和.MYI文件。數(shù)據(jù)庫(kù)表上定義的索引信息就存儲(chǔ)在MYI文件中，該文件的塊大小是1024字節(jié)。這個(gè)大小是可以通過(guò)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免費(fèi)源代碼中找到，也可以查看MySQL內(nèi)部手冊(cè)。

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

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

2. InnoDB的B+樹(shù)聚簇主碼

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

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

由于InnoDB用聚簇主碼存儲(chǔ)數(shù)據(jù)，底層信息占用的磁盤(pán)空間的大小很大程度上取決于頁(yè)面的填充因子。對(duì)于按序排列的主碼，InnoDB會(huì)用16K頁(yè)面的15/16作為填充因子。對(duì)于不是按序排列的主碼，默認(rèn)情況下InnoDB會(huì)插入初始數(shù)據(jù)的時(shí)候?yàn)槊恳粋€(gè)頁(yè)面分配50%作為填充因子。

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

3.InnoDB的B-樹(shù)非主碼

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

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

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

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

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

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

InnoDB存儲(chǔ)引擎在聚簇B+樹(shù)索引中存儲(chǔ)主碼：但在InnoDB內(nèi)部還是使用內(nèi)存中的散列表來(lái)更高效地進(jìn)行主碼查詢(xún)。這個(gè)機(jī)制有InnoDB存儲(chǔ)引擎來(lái)管理，用戶(hù)只能通過(guò)innodb_adaptive_hash_index配置項(xiàng)來(lái)選擇是否啟用這個(gè)唯一的配置選項(xiàng)。