MySQL數(shù)據(jù)庫(kù)有如下幾種常見的索引類型：

• BTree索引
• 哈希索引
• 全文索引

索引的本質(zhì)

MySQL官方對(duì)索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。提取句子主干，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。
最基本的查詢算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。
每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應(yīng)用于二叉查找樹上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

BTree索引

B-Tree和B+Tree

（1）B-Tree

為了描述B-Tree，首先定義一條數(shù)據(jù)記錄為一個(gè)二元組[key, data]，key為記錄的鍵值，對(duì)于不同數(shù)據(jù)記錄，key是互不相同的；data為數(shù)據(jù)記錄除key外的數(shù)據(jù)。那么B-Tree是滿足下列條件的數(shù)據(jù)結(jié)構(gòu)：

1. d為大于1的一個(gè)正整數(shù)，稱為B-Tree的度。
2. h為一個(gè)正整數(shù)，稱為B-Tree的高度。
3. 每個(gè)非葉子節(jié)點(diǎn)由n-1個(gè)key和n個(gè)指針組成，其中d<=n<=2d。
4. 每個(gè)葉子節(jié)點(diǎn)最少包含一個(gè)key和兩個(gè)指針，最多包含2d-1個(gè)key和2d個(gè)指針，葉節(jié)點(diǎn)的指針均為null 。
5. 所有葉節(jié)點(diǎn)具有相同的深度，等于樹高h(yuǎn)。
6. key和指針互相間隔，節(jié)點(diǎn)兩端是指針。
7. 一個(gè)節(jié)點(diǎn)中的key從左到右非遞減排列。
8. 所有節(jié)點(diǎn)組成樹結(jié)構(gòu)。
9. 每個(gè)指針要么為null，要么指向另外一個(gè)節(jié)點(diǎn)。

B-Tree示意圖

B-Tree特性：一個(gè)度為d的B-Tree，設(shè)其索引N個(gè)key，則其樹高h(yuǎn)的上限為logd((N+1)/2)，檢索一個(gè)key，其查找節(jié)點(diǎn)個(gè)數(shù)的漸進(jìn)復(fù)雜度為O(logdN)

（2）B+Tree

MySQL就普遍使用B+Tree實(shí)現(xiàn)其索引結(jié)構(gòu)，與B-Tree相比，B+Tree有以下不同點(diǎn)：

1. 每個(gè)節(jié)點(diǎn)的指針上限為2d而不是2d+1。

2. 內(nèi)節(jié)點(diǎn)不存儲(chǔ)data，只存儲(chǔ)key；葉子節(jié)點(diǎn)不存儲(chǔ)指針。
   圖3是一個(gè)簡(jiǎn)單的B+Tree示意。

   
   
   B+Tree示意
   
   

   一般在數(shù)據(jù)庫(kù)系統(tǒng)或文件系統(tǒng)中使用的B+Tree結(jié)構(gòu)都在經(jīng)典B+Tree的基礎(chǔ)上進(jìn)行了優(yōu)化，增加了順序訪問指針，示例如下：

   
   
   帶有順序訪問指針的B+Tree
   
   做這個(gè)優(yōu)化的目的是為了提高區(qū)間訪問的性能，例如上圖中如果要查詢key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率。

為什么使用B-Tree（B+Tree）

在計(jì)算機(jī)存儲(chǔ)介質(zhì)中，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理。

預(yù)讀的長(zhǎng)度一般為頁(yè)（page）的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱為一頁(yè)（在許多操作系統(tǒng)中，頁(yè)得大小通常為4k），主存和磁盤以頁(yè)為單位交換數(shù)據(jù)。

根據(jù)B-Tree的定義，可知檢索一次最多需要訪問h個(gè)節(jié)點(diǎn)。數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)者巧妙利用了磁盤預(yù)讀原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次I/O就可以完全載入。為了達(dá)到這個(gè)目的，在實(shí)際實(shí)現(xiàn)B-Tree還需要使用如下技巧：

