索引到底是什么

索引是幫助Mysql高效獲取數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)

索引儲存在哪里

和數(shù)據(jù)一樣饱溢，索引以文件形式儲存在硬盤上牧抵，在MyISAM儲存引擎中，數(shù)據(jù)和索引文件試試分開儲存的。

MyISAM文件儲存示意圖

在InnoDB中碳褒，數(shù)據(jù)和索引文件是合起來儲存的，注意下圖中沒有了I（index）結(jié)尾的文件看疗。

InnoDB文件儲存示意圖

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

想想JDK8的Hashmap中沙峻，當(dāng)鏈表長度大于一定限度時(shí)，為了能夠高效的檢索數(shù)據(jù)两芳，引入了紅黑樹摔寨。索引的思想也是這樣，通過一種數(shù)據(jù)結(jié)構(gòu)高效的數(shù)據(jù)結(jié)構(gòu)來加速數(shù)據(jù)檢索的過程怖辆。
想想以下這幾種常用的數(shù)據(jù)結(jié)構(gòu)可否用于索引呢是复？
1. BST
2. 紅黑樹
3. Hash

BST在節(jié)點(diǎn)有序的情況下會變成一種線性結(jié)構(gòu)，復(fù)雜度退化到O(n)竖螃，顯然是不行的淑廊。
紅黑樹解決了平衡的問題，但是在數(shù)據(jù)量比較大的情況下特咆，紅黑樹的高度太高季惩，導(dǎo)致磁盤IO次數(shù)過多，也不夠合理坚弱。
Hash似乎解決了磁盤IO的問題蜀备，但是Hash有大量沖突的時(shí)候還是線性遍歷，最關(guān)鍵的是限制太多荒叶，例如無法支持范圍查詢碾阁，也不支持部分索引匹配。

B+樹

B-樹

B+樹

比起紅黑樹些楣，上面兩種數(shù)據(jù)結(jié)構(gòu)都更加矮胖脂凶。他們兩之間一個(gè)很大的不同是B+樹的節(jié)點(diǎn)上不儲存value宪睹，只儲存key，而葉子節(jié)點(diǎn)上儲存了所有kv集合蚕钦，并且節(jié)點(diǎn)之間都是有序的亭病。

這樣的好處是每一次磁盤IO能夠讀取的節(jié)點(diǎn)更多，也就是樹的度可以設(shè)置的更大一些嘶居，因?yàn)槊看未疟PIO讀取的磁盤頁數(shù)是一定的罪帖，例如每次磁盤IO能夠讀取1頁=4kb，那么省去value的情況下同樣一頁數(shù)據(jù)能夠讀取更多的key整袁，這樣就大大減少了磁盤的IO次數(shù)。

此外佑吝，B+樹是排序好的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫中><或者order by等都可以直接依賴這一特性芋忿。

MyISAM索引實(shí)現(xiàn)（非聚集索引）

MyISAM中索引和數(shù)據(jù)是分開儲存的，并且主鍵索引和輔助索引（二級索引）的儲存方式是一樣的戈钢。

主鍵索引

輔助索引

InnoDB索引實(shí)現(xiàn)（聚集索引）

InnoDB中索引文件和數(shù)據(jù)文件是同一個(gè)文件。并且主鍵索引和二級索引儲存方式有所不同殉了，如圖所示，二級索引的葉子節(jié)點(diǎn)不儲存數(shù)據(jù)宣渗，僅儲存主鍵ID梨州。

主鍵索引

輔助索引

這里思考兩個(gè)問題

1. InnoDB表中必然有主鍵，為什么最好一定是有序自增id暴匠？
2. 為什么二級索引葉子節(jié)點(diǎn)儲存的是主鍵值鞍恢？

問題一：如果id是無序的，那么很有可能新插入的值會導(dǎo)致當(dāng)前節(jié)點(diǎn)分裂每窖，此時(shí)MySQL不得不為了將新記錄插到合適位置而移動(dòng)數(shù)據(jù)帮掉，甚至目標(biāo)頁面可能已經(jīng)被回寫到磁盤上而從緩存中清掉，此時(shí)又要從磁盤上讀回來窒典，這增加了很多開銷蟆炊，同時(shí)頻繁的移動(dòng)、分頁操作造成了大量的碎片瀑志，得到了不夠緊湊的索引結(jié)構(gòu)涩搓，后續(xù)不得不通過OPTIMIZE TABLE來重建表并優(yōu)化填充頁面污秆。
反之，如果每次插入有序昧甘，那就會在當(dāng)前頁后面連續(xù)寫入良拼，寫不下就會重新分配一個(gè)節(jié)點(diǎn)，內(nèi)存都是連續(xù)的充边，這樣效率自然也就最高了庸推。

問題二：如果二級索引儲存的也是數(shù)據(jù)，那么每次插入mysql都不得不更新每棵索引樹浇冰，這樣就加劇了新增編輯時(shí)的性能損耗贬媒，并且這樣一來空間利用率也不高，產(chǎn)生了大量冗余數(shù)據(jù)湖饱。

聯(lián)合索引

聯(lián)合索引底層數(shù)據(jù)結(jié)構(gòu)長什么樣掖蛤？

聯(lián)合索引示意

比較相等時(shí)，先比較第一列的值井厌，如果相等蚓庭，再繼續(xù)比較第二列，以此類推仅仆。

最左前綴原理

使用聯(lián)合索引時(shí)器赞，索引列的定義順序?qū)绊懙阶罱K查詢時(shí)索引的使用情況。例如聯(lián)合索引（a,b,c）墓拜，mysql會從最左邊的列優(yōu)先匹配港柜，如果最左邊的帶頭大哥沒有使用到，在未使用覆蓋索引的情況下咳榜，就只能全表掃描夏醉。
聯(lián)合底層數(shù)據(jù)結(jié)構(gòu)思考，mysql會優(yōu)先以聯(lián)合索引第一列匹配涌韩，此后才會匹配下一列畔柔，如果不指定第一列匹配的值，也就無法得知下一步查詢哪個(gè)節(jié)點(diǎn)臣樱。
另外還有一種情況靶擦，如果遇到 > < between等這樣的范圍查詢，那B+樹中也就無法對下一列進(jìn)行等值匹配了雇毫。