1. 引子
InnoDB存儲(chǔ)引擎支持以下幾種常見(jiàn)的索引：
?B+樹(shù)索引
?全文索引
?哈希索引
2. B+樹(shù)索引
在介紹B+樹(shù)索引之前先介紹與之密切相關(guān)的一些算法與數(shù)據(jù)結(jié)構(gòu)栏豺，幫助理解彬碱。
2.1 數(shù)據(jù)結(jié)構(gòu)與算法
2.1.1 二分查找法
二分查找法（binary search）也稱(chēng)為折半查找法，用來(lái)查找一組有序的記錄數(shù)組中的某一記錄奥洼，其基本思想是：將記錄按有序化（遞增或遞減）排列巷疼，在查找過(guò)程中采用跳躍式方式查找，即先以有序數(shù)列的中點(diǎn)位置為比較對(duì)象灵奖，如果要找的元素值小于該中點(diǎn)元素嚼沿，則將待查序列縮小為左半部分估盘，否則為右半部分。通過(guò)一次比較骡尽，將查找區(qū)間縮小一半遣妥。
2.1.2 二叉查找樹(shù)
在介紹B+樹(shù)前，需要先了解一下二叉查找樹(shù)攀细。B+樹(shù)是通過(guò)二叉查找樹(shù)箫踩，再由平衡二叉樹(shù)，B樹(shù)演化而來(lái)谭贪。相信在任何一本有關(guān)數(shù)據(jù)結(jié)構(gòu)的書(shū)中都可以找到二叉查找樹(shù)的章節(jié)境钟，二叉查找樹(shù)是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。
圖中的數(shù)字代表每個(gè)節(jié)點(diǎn)的鍵值俭识，在二叉查找樹(shù)中慨削，左子樹(shù)的鍵值總是小于根的鍵值，右子樹(shù)的鍵值總是大于根的鍵值鱼的。
二叉查找樹(shù)可以任意地構(gòu)造，同樣是2痘煤、3凑阶、5陆蟆、6咖祭、7颂碘、8這五個(gè)數(shù)字硼莽，也可以按照下圖的方式建立二叉查找樹(shù)芦昔。
此圖的平均查找次數(shù)和順序查找差不多巨缘。顯然這棵二叉查找樹(shù)的查詢效率就低了今缚。因此若想最大性能地構(gòu)造一棵二叉查找樹(shù)漫蛔，需要這棵二叉查找樹(shù)是平衡的调窍，從而引出了新的定義——平衡二叉樹(shù)宝冕，或稱(chēng)為AVL樹(shù)。
平衡二叉樹(shù)的定義如下：首先符合二叉查找樹(shù)的定義邓萨，其次必須滿足任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差為1地梨。
平衡二叉樹(shù)的查詢速度的確很快，但是維護(hù)一棵平衡二叉樹(shù)的代價(jià)是非常大的缔恳。通常來(lái)說(shuō)宝剖，需要1次或多次左旋和右旋來(lái)得到插入或更新后樹(shù)的平衡性。對(duì)于圖一所示的平衡樹(shù)歉甚，當(dāng)用戶需要插入一個(gè)新的鍵值為9的節(jié)點(diǎn)時(shí)万细，需做如圖所示的變動(dòng)：
這里通過(guò)一次左旋操作就將插入后的樹(shù)重新變?yōu)槠胶獾牧恕５怯械那闆r可能需要多次纸泄。除了插入操作赖钞，還有更新和刪除操作腰素，不過(guò)這和插入沒(méi)有本質(zhì)的區(qū)別，都是通過(guò)左旋或者右旋來(lái)完成的仁烹。因此對(duì)一棵平衡樹(shù)的維護(hù)是有一定開(kāi)銷(xiāo)的耸弄，不過(guò)平衡二叉樹(shù)多用于內(nèi)存結(jié)構(gòu)對(duì)象中，因此維護(hù)的開(kāi)銷(xiāo)相對(duì)較小卓缰。
2.1.3 B樹(shù)
B樹(shù)的結(jié)構(gòu)如下：
可以看到非葉子節(jié)點(diǎn)中也保存了數(shù)據(jù)计呈，另外黃色的部分表示指向子節(jié)點(diǎn)的指針。另外B樹(shù)相比于二叉樹(shù)的特點(diǎn)是一個(gè)節(jié)點(diǎn)可以保存多個(gè)數(shù)據(jù)征唬。
2.1.4 B+樹(shù)
在B+樹(shù)中捌显，所有記錄節(jié)點(diǎn)都是按鍵值的大小順序存放在同一層的葉子節(jié)點(diǎn)上，由各葉子節(jié)點(diǎn)指針進(jìn)行連接总寒。先來(lái)看一個(gè)B+樹(shù)扶歪，其高度為2，每頁(yè)可存放4條記錄摄闸，如圖一所示善镰。
B+樹(shù)和B樹(shù)的區(qū)別？
- B+樹(shù)的數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中年枕，非葉子節(jié)點(diǎn)只保存索引炫欺；B樹(shù)的數(shù)據(jù)既保存在葉子節(jié)點(diǎn)，也保存在非葉子節(jié)點(diǎn)熏兄。
- B+樹(shù)的葉子節(jié)點(diǎn)之間通過(guò)指針相互連接品洛，方便直接在葉子節(jié)點(diǎn)中進(jìn)行指定范圍內(nèi)的查詢；B+樹(shù)的葉子節(jié)點(diǎn)之間并為連接摩桶。
2.1.3.1 B+樹(shù)的插入操作
B+樹(shù)的插入必須保證插入后葉子節(jié)點(diǎn)中的記錄依然排序桥状，同時(shí)需要考慮插入到B+樹(shù)的三種情況，每種情況都可能會(huì)導(dǎo)致不同的插入算法硝清。
這里用一個(gè)例子來(lái)分析B+樹(shù)的插入辅斟。例如，對(duì)于圖5-6中的這棵B+樹(shù)芦拿，若用戶插入28這個(gè)鍵值砾肺，發(fā)現(xiàn)當(dāng)前Leaf Page和Index Page都沒(méi)有滿，直接進(jìn)行插入即可防嗡，之后得圖二：
接著再插入70這個(gè)鍵值变汪，這時(shí)原先的Leaf Page已經(jīng)滿了，但是Index Page還沒(méi)有滿蚁趁，符合表5-1的第二種情況裙盾，這時(shí)插入Leaf Page后的情況為55、55、60番官、65庐完、70，并根據(jù)中間的值60來(lái)拆分葉子節(jié)點(diǎn)徘熔，可得圖三：
最后插入鍵值95门躯，這時(shí)符合表中討論的第三種情況，即Leaf Page和Index Page都滿了酷师，這時(shí)需要做兩次拆分讶凉，得到圖四：
可以看到，不管怎么變化山孔，B+樹(shù)總是會(huì)保持平衡懂讯。但是為了保持平衡對(duì)于新插入的鍵值可能需要做大量的拆分頁(yè)（split）操作。因?yàn)锽+樹(shù)結(jié)構(gòu)主要用于磁盤(pán)台颠，頁(yè)的拆分意味著磁盤(pán)的操作褐望，所以應(yīng)該在可能的情況下盡量減少頁(yè)的拆分操作。因此串前，B+樹(shù)同樣提供了類(lèi)似于平衡二叉樹(shù)的旋轉(zhuǎn)（Rotation）功能瘫里。
旋轉(zhuǎn)發(fā)生在Leaf Page已經(jīng)滿，但是其的左右兄弟節(jié)點(diǎn)沒(méi)有滿的情況下荡碾。這時(shí)B+樹(shù)并不會(huì)急于去做拆分頁(yè)的操作谨读，而是將記錄移到所在頁(yè)的兄弟節(jié)點(diǎn)上。在通常情況下玩荠，左兄弟會(huì)被首先檢查用來(lái)做旋轉(zhuǎn)操作漆腌，因此再來(lái)看圖二的情況贼邓，若插入鍵值70阶冈，其實(shí)B+樹(shù)并不會(huì)急于去拆分葉子節(jié)點(diǎn)，而是去做旋轉(zhuǎn)操作塑径，得到如圖五所示的操作：
可以看到通過(guò)將記錄移到兄弟節(jié)點(diǎn)上后女坑，省去了拆分的操作。
2.2 B+樹(shù)索引
B+樹(shù)索引的本質(zhì)就是B+樹(shù)在數(shù)據(jù)庫(kù)中的實(shí)現(xiàn)统舀。但是B+索引在數(shù)據(jù)庫(kù)中有一個(gè)特點(diǎn)是高扇出性匆骗，因此在數(shù)據(jù)庫(kù)中，B+樹(shù)的高度一般都在2～4層誉简，這也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要2到4次IO碉就，這倒不錯(cuò)。
數(shù)據(jù)庫(kù)中的B+樹(shù)索引可以分為聚集索引（clustered inex）和輔助索引（secondary index） 闷串，但是不管是聚集還是輔助的索引瓮钥，其內(nèi)部都是B+樹(shù)的，即高度平衡的，葉子節(jié)點(diǎn)存放著所有的數(shù)據(jù)碉熄。聚集索引與輔助索引不同的是桨武，葉子節(jié)點(diǎn)存放的是否是一整行的信息。
2.2.1 聚集索引
之前已經(jīng)介紹過(guò)了锈津，InnoDB存儲(chǔ)引擎表是索引組織表呀酸，即表中數(shù)據(jù)按照主鍵順序存放。而聚集索引（clustered index）就是按照每張表的主鍵構(gòu)造一棵B+樹(shù)琼梆，將一個(gè)表的全部行數(shù)據(jù)分到所有葉子節(jié)點(diǎn)中進(jìn)行保存性誉。一張表只能有一個(gè)聚集索引。
優(yōu)點(diǎn)如下：
對(duì)于主鍵的排序查找和范圍查找速度非扯Ｌ荆快艾栋。葉子節(jié)點(diǎn)的數(shù)據(jù)就是用戶所要查詢的數(shù)據(jù)。如用戶需要查詢一張注冊(cè)用戶的表蛉顽，查詢最后注冊(cè)的10位用戶蝗砾，由于B+樹(shù)索引是雙向鏈表的，用戶可以快速找到最后一個(gè)數(shù)據(jù)頁(yè)携冤，并取出10條記錄悼粮。
范圍查詢（range query），即如果要查找主鍵某一范圍內(nèi)的數(shù)據(jù)曾棕，通過(guò)葉子節(jié)點(diǎn)的上層中間節(jié)點(diǎn)就可以得到頁(yè)的范圍扣猫，之后直接讀取數(shù)據(jù)頁(yè)即可。
2.2.2 輔助索引
對(duì)于輔助索引（Secondary Index翘地，也稱(chēng)非聚集索引）申尤，葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)。葉子節(jié)點(diǎn)除了包含鍵值以外衙耕，每個(gè)葉子節(jié)點(diǎn)中的索引行中還包含了一個(gè)書(shū)簽（bookmark）昧穿。該書(shū)簽用來(lái)告訴InnoDB存儲(chǔ)引擎哪里可以找到與索引相對(duì)應(yīng)的行數(shù)據(jù)。由于InnoDB存儲(chǔ)引擎表是索引組織表橙喘，因此InnoDB存儲(chǔ)引擎的輔助索引的書(shū)簽就是相應(yīng)行數(shù)據(jù)的聚集索引鍵时鸵。下圖顯示了InnoDB存儲(chǔ)引擎中輔助索引與聚集索引的關(guān)系。
輔助索引的存在并不影響數(shù)據(jù)在聚集索引中的組織厅瞎，因此每張表上可以有多個(gè)輔助索引饰潜。當(dāng)通過(guò)輔助索引來(lái)尋找數(shù)據(jù)時(shí)，InnoDB存儲(chǔ)引擎會(huì)遍歷輔助索引并通過(guò)葉級(jí)別的指針獲得指向主鍵索引的主鍵和簸，然后再通過(guò)主鍵索引來(lái)找到一個(gè)完整的行記錄彭雾。舉例來(lái)說(shuō)，如果在一棵高度為3的輔助索引樹(shù)中查找數(shù)據(jù)锁保，那需要對(duì)這棵輔助索引樹(shù)遍歷3次找到指定主鍵薯酝，如果聚集索引樹(shù)的高度同樣為3南誊，那么還需要對(duì)聚集索引樹(shù)進(jìn)行3次查找，最終找到一個(gè)完整的行數(shù)據(jù)所在的頁(yè)蜜托，因此一共需要6次邏輯IO訪問(wèn)以得到最終的一個(gè)數(shù)據(jù)頁(yè)抄囚。
聚集索引和輔助索引的區(qū)別？
- 最主要的區(qū)別就是聚集索引的葉子節(jié)點(diǎn)保存了最終的數(shù)據(jù)橄务，而輔助索引的葉子節(jié)點(diǎn)保存了指向數(shù)據(jù)的指針幔托，最終數(shù)據(jù)還得靠這個(gè)指針繼續(xù)去查詢。
- Mysql數(shù)據(jù)庫(kù)中蜂挪，InnoDB引擎使用的聚集索引重挑，MyISAM引擎使用的是輔助索引。MyISAM引擎實(shí)現(xiàn)中棠涮，索引文件和數(shù)據(jù)文件是分開(kāi)的谬哀，而InnoDB引擎中索引和數(shù)據(jù)是放同一個(gè)文件中的。
上述的解釋并不意味著聚集索引一定比輔助索引快严肪。比如使用select count(*) from table;這種命令的時(shí)候史煎，實(shí)際mysql內(nèi)部最終并不是通過(guò)聚集索引實(shí)現(xiàn)查詢的，而是內(nèi)部?jī)?yōu)化器選用輔助索引實(shí)現(xiàn)查詢驳糯。這樣做的原因是該查詢并不查詢數(shù)據(jù)篇梭，只是查詢數(shù)據(jù)條數(shù)，相比于聚集索引酝枢，輔助索引由于只保存了索引值恬偷，而不保存數(shù)據(jù)值，因此占用空間更小帘睦，查找更快袍患。
2.2.3 聯(lián)合索引
聯(lián)合索引是指對(duì)表上的多個(gè)列進(jìn)行索引。前面討論的情況都是只對(duì)表上的一個(gè)列進(jìn)行索引竣付。聯(lián)合索引的創(chuàng)建方法與單個(gè)索引創(chuàng)建的方法一樣诡延，不同之處僅在于有多個(gè)索引列。例如以下代碼創(chuàng)建了一張t表卑笨，并且索引idx_a_b是聯(lián)合索引孕暇，聯(lián)合的列為（a仑撞，b）：
CREATE TABLE t(
a INT,
b INT,
PRIMARY KEY(a),
KEY idx_a_b(a,b)
)ENGINE=INNODB
那么何時(shí)需要使用聯(lián)合索引呢赤兴？在討論這個(gè)問(wèn)題之前，先來(lái)看一下聯(lián)合索引內(nèi)部的結(jié)果隧哮。從本質(zhì)上來(lái)說(shuō)桶良，聯(lián)合索引也是一棵B+樹(shù)，不同的是聯(lián)合索引的鍵值的數(shù)量不是1沮翔，而是大于等于2陨帆。接著來(lái)討論兩個(gè)整型列組成的聯(lián)合索引，假定兩個(gè)鍵值的名稱(chēng)分別為a、b疲牵，如圖:
從圖可以觀察到多個(gè)鍵值的B+樹(shù)情況承二。其實(shí)和之前討論的單個(gè)鍵值的B+樹(shù)并沒(méi)有什么不同，鍵值都是排序的纲爸，通過(guò)葉子節(jié)點(diǎn)可以邏輯上順序地讀出所有數(shù)據(jù)亥鸠，就上面的例子來(lái)說(shuō)，即（1识啦，1）负蚊、（1，2）颓哮、（2家妆，1）、（2冕茅，4）伤极、（3，1）姨伤、（3塑荒，2）。數(shù)據(jù)按（a姜挺，b）的順序進(jìn)行了存放（key中的兩個(gè)數(shù)字都進(jìn)行了排序）齿税。
最左匹配原則
聯(lián)合索引有一個(gè)原則：最左匹配原則。如上述示例中我們創(chuàng)建了一個(gè)由a和b組成的索引炊豪，如果查詢語(yǔ)句寫(xiě)作如下：
select * from t where a='1' and b='2'凌箕；
那么會(huì)使用聯(lián)合索引進(jìn)行進(jìn)行查詢，如果只寫(xiě)了a词渤，也是會(huì)使用聯(lián)合索引：
select * from t where a= '1';
但是如果只寫(xiě)了b作為查詢條件牵舱，那么就不會(huì)使用聯(lián)合索引：
select * from t where b='2';
除此之外，最左匹配原則還有下面幾個(gè)特點(diǎn)：
- 通過(guò)最左匹配原則缺虐，mysql會(huì)一直向右匹配直到遇到范圍查詢(>,<,between,like)就會(huì)停止匹配芜壁，比如
a=3 and b=4 and c<5 and d=6如果建立(a,b,c,d)的索引，d實(shí)際是用不到索引的高氮，如果a=3 and b=4 and d=6 nad c<5則建立(a,b,c,d)的索引慧妄，那abcd都用到了索引進(jìn)行查詢。 - =和in可以亂序剪芍，不影響索引的建立塞淹，如
a = 3 and b=4 and c=5 and d=6這種情況下abcd的條件都會(huì)順便換位置，不影響罪裹”テ眨可以亂序的原因是：mysql優(yōu)化器會(huì)對(duì)sql進(jìn)行優(yōu)化运挫，重新將順序調(diào)整為設(shè)置索引的順序。
3. 全文索引
3.1 概述
通過(guò)前面章節(jié)的介紹套耕，已經(jīng)知道B+樹(shù)索引的特點(diǎn)谁帕，可以通過(guò)索引字段的前綴（prefix）進(jìn)行查找。例如冯袍，對(duì)于下面的查詢B+樹(shù)索引是支持的：
SELECT * FROM blog WHERE content like'xxx%'
上述SQL語(yǔ)句可以查詢博客內(nèi)容以xxx開(kāi)頭的文章雇卷，并且只要content添加了B+樹(shù)索引，就能利用索引進(jìn)行快速查詢颠猴。然而實(shí)際這種查詢不符合用戶的要求关划，因?yàn)樵诟嗟那闆r下，用戶需要查詢的是博客內(nèi)容包含單詞xxx的文章翘瓮，即：
SELECT * FROM blog WHERE content like'%xxx%'
根據(jù)B+樹(shù)索引的特性贮折，上述SQL語(yǔ)句即便添加了B+樹(shù)索引也是需要進(jìn)行索引的掃描來(lái)得到結(jié)果。類(lèi)似這樣的需求在互聯(lián)網(wǎng)應(yīng)用中還有很多资盅。例如调榄，搜索引擎需要根據(jù)用戶輸入的關(guān)鍵字進(jìn)行全文查找，電子商務(wù)網(wǎng)站需要根據(jù)用戶的查詢條件呵扛，在可能需要在商品的詳細(xì)介紹中進(jìn)行查找每庆，這些都不是B+樹(shù)索引所能很好地完成的工作。
全文檢索（Full-Text Search）是將存儲(chǔ)于數(shù)據(jù)庫(kù)中的整本書(shū)或整篇文章中的任意內(nèi)容信息查找出來(lái)的技術(shù)今穿。它可以根據(jù)需要獲得全文中有關(guān)章缤灵、節(jié)、段蓝晒、句腮出、詞等信息，也可以進(jìn)行各種統(tǒng)計(jì)和分析芝薇。
3.2 倒排索引
全文檢索通常使用倒排索引（inverted index）來(lái)實(shí)現(xiàn)胚嘲。倒排索引同B+樹(shù)索引一樣，也是一種索引結(jié)構(gòu)洛二。它在輔助表（auxiliary table）中存儲(chǔ)了單詞與單詞自身在一個(gè)或多個(gè)文檔中所在位置之間的映射馋劈。這通常利用關(guān)聯(lián)數(shù)組實(shí)現(xiàn)，其擁有兩種表現(xiàn)形式：
?inverted file index晾嘶，其表現(xiàn)形式為{單詞妓雾，單詞所在文檔的ID}
?full invertedindex，其表現(xiàn)形式為{單詞变擒，(單詞所在文檔的ID君珠，在具體文檔中的位置)}
4. 哈希索引
哈希索引即先通過(guò)哈希算法得出哈希值作為地址再進(jìn)行保存寝志。使用哈希索引理論上復(fù)雜度為1娇斑，比B+樹(shù)的效率更高策添，但是卻不常使用作為數(shù)據(jù)的索引實(shí)現(xiàn)。原因在于哈希索引內(nèi)部查詢條件為哈希值毫缆，由于沒(méi)有順序唯竹，所以不能進(jìn)行范圍查找，而只能使用等于查找苦丁，同時(shí)也沒(méi)有asc,desc等排序功能浸颓。
哈希索引可能存在的另外一個(gè)問(wèn)題是：遇到大量Hash值相同的情況下，效率不一定會(huì)比B+樹(shù)索引高旺拉，即極端情況下會(huì)變成線性結(jié)構(gòu)产上。
5. 總結(jié)
索引是建的越多越好嗎？
不是蛾狗。
- 數(shù)據(jù)量小的表不需要建立索引晋涣，建立索引會(huì)增加額外的開(kāi)銷(xiāo)。
- 數(shù)據(jù)變更需要維護(hù)索引沉桌，更多的索引意味著更多的維護(hù)成本
- 更多的索引意味著更多的空間