• 每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(duì)齊的，就實(shí)現(xiàn)了一個(gè)node只需一次I/O。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過(guò)100，因此h非常?。ㄍǔ２怀^(guò)3）。綜上所述，用B-Tree作為索引結(jié)構(gòu)效率是非常高的。

而紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無(wú)法利用局部性，所以紅黑樹的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。

上文還說(shuō)過(guò)，B+Tree更適合外存索引，原因和內(nèi)節(jié)點(diǎn)出度d有關(guān)。從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于節(jié)點(diǎn)內(nèi)key和data的大?。?/p>

dmax = floor(pagesize / (keysize + datasize + pointsize))   (pagesize – dmax >= pointsize)

或

dmax = floor(pagesize / (keysize + datasize + pointsize)) – 1   (pagesize – dmax < pointsize)

floor表示向下取整。由于B+Tree內(nèi)節(jié)點(diǎn)去掉了data域，因此可以擁有更大的出度，擁有更好的性能。

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

在MySQL中，索引屬于存儲(chǔ)引擎級(jí)別的概念，不同存儲(chǔ)引擎對(duì)索引的實(shí)現(xiàn)方式是不同的，本文主要討論MyISAM和InnoDB兩個(gè)存儲(chǔ)引擎的索引實(shí)現(xiàn)方式。

MyISAM索引實(shí)現(xiàn)

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。下圖是MyISAM索引的原理圖：

MyISAM主索引結(jié)構(gòu)

MyISAM輔助索引結(jié)構(gòu)

InnoDB索引實(shí)現(xiàn)

雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同。

• 第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。
  

  InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖
  
  上圖是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄，這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類型為長(zhǎng)整形。

• 第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。換句話說(shuō)，InnoDB的所有輔助索引都引用主鍵作為data域。
  

  InnoDB輔助索引
  
  這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。

了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助，例如知道了InnoDB的索引實(shí)現(xiàn)后，就很容易明白為什么不建議使用過(guò)長(zhǎng)的字段作為主鍵，因?yàn)樗休o助索引都引用主索引，過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大。再例如，用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵則是一個(gè)很好的選擇。

InnoDB的主鍵選擇與插入優(yōu)化

在使用InnoDB存儲(chǔ)引擎時(shí)，如果沒有特別的需要，請(qǐng)永遠(yuǎn)使用一個(gè)與業(yè)務(wù)無(wú)關(guān)的自增字段作為主鍵。

上文討論過(guò)InnoDB的索引實(shí)現(xiàn)，InnoDB使用聚集索引，數(shù)據(jù)記錄本身被存于主索引（一顆B+Tree）的葉子節(jié)點(diǎn)上。這就要求同一個(gè)葉子節(jié)點(diǎn)內(nèi)（大小為一個(gè)內(nèi)存頁(yè)或磁盤頁(yè)）的各條數(shù)據(jù)記錄按主鍵順序存放，因此每當(dāng)有一條新的記錄插入時(shí)，MySQL會(huì)根據(jù)其主鍵將其插入適當(dāng)?shù)墓?jié)點(diǎn)和位置，如果頁(yè)面達(dá)到裝載因子（InnoDB默認(rèn)為15/16），則開辟一個(gè)新的頁(yè)（節(jié)點(diǎn)）。

如果表使用自增主鍵，那么每次插入新的記錄，記錄就會(huì)順序添加到當(dāng)前索引節(jié)點(diǎn)的后續(xù)位置，當(dāng)一頁(yè)寫滿，就會(huì)自動(dòng)開辟一個(gè)新的頁(yè)。如下圖所示：

這樣就會(huì)形成一個(gè)緊湊的索引結(jié)構(gòu)，近似順序填滿。由于每次插入時(shí)也不需要移動(dòng)已有數(shù)據(jù)，因此效率很高，也不會(huì)增加很多開銷在維護(hù)索引上。

