概述
最近一段時(shí)間重新深入研究了一遍MySQL的內(nèi)容姑曙，今天主要分享分析MySQL索引原理襟交，后續(xù)會(huì)輸出一些關(guān)于MySQL方面的干貨，希望各位小伙伴喜歡渣磷。
一婿着、什么是索引、為什么要建立索引醋界？
關(guān)于索引的理解，個(gè)人更加喜歡將其比喻為字典里面的目錄提完，根據(jù)字典來進(jìn)行查詢的速度遠(yuǎn)大于每一頁逐個(gè)逐個(gè)字排查的速度形纺。
? ? 索引主要用于快速找出在某個(gè)列中有特定值的行，倘若不使用索引徒欣，MySQL必須從第一條記錄開始讀完整個(gè)表逐样，直到找出相關(guān)的行，表越大，查詢數(shù)據(jù)所花費(fèi)的時(shí)間就越多脂新。如果表中查詢的列有一個(gè)索引挪捕，MySQL能夠快速到達(dá)一個(gè)位置去搜索數(shù)據(jù)，而不必查找所有數(shù)據(jù)争便，那么將會(huì)節(jié)省很大一部分時(shí)間级零。
（一）、索引的存儲(chǔ)文件是如何的滞乙？
首先我們來看看mysql索引數(shù)據(jù)的存儲(chǔ)位置：
mysql的數(shù)據(jù)存儲(chǔ)是存放在mysql的data文件夾底下奏纪，截圖如下所示：
? ? ? 查看該文件夾底下，我們通痴镀簦可以看到相關(guān)的信息內(nèi)容：
.frm表結(jié)構(gòu)文件序调，和所選用的存儲(chǔ)引擎無關(guān)。
（二）兔簇、MyISAM引擎的文件格式
1发绢、myd?數(shù)據(jù)文件后綴
2、myi??索引文件后綴
（三）垄琐、InnoDB引擎的文件格式
1朴摊、ibd?將索引信息和數(shù)據(jù)一起存儲(chǔ)起來
二、索引的結(jié)構(gòu)是什么此虑？為何不采用別的結(jié)構(gòu)甚纲？
?? ? 索引在起初做設(shè)計(jì)的時(shí)候其實(shí)是有一定數(shù)據(jù)結(jié)構(gòu)選型的，對(duì)于不同的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)朦前，我做了以下的相關(guān)總結(jié)：
（一）介杆、使用二叉樹作為索引結(jié)構(gòu)缺陷
容易導(dǎo)致二叉樹出現(xiàn)結(jié)構(gòu)偏移，極端情況容易變成一條鏈表的形狀韭寸。
例如下方情況：
（二）春哨、使用紅黑樹數(shù)據(jù)結(jié)構(gòu)的缺陷
紅黑樹雖然有自動(dòng)進(jìn)行樹節(jié)點(diǎn)的二叉平衡功能。雖然相對(duì)于二叉樹而言恩伺，不會(huì)有太嚴(yán)重的單邊偏移情況赴背，但還是避免不了極端情況下樹的重心出現(xiàn)偏移的現(xiàn)象。（數(shù)據(jù)量變大的情況下晶渠，深度會(huì)變大）
使用紅黑樹數(shù)據(jù)結(jié)構(gòu)容易在極端的情況下發(fā)生紅黑樹失重情況凰荚，如下圖所示，隨著數(shù)據(jù)量的增大褒脯，失重情況愈發(fā)嚴(yán)重：
（三）便瑟、hash索引的缺陷
雖然說hash查詢的速度很快，但是依然有以下缺陷：
1番川、無法解決查詢范圍導(dǎo)致的問題
? 2到涂、無法解決hash沖突的問題
三脊框、如何理解BTree
在學(xué)習(xí)索引的真正結(jié)構(gòu)之前，首先我們需要來了解一下什么是BTree践啄。
（一）浇雹、BTree的基本結(jié)構(gòu)如下圖所示：
（二）、BTree里面包含有幾個(gè)重要的特點(diǎn)
? ? 1屿讽、度(Degree)-節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)個(gè)數(shù)昭灵，一旦存儲(chǔ)數(shù)據(jù)超過度值就要進(jìn)行節(jié)點(diǎn)分裂
? ? 2、 所有葉子節(jié)點(diǎn)具有相同的深度
? ? 3聂儒、葉子節(jié)點(diǎn)的指針為空
? ? 4虎锚、葉子節(jié)點(diǎn)中的數(shù)據(jù)key從左到右遞增排列
btree數(shù)據(jù)結(jié)構(gòu)通過節(jié)點(diǎn)的橫向擴(kuò)展，從而壓低整個(gè)Btree的高度衩婚，減少了節(jié)點(diǎn)io讀取的次數(shù)窜护。通常百萬級(jí)別的數(shù)據(jù)會(huì)被壓到3-5層的高度。
四非春、節(jié)點(diǎn)數(shù)據(jù)讀取過程發(fā)生了什么柱徙？
我在初學(xué)索引的時(shí)候，覺得io次數(shù)讀取越少奇昙，因此獲取數(shù)據(jù)的速度會(huì)越快护侮。后來重新回看了一遍操作系統(tǒng)原理的講解之后，對(duì)于這塊的內(nèi)容有了更加深入的認(rèn)識(shí)储耐。
（一）羊初、磁盤數(shù)據(jù)讀取
指針在同一磁道上邊讀取數(shù)據(jù)的時(shí)候如果采用的是順序讀取方式，那么數(shù)據(jù)的讀取效率就會(huì)比較高效什湘。倘若數(shù)據(jù)在進(jìn)行讀取的時(shí)候采用了隨機(jī)讀取的方式长赞，則需要進(jìn)行磁道的變換，這種磁道變換讀取所帶來的性能消耗會(huì)是巨大的闽撤。每個(gè)節(jié)點(diǎn)存放的地址通常都不會(huì)是連續(xù)的得哆，不可避免的會(huì)有一些內(nèi)存碎片存在，因此每一次進(jìn)行io讀取都會(huì)是比較耗費(fèi)性能的哟旗。
btree里面的節(jié)點(diǎn)采用了key-value的基本存儲(chǔ)結(jié)構(gòu)贩据，key是索引的數(shù)值，value是存儲(chǔ)的data數(shù)值闸餐。由于我們對(duì)于btree進(jìn)行節(jié)點(diǎn) 比較的時(shí)候是基于內(nèi)存進(jìn)行數(shù)據(jù)比較饱亮，先從磁盤進(jìn)行io讀取數(shù)據(jù)，讀取到cpu緩存中進(jìn)行比對(duì)绎巨。
在了解了磁道讀取問題之后近尚，我們?cè)賮硭伎家幌滤饕谋闅v。
如下圖所示：
? ? 如圖所示场勤，假設(shè)我們沒有采用索引戈锻，要讀取數(shù)據(jù)第七行（23），則需要進(jìn)行7次的io讀取操作和媳。假若使用了索引格遭，則可以通過走索引的方式，34-->22-->23一共三次io讀取操作即可查找到所要的節(jié)點(diǎn)23留瞳。
（二）拒迅、度值無限擴(kuò)增會(huì)如何？
如果我們將節(jié)點(diǎn)的度設(shè)置到極致她倘，例如說將度設(shè)置到100W璧微，那么BTree的高度就會(huì)降低，查詢的次數(shù)就會(huì)大大減少硬梁，是否可行前硫？
這種想法是不可行的，節(jié)點(diǎn)會(huì)變得過大荧止。每次進(jìn)行節(jié)點(diǎn)數(shù)據(jù)讀取的時(shí)候都需要將磁盤的數(shù)據(jù)加載到操作系統(tǒng)自身的緩存中屹电。假設(shè)將度值設(shè)置過大，io一次讀取的大小還是有限跃巡，過大的節(jié)點(diǎn)還是需要進(jìn)行多次的io讀取危号。
計(jì)算機(jī)里面的內(nèi)存和磁盤之間進(jìn)行數(shù)據(jù)讀取是按照計(jì)算機(jī)自身標(biāo)準(zhǔn)來進(jìn)行設(shè)置的，每次讀取的大小空間基本單位通常稱之為頁素邪，假設(shè)每一頁的數(shù)據(jù)讀取通常是8k（不同硬件設(shè)備大小不同）外莲，假若說一個(gè)節(jié)點(diǎn)的大小為10M,那么讀取該節(jié)點(diǎn)里面的數(shù)據(jù)則需要進(jìn)行多次的io操作。（通常DBA在進(jìn)行數(shù)據(jù)庫的度值設(shè)置的時(shí)候默認(rèn)是將一個(gè)頁單位的大小設(shè)置為度的大小兔朦。）
（三）偷线、磁盤 IO
一個(gè)數(shù)據(jù)庫必須保證其中存儲(chǔ)的所有數(shù)據(jù)都是可以隨時(shí)讀寫的，同時(shí)因?yàn)?b> MySQL 中所有的數(shù)據(jù)其實(shí)都是以文件的形式存儲(chǔ)在磁盤上的烘绽，而從磁盤上隨機(jī)訪問對(duì)應(yīng)的數(shù)據(jù)非常耗時(shí)淋昭，所以數(shù)據(jù)庫程序和操作系統(tǒng)提供了 緩沖池和 內(nèi)存以提高數(shù)據(jù)的訪問速度。
除此之外安接，我們知道數(shù)據(jù)庫對(duì)數(shù)據(jù)的讀取并不是以行為單位進(jìn)行的翔忽，無論是讀取一行還是多行，都會(huì)將該行或者多行所在的頁全部加載進(jìn)來盏檐，然后再讀取對(duì)應(yīng)的數(shù)據(jù)記錄歇式；也就是說，讀取所耗費(fèi)的時(shí)間與行數(shù)無關(guān)胡野，只與頁數(shù)有關(guān)材失。（這也就是數(shù)據(jù)庫的預(yù)讀取機(jī)制）
? 頁大小可以如下操作顯示：
在 MySQL 中，頁的大小一般為 16KB硫豆，不過也可能是 8KB龙巨、32KB 或者其他值笼呆，這跟 MySQL 的存儲(chǔ)引擎對(duì)數(shù)據(jù)的存儲(chǔ)方式有很大的關(guān)系。
關(guān)于數(shù)據(jù)庫的緩存池原理剖析日后在后續(xù)我會(huì)進(jìn)行解析旨别，這里暫時(shí)先略過诗赌。
五、如何進(jìn)行BTree的優(yōu)化秸弛？
如果每個(gè)節(jié)點(diǎn)的大小越小铭若，則操作系統(tǒng)讀取一頁數(shù)據(jù)的內(nèi)容則越多，內(nèi)存中可容納的數(shù)據(jù)量增加递览，處理的效率也會(huì)有所提升叼屠。因此 B+Tree 就此誕生了。
（一）绞铃、如何理解B+Tree镜雨？
? B+Tree的基本結(jié)構(gòu)如下圖所示：
? （二）、B+Tree幾個(gè)比較重要的特點(diǎn)：
? ? 1憎兽、非葉子節(jié)點(diǎn)不存儲(chǔ)data冷离，只存儲(chǔ)key，可以增大度的值纯命。
? ? 2西剥、葉子節(jié)點(diǎn)不存儲(chǔ)指針。
? 3亿汞、順序訪問指針瞭空，提高區(qū)間訪問的性能。
?????仔細(xì)觀察圖中樹結(jié)構(gòu)的同學(xué)不知道是否有發(fā)現(xiàn)疗我，B+Tree里面對(duì)于索引數(shù)據(jù)進(jìn)行了適當(dāng)?shù)娜哂啻鎯?chǔ)咆畏，但是這一點(diǎn)相比于度大小的增加而言，并不會(huì)帶來太多的性能影響吴裤。由于非葉子結(jié)點(diǎn)只存儲(chǔ)key旧找，并沒有存儲(chǔ)data數(shù)據(jù)，因此所有的非葉子結(jié)點(diǎn)的度可以增加地更大麦牺， 使得一次 io 讀取的數(shù)據(jù)更多钮蛛，從磁盤讀取到操作系統(tǒng)內(nèi)存中的數(shù)據(jù)也大大增加。
仔細(xì)觀察B+Tree里面的數(shù)據(jù)結(jié)構(gòu)剖膳，會(huì)發(fā)現(xiàn)葉子節(jié)點(diǎn)里面有相應(yīng)的順序訪問指針魏颓。
? ? B+Tree的葉子節(jié)點(diǎn)之間的順序訪問指針的作用可以提高范圍查詢的效率。
例如說在一定范圍內(nèi)進(jìn)行數(shù)據(jù)查詢的時(shí)候不需要像BTree那樣吱晒，每次在進(jìn)行節(jié)點(diǎn)數(shù)據(jù)讀取的時(shí)候都需要重新從頂部開始讀取甸饱，可以根據(jù)相應(yīng)的順序指針直接進(jìn)行連續(xù)讀取，提高了范圍性讀取數(shù)據(jù)的效率。
六叹话、Myisam非聚簇索引
? ? ? 之前我們有說過mysql里面數(shù)據(jù)存儲(chǔ)的位置和文件信息偷遗。myisam存儲(chǔ)引擎里面，mysql讀取數(shù)據(jù)的時(shí)候會(huì)有一個(gè)文件指針渣刷，根據(jù)指針來讀取數(shù)據(jù)文件的順序?yàn)椋? myi--->.myd（讀取數(shù)據(jù)文件里面的內(nèi)容然后查找數(shù)據(jù)）
? ? 存儲(chǔ)引擎里面的索引通常會(huì)被劃分為主鍵索引和非主鍵索引（一般是指除了主鍵索引之外的那些索引）
（一）鹦肿、主鍵索引：
主鍵索引比較好理解矗烛，B+Tree里面的葉子節(jié)點(diǎn)的key存儲(chǔ)的是索引值辅柴，value存儲(chǔ)的是相應(yīng)data數(shù)據(jù)的指針。
（二）瞭吃、輔助索引：
Myisam里面的輔助索引結(jié)構(gòu)和主鍵索引基本一致碌嘀，結(jié)構(gòu)如下圖所示
（三）、Innodb聚簇索引
在上邊我們提及過innodb存儲(chǔ)中歪架，是將數(shù)據(jù)和索引放在了同一份文件里面的股冗。
因此innodb里面的非主鍵索引（輔助索引）和主鍵索引有一定的區(qū)別，下邊我們來用圖例進(jìn)行詳細(xì)對(duì)比說明：
innodb里面的主鍵索引和非主鍵索引：
（四）和蚪、主鍵索引
主鍵索引里面的存儲(chǔ)情況如下圖所示止状，葉子節(jié)點(diǎn)里面的key是索引的信息，value是數(shù)據(jù)表里面該索引對(duì)應(yīng)行的數(shù)據(jù)信息攒霹。
（五）怯疤、非主鍵索引
這種索引在進(jìn)行存儲(chǔ)的時(shí)候，雖然說節(jié)點(diǎn)依然是key-value的結(jié)構(gòu)催束，key對(duì)應(yīng)的是相應(yīng)的索引集峦，但是value對(duì)應(yīng)的卻是主鍵索引的值。如下圖所示：
如果索引里面存儲(chǔ)的值不是數(shù)字類型而是字符串類型抠刺，那么在進(jìn)行索引插入或者索引查找的時(shí)候都需要通過計(jì)算每個(gè)字符的ASCII碼來判斷索引的大小塔淤。
七、為什么InnoDB表必須有主鍵速妖？
? ? ? 在innodb存儲(chǔ)引擎里面高蜂，數(shù)據(jù)的默認(rèn)的存儲(chǔ)結(jié)構(gòu)默認(rèn)是以B+Tree的結(jié)構(gòu)來進(jìn)行存儲(chǔ)的，因此必須要有主鍵存在罕容。
即使手動(dòng)沒有設(shè)置主鍵备恤，innodb也會(huì)自動(dòng)選取一列數(shù)據(jù)進(jìn)行設(shè)置，或者默認(rèn)生成一列作為主鍵杀赢。
（一）烘跺、使用uuid和自增id作為主鍵的區(qū)別？
在了解了索引原理之后脂崔，我們不妨從底層來思考一下使用uuid替代自增id帶來的缺陷滤淳。
1、由于uuid的長度普遍要比自增id的長度要長砌左，因此uuid更加占用磁盤空間脖咐。
2铺敌、uuid通常都是以字符串的形式存在的，因此在進(jìn)行比較的時(shí)候大多都是基于字符串的形式進(jìn)行比較的(使用ack||碼),而自增主鍵使用的是integer的比較方式屁擅。效率方面差異較大偿凭。
3、uuid在進(jìn)行數(shù)據(jù)插入的時(shí)候可能會(huì)插入到某個(gè)度已經(jīng)滿了的節(jié)點(diǎn)里面派歌，這個(gè)時(shí)候原有的舊節(jié)點(diǎn)就需要進(jìn)行節(jié)點(diǎn)的分裂操作了弯囊，需要進(jìn)行數(shù)據(jù)的移動(dòng)，降低性能效率胶果。
（二）匾嘱、聯(lián)合索引的底層存儲(chǔ)結(jié)構(gòu)是如何的？
在實(shí)際項(xiàng)目開發(fā)中早抠，聯(lián)合索引是我們經(jīng)常會(huì)用到的優(yōu)化技巧之一霎烙，本文暫時(shí)先不講優(yōu)化，先從底層去理解聯(lián)合索引的存儲(chǔ)方式蕊连，后邊會(huì)展開優(yōu)化的講解悬垃。例如一個(gè)聯(lián)合索引里面用到了id，職位名稱甘苍，出生日期三個(gè)字段尝蠕，那么在存儲(chǔ)的時(shí)候會(huì)將三個(gè)字段一起存入節(jié)點(diǎn)里面的key位置。如下圖所示：
在索引節(jié)點(diǎn)里面的key進(jìn)行比對(duì)的時(shí)候羊赵，會(huì)按照id趟佃，職位名稱，出生日期的順序（由左到右）昧捷，比較的時(shí)候是逐一比對(duì)闲昭，一旦沒有匹配到指定字段，則不會(huì)繼續(xù)匹配靡挥，這也是我們常說的復(fù)合索引里面的最左前綴匹配原則序矩。
關(guān)于MySQL索引的基本介紹大致就只想到了這些，關(guān)于索引優(yōu)化方面后邊我會(huì)進(jìn)行系列的干貨輸出跋破，希望各位小伙伴喜歡簸淀。
