索引到底是什么
索引是幫助Mysql高效獲取數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)
索引儲存在哪里
和數(shù)據(jù)一樣，索引以文件形式儲存在硬盤上，在MyISAM儲存引擎中，數(shù)據(jù)和索引文件試試分開儲存的。
在InnoDB中，數(shù)據(jù)和索引文件是合起來儲存的，注意下圖中沒有了I（index）結(jié)尾的文件。
后面會進(jìn)一步分析為什么會這樣
索引的數(shù)據(jù)結(jié)構(gòu)
想想JDK8的Hashmap中，當(dāng)鏈表長度大于一定限度時，為了能夠高效的檢索數(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é)點有序的情況下會變成一種線性結(jié)構(gòu)，復(fù)雜度退化到O(n)，顯然是不行的。
紅黑樹解決了平衡的問題，但是在數(shù)據(jù)量比較大的情況下，紅黑樹的高度太高，導(dǎo)致磁盤IO次數(shù)過多，也不夠合理。
Hash似乎解決了磁盤IO的問題，但是Hash有大量沖突的時候還是線性遍歷，最關(guān)鍵的是限制太多，例如無法支持范圍查詢，也不支持部分索引匹配。
B+樹
比起紅黑樹，上面兩種數(shù)據(jù)結(jié)構(gòu)都更加矮胖。他們兩之間一個很大的不同是B+樹的節(jié)點上不儲存value，只儲存key，而葉子節(jié)點上儲存了所有kv集合，并且節(jié)點之間都是有序的。
這樣的好處是每一次磁盤IO能夠讀取的節(jié)點更多，也就是樹的度可以設(shè)置的更大一些，因為每次磁盤IO讀取的磁盤頁數(shù)是一定的，例如每次磁盤IO能夠讀取1頁=4kb，那么省去value的情況下同樣一頁數(shù)據(jù)能夠讀取更多的key，這樣就大大減少了磁盤的IO次數(shù)。
此外，B+樹是排序好的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫中><或者order by等都可以直接依賴這一特性。
MyISAM索引實現(xiàn)（非聚集索引）
MyISAM中索引和數(shù)據(jù)是分開儲存的，并且主鍵索引和輔助索引（二級索引）的儲存方式是一樣的。
InnoDB索引實現(xiàn)（聚集索引）
InnoDB中索引文件和數(shù)據(jù)文件是同一個文件。并且主鍵索引和二級索引儲存方式有所不同，如圖所示，二級索引的葉子節(jié)點不儲存數(shù)據(jù)，僅儲存主鍵ID。
這里思考兩個問題
- InnoDB表中必然有主鍵，為什么最好一定是有序自增id？
- 為什么二級索引葉子節(jié)點儲存的是主鍵值？
問題一：如果id是無序的，那么很有可能新插入的值會導(dǎo)致當(dāng)前節(jié)點分裂，此時MySQL不得不為了將新記錄插到合適位置而移動數(shù)據(jù)，甚至目標(biāo)頁面可能已經(jīng)被回寫到磁盤上而從緩存中清掉，此時又要從磁盤上讀回來，這增加了很多開銷，同時頻繁的移動、分頁操作造成了大量的碎片，得到了不夠緊湊的索引結(jié)構(gòu)，后續(xù)不得不通過OPTIMIZE TABLE來重建表并優(yōu)化填充頁面。
反之，如果每次插入有序，那就會在當(dāng)前頁后面連續(xù)寫入，寫不下就會重新分配一個節(jié)點，內(nèi)存都是連續(xù)的，這樣效率自然也就最高了。
問題二：如果二級索引儲存的也是數(shù)據(jù)，那么每次插入mysql都不得不更新每棵索引樹，這樣就加劇了新增編輯時的性能損耗，并且這樣一來空間利用率也不高，產(chǎn)生了大量冗余數(shù)據(jù)。
聯(lián)合索引
聯(lián)合索引底層數(shù)據(jù)結(jié)構(gòu)長什么樣？
比較相等時，先比較第一列的值，如果相等，再繼續(xù)比較第二列，以此類推。
最左前綴原理
使用聯(lián)合索引時，索引列的定義順序?qū)绊懙阶罱K查詢時索引的使用情況。例如聯(lián)合索引（a,b,c），mysql會從最左邊的列優(yōu)先匹配，如果最左邊的帶頭大哥沒有使用到，在未使用覆蓋索引的情況下，就只能全表掃描。
聯(lián)合底層數(shù)據(jù)結(jié)構(gòu)思考，mysql會優(yōu)先以聯(lián)合索引第一列匹配，此后才會匹配下一列，如果不指定第一列匹配的值，也就無法得知下一步查詢哪個節(jié)點。
另外還有一種情況，如果遇到 > < between等這樣的范圍查詢，那B+樹中也就無法對下一列進(jìn)行等值匹配了。
