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

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

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

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

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

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

注意：

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

（二）MySQL索引類型

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

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

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

 1.B-樹

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

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

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

 (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]的子樹，p[M]指向的關(guān)鍵字大于K[m-1]的子樹;

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

2.B+樹

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

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

B+樹的特性：

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

4.通信R-樹

R-樹數(shù)據(jù)結(jié)構(gòu)支持基于數(shù)據(jù)類型對幾何數(shù)據(jù)進(jìn)行管理。目前只有MyISAM使用R-樹實(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)中并沒有什么實(shí)用的價(jià)值，因?yàn)榇笠?guī)模系統(tǒng)有很多專門的文件檢索產(chǎn)品。所以不用在介紹。

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

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

1.MyISAM的B-樹

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

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

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

2. InnoDB的B+樹聚簇主碼

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

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

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

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

3.InnoDB的B-樹非主碼

InnoDB中的非主碼索引使用了B-樹數(shù)據(jù)結(jié)構(gòu)，但I(xiàn)nnoDB中的B-樹結(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)度可以表示為直接鍵查找的簡單性，散列索引的相似度模式匹配查詢比直接查詢慢。也可以為MEMORY引擎指定一個(gè)B-樹索引實(shí)現(xiàn)。

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

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

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

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