如果使用非自增主鍵（如果身份證號(hào)或?qū)W號(hào)等），由于每次插入主鍵的值近似于隨機(jī)，因此每次新紀(jì)錄都要被插到現(xiàn)有索引頁(yè)得中間某個(gè)位置：

此時(shí)MySQL不得不為了將新記錄插到合適位置而移動(dòng)數(shù)據(jù)，甚至目標(biāo)頁(yè)面可能已經(jīng)被回寫到磁盤上而從緩存中清掉，此時(shí)又要從磁盤上讀回來(lái)，這增加了很多開銷，同時(shí)頻繁的移動(dòng)、分頁(yè)操作造成了大量的碎片，得到了不夠緊湊的索引結(jié)構(gòu)，后續(xù)不得不通過(guò)OPTIMIZE TABLE來(lái)重建表并優(yōu)化填充頁(yè)面。

因此，請(qǐng)盡量在InnoDB上采用自增字段做主鍵。

主索引和輔助索引對(duì)比

• 主索引鍵不允許重復(fù)，輔助索引鍵允許重復(fù)

• 主索引是稀疏索引，輔助索引是稠密索引

• 主索引索引的順序就是數(shù)據(jù)的物理存儲(chǔ)順序，而輔助索引索引順序與物理存儲(chǔ)順序不同

• 主索引可以在B+樹的葉節(jié)點(diǎn)上直接找到數(shù)據(jù)且對(duì)主鍵的排序查找和范圍查找很快，而輔助索引搜索需要檢索兩遍索引，首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄（對(duì)于InnoDB而言）

• 輔助索引適用于聚集文件，假設(shè)關(guān)系R和關(guān)系S存在多對(duì)一的關(guān)系，當(dāng)需要將關(guān)系R中每一個(gè)元組和關(guān)系S中每一個(gè)元組存在一起，就需要輔助索引

聚集索引的優(yōu)點(diǎn)

• 可以將相關(guān)數(shù)據(jù)保存在一起
  例如實(shí)現(xiàn)電子郵箱時(shí)，可以根據(jù)用戶ID來(lái)聚集數(shù)據(jù)，這樣只需要從磁盤讀取少量的數(shù)據(jù)頁(yè)就能獲取某個(gè)用戶的全部郵件。如果沒有使用聚集索引，則每封郵件可能導(dǎo)致一次IO

• 數(shù)據(jù)訪問更快
  聚集索引將數(shù)據(jù)和索引放在同一個(gè)B-Tree中，因此獲取數(shù)據(jù)速度更快

• 使用覆蓋索引掃描的查詢可以直接舒勇葉節(jié)點(diǎn)的主鍵值

聚集索引的缺點(diǎn)

• 聚集數(shù)據(jù)極大提高了IO密集型應(yīng)用的性能，但如果數(shù)據(jù)全部放在內(nèi)存中，則聚集索引會(huì)失去優(yōu)勢(shì)

• 插入速度嚴(yán)重依賴于插入順序。按照主鍵的順序插入是加載數(shù)據(jù)到InnoDB最快的方式。但如果不是按照主鍵的順序加載，那么在加載完成后最好使用OPTIMIZE TABLE 命令重新組織表

• 更新聚集索引的代價(jià)很高

• 聚集索引的表在插入新行，或者主鍵被更新需要移動(dòng)的時(shí)候，可能面臨頁(yè)分裂的問題

• 聚族索引可能導(dǎo)致全表掃描變慢

• 二級(jí)索引（非聚集索引）可能比想象中的大，因?yàn)槎?jí)索引的葉子結(jié)點(diǎn)包含了主鍵，這也是為何主鍵不能過(guò)長(zhǎng)的原因

• 二級(jí)索引訪問數(shù)據(jù)需要兩次索引查找

參考文章

MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理
數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)