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

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

索引的本質(zhì)

MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)颈渊。提取句子主干杆融，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)袁串。
最基本的查詢算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(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ù)之外，數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)幔嫂，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)辆它，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)履恩，就是索引娩井。

BTree索引

B-Tree和B+Tree

（1）B-Tree

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

1. d為大于1的一個正整數(shù)，稱為B-Tree的度而涉。
2. h為一個正整數(shù)著瓶，稱為B-Tree的高度。
3. 每個非葉子節(jié)點由n-1個key和n個指針組成啼县，其中d<=n<=2d材原。
4. 每個葉子節(jié)點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針季眷，葉節(jié)點的指針均為null 余蟹。
5. 所有葉節(jié)點具有相同的深度，等于樹高h子刮。
6. key和指針互相間隔威酒，節(jié)點兩端是指針窑睁。
7. 一個節(jié)點中的key從左到右非遞減排列。
8. 所有節(jié)點組成樹結(jié)構(gòu)葵孤。
9. 每個指針要么為null担钮，要么指向另外一個節(jié)點。

B-Tree示意圖

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

（2）B+Tree

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

1. 每個節(jié)點的指針上限為2d而不是2d+1司澎。

2. 內(nèi)節(jié)點不存儲data欺缘，只存儲key；葉子節(jié)點不存儲指針挤安。
   圖3是一個簡單的B+Tree示意谚殊。

   
   
   B+Tree示意
   
   

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

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

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

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

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

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

• 每次新建節(jié)點時庄拇，直接申請一個頁的空間注服，這樣就保證一個節(jié)點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的措近，就實現(xiàn)了一個node只需一次I/O溶弟。

B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存），漸進復(fù)雜度為O(h)=O(logdN)瞭郑。一般實際應(yīng)用中辜御，出度d是非常大的數(shù)字，通常超過100屈张，因此h非常星苋ā（通常不超過3）。綜上所述阁谆，用B-Tree作為索引結(jié)構(gòu)效率是非常高的菜拓。

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

上文還說過，B+Tree更適合外存索引姨谷，原因和內(nèi)節(jié)點出度d有關(guān)逗宁。從上面分析可以看到，d越大索引的性能越好梦湘，而出度的上限取決于節(jié)點內(nèi)key和data的大邢箍拧：

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é)點去掉了data域，因此可以擁有更大的出度哼拔，擁有更好的性能引有。

MySQL索引實現(xiàn)

在MySQL中，索引屬于存儲引擎級別的概念倦逐，不同存儲引擎對索引的實現(xiàn)方式是不同的譬正，本文主要討論MyISAM和InnoDB兩個存儲引擎的索引實現(xiàn)方式。

MyISAM索引實現(xiàn)

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

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

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

InnoDB索引實現(xiàn)

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

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

  InnoDB主索引（同時也是數(shù)據(jù)文件）的示意圖
  
  上圖是InnoDB主索引（同時也是數(shù)據(jù)文件）的示意圖彰亥，可以看到葉節(jié)點包含了完整的數(shù)據(jù)記錄咧七，這種索引叫做聚集索引。因為InnoDB的數(shù)據(jù)文件本身要按主鍵聚集剩愧，所以InnoDB要求表必須有主鍵（MyISAM可以沒有）猪叙，如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵仁卷，如果不存在這種列穴翩，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節(jié)锦积，類型為長整形芒帕。

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

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

了解不同存儲引擎的索引實現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助橙垢，例如知道了InnoDB的索引實現(xiàn)后垛叨，就很容易明白為什么不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引柜某，過長的主索引會令輔助索引變得過大嗽元。再例如，用非單調(diào)的字段作為主鍵在InnoDB中不是個好主意喂击，因為InnoDB數(shù)據(jù)文件本身是一顆B+Tree剂癌，非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效翰绊，而使用自增字段作為主鍵則是一個很好的選擇佩谷。

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

在使用InnoDB存儲引擎時，如果沒有特別的需要监嗜，請永遠使用一個與業(yè)務(wù)無關(guān)的自增字段作為主鍵谐檀。

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

如果表使用自增主鍵乍惊，那么每次插入新的記錄杜秸，記錄就會順序添加到當(dāng)前索引節(jié)點的后續(xù)位置，當(dāng)一頁寫滿润绎，就會自動開辟一個新的頁撬碟。如下圖所示：

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

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

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

因此，請盡量在InnoDB上采用自增字段做主鍵狱从。

主索引和輔助索引對比

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

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

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

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

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

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

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

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

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

聚集索引的缺點

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

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

• 更新聚集索引的代價很高

• 聚集索引的表在插入新行，或者主鍵被更新需要移動的時候缎罢，可能面臨頁分裂的問題

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

• 二級索引（非聚集索引）可能比想象中的大伊群，因為二級索引的葉子結(jié)點包含了主鍵，這也是為何主鍵不能過長的原因

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

參考文章

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