前言

Hello我又來了，快年底了椰苟，作為一個有抱負的碼農(nóng)抑月，我想給自己攢一個年終總結(jié)。自上上篇寫了手動搭建Redis集群和MySQL主從同步(非Docker)和上篇寫了動手實現(xiàn)MySQL讀寫分離and故障轉(zhuǎn)移之后舆蝴，索性這次把數(shù)據(jù)庫中最核心的也是最難搞懂的內(nèi)容谦絮，也就是索引，分享給大家洁仗。這篇博客我會談談對于索引結(jié)構(gòu)我自己的看法层皱，以及分享如何從零開始一層一層向上最終理解索引結(jié)構(gòu)。

從一個簡單的表開始

create table user(
    id int primary key,
    age int,
    height int,
    weight int,
    name varchar(32)
)engine = innoDb;

相信只要入門數(shù)據(jù)庫的同學都可以理解這個語句京痢，我們也將從這個最簡單的表開始奶甘，一步步地理解MySQL的索引結(jié)構(gòu)。

首先祭椰，我們往這個表中插入一些數(shù)據(jù)臭家。

INSERT INTO user(id,age,height,weight,name)VALUES(2,1,2,7,'小吉');
INSERT INTO user(id,age,height,weight,name)VALUES(5,2,1,8,'小尼');
INSERT INTO user(id,age,height,weight,name)VALUES(1,4,3,1,'小泰');
INSERT INTO user(id,age,height,weight,name)VALUES(4,1,5,2,'小美');
INSERT INTO user(id,age,height,weight,name)VALUES(3,5,6,7,'小蔡');

我們來查一下，看看這些數(shù)據(jù)是否已經(jīng)放入表中蹄殃。

select * from user;

最初的表

可以看到，數(shù)據(jù)已經(jīng)完整地放到了我們創(chuàng)建的user表中。

但是不知道大家發(fā)現(xiàn)了什么沒有式廷，好像發(fā)生了一件非常詭異的事情，我們插入的數(shù)據(jù)好像亂序了...

MySQL好像悄悄的給我們按照id排了個序蠕趁。

為什么會出現(xiàn)MySQL在我們沒有顯式排序的情況下，默默幫我們排了序呢倔韭？它是在什么時候進行排序的？

頁的引入

不知道大家畢業(yè)多長時間了醇疼，作為一個剛學完操作系統(tǒng)不久的學渣，頁的概念依舊在腦中還沒有變涼乙濒。其實MySQL中也有類似頁的邏輯存儲單位么库，聽我慢慢道來。

在操作系統(tǒng)的概念中忱反，當我們往磁盤中取數(shù)據(jù)，假設要取出的數(shù)據(jù)的大小是1KB米者，但是操作系統(tǒng)并不會只取出這1kb的數(shù)據(jù)随橘，而是會取出4KB的數(shù)據(jù)，因為操作系統(tǒng)的一個頁表項的大小是4KB萝嘁。那為什么我們只需要1KB的數(shù)據(jù)，但是操作系統(tǒng)要取出4KB的數(shù)據(jù)呢咱枉？這就涉及到一個程序局部性的概念，具體的概念我背不清了亿乳，大概就是“一個程序在訪問了一條數(shù)據(jù)之后障陶，在之后會有極大的可能再次訪問這條數(shù)據(jù)和訪問這條數(shù)據(jù)的相鄰數(shù)據(jù)”，所以索性直接加載4KB的數(shù)據(jù)到內(nèi)存中媳维，下次要訪問這一頁的數(shù)據(jù)時，直接從內(nèi)存中找州丹，可以減少磁盤IO次數(shù)，我們知道所计，磁盤IO是影響程序性能主要的因素，因為磁盤IO和內(nèi)存IO的速度是不可同日而語的。

或許看完上面那一大段描述夷都，還是有些抽象，所以我們索性回到數(shù)據(jù)庫層面中荣瑟，重新理解頁的概念劫谅。

拋開所有東西不談荞驴，假設還是我們剛才插入的那些數(shù)據(jù)，我們現(xiàn)在要找id = 5的數(shù)據(jù)鲫骗，依照最原始的方式，我們一定會想到的就是——遍歷术吝，沒錯，這也是我們剛開始學計算機的時候最常用的尋找數(shù)據(jù)的方式纪岁。那么我們就來看看漩氨，以遍歷的方式款青，我們找到id=5的數(shù)據(jù)，需要經(jīng)歷幾次磁盤IO康震。

首先，我們得先從id=1的數(shù)據(jù)開始讀起橘忱，然后判斷是否是我們需要的數(shù)據(jù)，如果不是潘拱，就再取id=2的數(shù)據(jù)泽铛，再進行判斷，循環(huán)往復弛随。毋庸置疑，在MySQL幫我們排好序之后愕够，我們需要經(jīng)歷五次磁盤IO，才能將5號數(shù)據(jù)找到并讀出來遂跟。

那么我們再來看看引入頁的概念之后，我們是如何讀數(shù)據(jù)的哄尔。

在引入頁的概念之后，MySQL會將多條數(shù)據(jù)存在一個叫“頁”的數(shù)據(jù)結(jié)構(gòu)中媒峡，當MySQL讀取id=1的數(shù)據(jù)時，會將id=1數(shù)據(jù)所在的頁整頁讀到內(nèi)存中，然后在內(nèi)存中進行遍歷判斷氯檐，由于內(nèi)存的IO速度比磁盤高很多，所以相對于磁盤IO，幾乎可以忽略不計拆挥，那么我們來看看這樣讀取數(shù)據(jù)我們需要經(jīng)歷幾次磁盤IO（假設每一頁可以存4條數(shù)據(jù)）。那么我們第一次會讀取id=1的數(shù)據(jù)汉矿，并且將id=1到id=4的數(shù)據(jù)全部讀到內(nèi)存中流强，這是第一次磁盤IO，第二次將讀取id=5的數(shù)據(jù)到內(nèi)存中柴淘，這是第二次磁盤IO敛熬。所以我們只需要經(jīng)歷2次磁盤IO就可以找到id=5的這條數(shù)據(jù)夕吻。

但其實，在MySQL的InnoDb引擎中庸诱，頁的大小是16KB，是操作系統(tǒng)的4倍，而int類型的數(shù)據(jù)是4個字節(jié)形导，其它類型的數(shù)據(jù)的字節(jié)數(shù)通常也在4000字節(jié)以內(nèi)，所以一頁是可以存放很多很多條數(shù)據(jù)的淋叶，而MySQL的數(shù)據(jù)正是以頁為基本單位組合而成的阎曹。

最初的頁結(jié)構(gòu)

上圖就是我們目前為止所理解的頁的結(jié)構(gòu)，他包含我們的多條數(shù)據(jù)煞檩，另外处嫌，MySQL的數(shù)據(jù)以頁組成，那么它有指向下一頁的指針和指向上一頁的指針斟湃。

那么說到這里赚楚，其實可以回答第一個問題了敛摘，MySQL實際上就是在我們插入數(shù)據(jù)的時候，就幫我們在頁中排好了序晌端，至于為什么要排序演痒，這里先賣個關子曾撤，接著往下看。

排序?qū)π阅艿挠绊?/h2>

上文中我們提了一個問題属瓣，為什么數(shù)據(jù)庫在插入數(shù)據(jù)時要對其進行排序呢？我們按正常順序插入數(shù)據(jù)不是頁挺好的嗎选泻？

這就要涉及到一個數(shù)據(jù)庫查詢流程的問題了短曾，無論如何儒鹿，我們是絕對不會去平白無故地在插入數(shù)據(jù)時增加一個操作來讓流程復雜化的，所以插入數(shù)據(jù)時排序一定有其目的株搔，就是優(yōu)化查詢的效率。

而我們不難看出，頁內(nèi)部存放數(shù)據(jù)的模塊，實質(zhì)上就是一個鏈表的結(jié)構(gòu)妓湘，鏈表的特點也就是增刪快坷随，查詢慢译暂，所以優(yōu)化查詢的效率是必須的劫乱。

• 基于單頁模式存儲的查詢流程

  還是基于我們第一節(jié)中的那張頁圖來談舰绘，我們插入了五條數(shù)據(jù)驳概，id分別是從1-5流济，那么假設我要找一個表中不存在的id并扇，假設id=-1出刷，那么現(xiàn)在的查詢流程就是：

  將id=1的這一整頁數(shù)據(jù)取出璧疗，進行逐個比對，那么當我們找到id=1的這條數(shù)據(jù)時馁龟，發(fā)現(xiàn)這個id大于我們所需要找的哪個id崩侠，由于數(shù)據(jù)庫在插入數(shù)據(jù)時，已經(jīng)進行過排序了坷檩，那么在id=1的數(shù)據(jù)后面却音，都是id>1的數(shù)據(jù)，所以我們就不需要再繼續(xù)往下尋找了矢炼。

  如果在插入時沒有進行排序盏求，那毋庸置疑，我們需要再繼續(xù)往下進行尋找雾叭，逐條查找直到到結(jié)尾也沒有找到這條數(shù)據(jù)料身，才能返回不存在這條數(shù)據(jù)。

當然胰锌，這只是排序優(yōu)化的冰山一角骗绕，接著往下看。

上述頁模式可能帶來的問題

說完了排序资昧，下面就來分析一下我們在第一節(jié)中的那幅圖酬土，對于大數(shù)據(jù)量下有什么弊端，或者換一個說法格带，我們可以怎么對這個模式進行優(yōu)化撤缴。

我們不難看出，在現(xiàn)階段我們了解的頁模式中叽唱，只有一個功能腹泌，就是在查詢某條數(shù)據(jù)的時候直接將一整頁的數(shù)據(jù)加載到內(nèi)存中，以減少硬盤IO次數(shù)尔觉，從而提高性能凉袱。但是，我們也可以看到侦铜，現(xiàn)在的頁模式內(nèi)部专甩，實際上是采用了鏈表的結(jié)構(gòu)，前一條數(shù)據(jù)指向后一條數(shù)據(jù)钉稍，本質(zhì)上還是通過數(shù)據(jù)的逐條比較來取出特定的數(shù)據(jù)涤躲。那么假設，我們這一頁中有一百萬條數(shù)據(jù)贡未，我們要查的數(shù)據(jù)正好在最后一個种樱，那么我們是不是一定要從前往后找到這一條數(shù)據(jù)呢蒙袍？如果是這樣，我們需要查找的次數(shù)就達到了一百萬次嫩挤，即使是在內(nèi)存中查找害幅，這個效率也是不高的。那么有什么辦法來優(yōu)化這種情況下的查找效率呢岂昭？

頁目錄的引入

我們可以打個比方以现，我們在看書的時候，如果要找到某一節(jié)约啊，而這一節(jié)我們并不知道在哪一頁邑遏，我們是不是就要從前往后，一節(jié)一節(jié)地去尋找我們需要地內(nèi)容地頁碼呢恰矩？答案是否定的记盒，因為在書的前面，存在目錄外傅，它會告訴你這一節(jié)在哪一頁纪吮，例如，第一節(jié)在第1頁栏豺、第二節(jié)在第13頁彬碱。在數(shù)據(jù)庫的頁中豆胸，實際上也使用了這種目錄的結(jié)構(gòu)奥洼，這就是頁目錄。

那么引入頁目錄之后晚胡，我們所理解的頁結(jié)構(gòu)灵奖，就變成了這樣：

加了頁目錄的頁結(jié)構(gòu)

分析一下這張圖，實際上頁目錄就像是我們在看書的時候書本的目錄一樣估盘，目錄項1就相當于第一節(jié)瓷患，目錄項2就相當于第二節(jié)，而每一條數(shù)據(jù)就相當于書本的每一頁遣妥，這張圖就可以解釋成擅编，第一節(jié)從第一頁開始，第二節(jié)從第三頁開始箫踩，而實際上爱态，每個目錄項會存放自己這個目錄項當中最小的id，也就是說境钟，目錄項1中會存放1锦担，而目錄項2會存放3。

那么對比一下數(shù)據(jù)庫在沒有頁目錄時候的查找流程慨削，假設要查找id=3的數(shù)據(jù)洞渔，在沒有頁目錄的情況下套媚，需要查找id=1、id=2磁椒、id=3堤瘤，三次才能找到該數(shù)據(jù)，而如果有頁目錄之后衷快，只需要先查看一下id=3存在于哪個目錄項下宙橱，然后直接通過目錄項進行數(shù)據(jù)的查找即可，如果在該目錄項下沒有找到這條數(shù)據(jù)蘸拔，那么就可以直接確定這條數(shù)據(jù)不存在师郑，這樣就大大提升了數(shù)據(jù)庫的查找效率，但是這種頁目錄的實現(xiàn)调窍，首先就需要基于數(shù)據(jù)是在已經(jīng)進行過排序的的場景下宝冕，才可以發(fā)揮其作用，所以看到這里邓萨，大家應該明白第二個問題了地梨，為什么數(shù)據(jù)庫在插入時會進行排序，這才是真正發(fā)揮排序的作用的地方缔恳。

頁的擴展

在上文中宝剖，我們基本上說明白了MySQL數(shù)據(jù)庫中頁的概念，以及它是如何基于頁來減少磁盤IO次數(shù)的歉甚，以及排序是如何優(yōu)化查詢的效率的万细。那么我們現(xiàn)在再來思考第三個問題：在開頭說頁的概念的時候，我們有說過纸泄，MySQL中每一頁的大小只有16KB赖钞，不會隨著數(shù)據(jù)的插入而自動擴容，所以這16KB不可能存下我們所有的數(shù)據(jù)聘裁，那么必定會有多個頁來存儲數(shù)據(jù)雪营，那么在多頁的情況下，MySQL中又是怎么組織這些頁的呢衡便？

針對這個問題献起，我們繼續(xù)來畫出我們現(xiàn)在所了解的多頁的結(jié)構(gòu)圖：

多頁結(jié)構(gòu)

可以看到，在數(shù)據(jù)不斷變多的情況下镣陕，MySQL會再去開辟新的頁來存放新的數(shù)據(jù)谴餐，而每個頁都有指向下一頁的指針和指向上一頁的指針，將所有頁組織起來（這里修改了一下數(shù)據(jù)茁彭，將每一列的數(shù)據(jù)都放到了數(shù)據(jù)區(qū)中总寒，其中第一個空格之前的代表id），第一頁中存放id為1-5的數(shù)據(jù)理肺，第二頁存放id為6-10的數(shù)據(jù)摄闸，第三頁存放id為11-15的數(shù)據(jù)善镰，需要注意的是在開辟新頁的時候，我們插入的數(shù)據(jù)不一定是放在新開辟的頁上年枕，而是要進行所有頁的數(shù)據(jù)比較炫欺，來決定這條插入的數(shù)據(jù)放在哪一頁上，而完成數(shù)據(jù)插入之后熏兄，最終的多頁結(jié)構(gòu)就會像上圖中畫的那樣品洛。

多頁模式

在多頁模式下，MySQL終于可以完成多數(shù)據(jù)的存儲了摩桶，就是采用開辟新頁的方式桥状，將多條數(shù)據(jù)放在不同的頁中，然后同樣采用鏈表的數(shù)據(jù)結(jié)構(gòu)硝清，將每一頁連接起來辅斟。那么可以思考第四個問題：多頁情況下是否對查詢效率有影響呢？

• 多頁模式對于查詢效率的影響

  針對這個問題芦拿，既然問出來了士飒，那么答案是肯定的，多頁會對查詢效率產(chǎn)生一定的影響蔗崎，影響主要就體現(xiàn)在酵幕，多頁其本質(zhì)也是一個鏈表結(jié)構(gòu)，只要是鏈表結(jié)構(gòu)缓苛，查詢效率一定不會高芳撒。假設數(shù)據(jù)又非常多條，數(shù)據(jù)庫就會開辟非常多的新頁他嫡，而這些新頁就會像鏈表一樣連接在一起番官，當我們要在這么多頁中查詢某條數(shù)據(jù)時庐完，它還是會從頭節(jié)點遍歷到存在我們要查找的那條數(shù)據(jù)所存在的頁上钢属，我們好不容易通過頁目錄優(yōu)化了頁中數(shù)據(jù)的查詢效率，現(xiàn)在又出現(xiàn)了以頁為單位的鏈表门躯，這不是前功盡棄了嗎淆党？

• 如何優(yōu)化多頁模式

  由于多頁模式會影響查詢的效率，那么肯定需要有一種方式來優(yōu)化多頁模式下的查詢讶凉。相信有同學已經(jīng)猜出來了染乌，既然我們可以用頁目錄來優(yōu)化頁內(nèi)的數(shù)據(jù)區(qū)，那么我們也可以采取類似的方式來優(yōu)化這種多頁的情況懂讯。是的荷憋，頁內(nèi)數(shù)據(jù)區(qū)和多頁模式本質(zhì)上都是鏈表，那么的確可以采用相同的方式來對其進行優(yōu)化褐望，它就是目錄頁勒庄。

  所以我們對比頁內(nèi)數(shù)據(jù)區(qū)串前，來分析如何優(yōu)化多頁結(jié)構(gòu)。在單頁時实蔽，我們采用了頁目錄的目錄項來指向一行數(shù)據(jù)荡碾，這條數(shù)據(jù)就是存在于這個目錄項中的最小數(shù)據(jù)，那么就可以通過頁目錄來查找所需數(shù)據(jù)局装。所以對于多頁結(jié)構(gòu)也可以采用這種方式坛吁，使用一個目錄項來指向某一頁，而這個目錄項存放的就是這一頁中存放的最小數(shù)據(jù)的索引值铐尚。和頁目錄不同的地方在于拨脉，這種目錄管理的級別是頁，而頁目錄管理的級別是行宣增。

  那么分析到這里女坑，我們多頁模式的結(jié)構(gòu)就會是下圖所示的這樣：

  形成B+樹

  存在一個目錄頁來管理頁目錄，目錄頁中的數(shù)據(jù)存放的就是指向的那一頁中最小的數(shù)據(jù)统舀。

  這里要注意的一點是：其實目錄頁的本質(zhì)也是頁匆骗，普通頁中存的數(shù)據(jù)是項目數(shù)據(jù)，而目錄頁中存的數(shù)據(jù)是普通頁的地址誉简。

  假設我們要查找id=19的數(shù)據(jù)碉就，那么按照以前的查找方式，我們需要從第一頁開始查找闷串，發(fā)現(xiàn)不存在那么再到第二頁查找瓮钥，一直找到第四頁才能找到id=19的數(shù)據(jù)，但是如果有了目錄頁烹吵，就可以使用id=19與目錄頁中存放的數(shù)據(jù)進行比較碉熄，發(fā)現(xiàn)19大于任何一條數(shù)據(jù)，于是進入id=16指向的頁進行查找肋拔，直接然后再通過頁內(nèi)的頁目錄行級別的數(shù)據(jù)的查找锈津，很快就可以找到id為19的數(shù)據(jù)了。隨著數(shù)據(jù)越來越多凉蜂，這種結(jié)構(gòu)的效率相對于普通的多頁模式琼梆，優(yōu)勢也就越來越明顯。

  回歸正題窿吩，相信有對MySQL比較了解的同學已經(jīng)發(fā)現(xiàn)了茎杂，我們畫的最終的這幅圖，就是MySQL中的一種索引結(jié)構(gòu)——B+樹纫雁。

B+樹的引入

B+樹的特點我在《[從入門到入土]令人脫發(fā)的數(shù)據(jù)庫底層設計》已經(jīng)有詳細敘述過了煌往，在這里就不重復敘述了，如果有不了解的同學可以去看這篇博客轧邪。

我們接著往下聊刽脖，我們將我們畫的存在目錄頁的多頁模式圖宏觀化悼粮，可以形成下面的這張圖：

多頁宏觀化

這就是我們兜兜轉(zhuǎn)轉(zhuǎn)由簡到繁形成的一顆B+樹。和常規(guī)B+樹有些許不同曾棕，這是一棵MySQL意義上的B+樹扣猫，MySQL的一種索引結(jié)構(gòu)，其中的每個節(jié)點就可以理解為是一個頁翘地，而葉子節(jié)點也就是數(shù)據(jù)頁申尤，除了葉子節(jié)點以外的節(jié)點就是目錄頁。這一點再圖中也可以看出來衙耕，非葉子節(jié)點只存放了索引昧穿，而只有葉子節(jié)點中存放了真實的數(shù)據(jù)，這也是符合B+樹的特點的橙喘。

• B+樹的優(yōu)勢

  1. 由于葉子節(jié)點上存放了所有的數(shù)據(jù)时鸵，并且有指針相連，每個葉子節(jié)點在邏輯上是相連的厅瞎，所以對于范圍查找比較友好饰潜。
  2. B+樹的所有數(shù)據(jù)都在葉子節(jié)點上，所以B+樹的查詢效率穩(wěn)定和簸，一般都是查詢3次彭雾。
  3. B+樹有利于數(shù)據(jù)庫的掃描。
  4. B+樹有利于磁盤的IO锁保，因為他的層高基本不會因為數(shù)據(jù)擴大而增高（三層樹結(jié)構(gòu)大概可以存放兩千萬數(shù)據(jù)量薯酝。

頁的完整結(jié)構(gòu)

說完了頁的概念和頁是如何一步一步地組合稱為B+樹的結(jié)構(gòu)之后，相信大家對于頁都有了一個比較清楚的認知爽柒，所以這里就要開始說說官方概念了吴菠，基于我們上文所說的，給出一個完整的頁結(jié)構(gòu)浩村，也算是對上文中自己理解頁結(jié)構(gòu)的一種補充做葵。

頁結(jié)構(gòu)

上圖為 Page 數(shù)據(jù)結(jié)構(gòu)，F(xiàn)ile Header 字段用于記錄 Page 的頭信息穴亏，其中比較重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段蜂挪，通過這兩個字段重挑，我們可以找到該頁的上一頁和下一頁嗓化，實際上所有頁通過兩個字段可以形成一條雙向鏈表。Page Header 字段用于記錄 Page 的狀態(tài)信息谬哀。接下來的 Infimum 和 Supremum 是兩個偽行記錄刺覆，Infimum（下確界）記錄比該頁中任何主鍵值都要小的值，Supremum （上確界）記錄比該頁中任何主鍵值都要大的值史煎，這個偽記錄分別構(gòu)成了頁中記錄的邊界谦屑。

User Records 中存放的是實際的數(shù)據(jù)行記錄驳糯，具體的行記錄結(jié)構(gòu)將在本文的第二節(jié)中詳細介紹。Free Space 中存放的是空閑空間氢橙，被刪除的行記錄會被記錄成空閑空間酝枢。Page Directory 記錄著與二叉查找相關的信息。File Trailer 存儲用于檢測數(shù)據(jù)完整性的校驗和等數(shù)據(jù)悍手。

來源:https://www.cnblogs.com/bdsir/p/8745553.html

B+樹頁結(jié)構(gòu)

基于B+樹聊聊MySQL的其它知識點

看到這里帘睦，我們已經(jīng)了解了MySQL從單條數(shù)據(jù)開始，到通過頁來減少磁盤IO次數(shù)坦康，并且在頁中實現(xiàn)了頁目錄來優(yōu)化頁中的查詢效率竣付，然后使用多頁模式來存儲大量的數(shù)據(jù)，最終使用目錄頁來實現(xiàn)多頁模式的查詢效率并形成我們口中的索引結(jié)構(gòu)——B+樹滞欠。既然說到這里了古胆，那我們就來聊聊MySQL的其他知識點。

• 聚簇索引和非聚簇索引

  關于聚簇索引和非聚簇索引在[從入門到入土]令人脫發(fā)的數(shù)據(jù)庫底層設計這篇文章中已經(jīng)有了詳細的介紹筛璧，這里簡單地說說逸绎，所謂聚簇索引，就是將索引和數(shù)據(jù)放到一起夭谤，找到索引也就找到了數(shù)據(jù)桶良，我們剛才看到的B+樹索引就是一種聚簇索引，而非聚簇索引就是將數(shù)據(jù)和索引分開沮翔，查找時需要先查找到索引陨帆，然后通過索引回表找到相應的數(shù)據(jù)。InnoDB有且只有一個聚簇索引采蚀，而MyISAM中都是非聚簇索引疲牵。

• 聯(lián)合索引的最左前綴匹配原則

  在MySQL數(shù)據(jù)庫中不僅可以對某一列建立索引，還可以對多列建立一個聯(lián)合索引榆鼠，而聯(lián)合索引存在一個最左前綴匹配原則的概念纲爸，如果基于B+樹來理解這個最左前綴匹配原則，相對來說就會容易很很多了妆够。

  首先我們基于文首的這張表建立一個聯(lián)合索引：

  create index idx_obj on user(age asc,height asc,weight asc)
  

  我們已經(jīng)了解了索引的數(shù)據(jù)結(jié)構(gòu)是一顆B+樹识啦，也了解了B+樹優(yōu)化查詢效率的其中一個因素就是對數(shù)據(jù)進行了排序，那么我們在創(chuàng)建idx_obj這個索引的時候神妹，也就相當于創(chuàng)建了一顆B+樹索引颓哮，而這個索引就是依據(jù)聯(lián)合索引的成員來進行排序，這里是age,height,weight鸵荠∶崦看過我之前那篇博客的同學知道，InnoDB中只要有主鍵被定義，那么主鍵列被作為一個聚簇索引姨伤，而其它索引都將被作為非聚簇索引哨坪，所以自然而然的，這個索引就會是一個非聚簇索引乍楚。

  所以根據(jù)這些我們可以得出結(jié)論：

  1. idx_obj這個索引會根據(jù)age,height,weight進行排序
  2. idx_obj這個索引是一個非聚簇索引当编，查詢時需要回表

  根據(jù)這兩個結(jié)論，首先需要了解的就是徒溪，如何排序凌箕？

  單列排序很簡單，比大小嘛词渤，誰都會牵舱，但是多列排序時基于什么原則的呢（重點）？

  實際上在MySQL中缺虐，聯(lián)合索引的排序有這么一個原則芜壁，從左往右依次比較大小，就拿剛才建立的索引舉例子高氮，他會先去比較age的大小慧妄，如果age的大小相同，那么比較height的大小剪芍，如果height也無法比較大小塞淹， 那么就比較weight的大小，最終對這個索引進行排序罪裹。

  那么根據(jù)這個排序我們也可以畫出一個B+樹饱普，這里就不像上文畫的那么詳細了，簡化一下：

  數(shù)據(jù)：

  多列索引數(shù)據(jù)

  B+樹：

  多列索引結(jié)構(gòu)

  注意：此時由于時非聚簇索引状共，所以葉子節(jié)點不在有數(shù)據(jù)套耕，而是存了一個主鍵索引，最終會通過主鍵索引來回表查詢數(shù)據(jù)峡继。

  B+樹的結(jié)構(gòu)有了冯袍，就可以通過這個來理解最左前綴匹配原則了。

  我們先寫一個查詢語句

  SELECT * FROM user WHERE age=1 and height = 2 and weight = 7
  

  毋庸置疑碾牌，這條語句一定會走idx_obj這個索引康愤。

  那么我們再看一個語句：

  SELECT * FROM user WHERE height=2 and weight = 7
  

  思考一下，這條SQL會走索引嗎舶吗？

  答案是否定的征冷，那么我們分析的方向就是，為什么這條語句不會走索引裤翩。

  上文中我們提到了一個多列的排序原則资盅，是從左到右進行比較然后排序的调榄，而我們的idx_obj這個索引從左到右依次是age,height,weight踊赠，所以當我們使用height和weight來作為查詢條件時呵扛，由于age的缺失，那么就無法從age來進行比較了筐带。看到這里可能有小伙伴會有疑問，那如果直接用height和weight來進行比較不可以嗎虐唠？顯然是不可以的贷痪，可以舉個例子，我們把缺失的這一列寫作一個問好帖鸦，那么這條語句的查詢條件就變成了?27芝薇，那么我們從這課B+樹的根節(jié)點開始，根節(jié)點上有127和365作儿，那么以height和weight來進行比較的話洛二，走的一定是127這一邊，但是如果缺失的列數(shù)字是大于3的呢攻锰？比如427晾嘶，527，627娶吞，那么如果走索引來查詢數(shù)據(jù)垒迂，將會丟失數(shù)據(jù)，錯誤查詢妒蛇。所以這種情況下是絕對不會走索引進行查詢的机断。這就是最左前綴匹配原則的成因。

  1.最左前綴匹配原則绣夺，MySQL會一直向右匹配直到遇到范圍查詢（>毫缆、<、between乐导、like）就停止匹配苦丁，比如 a=3 and b=4 and c>5 and d=6,如果建立(a,b,c,d)順序的索引，d是無法使用索引的物臂，如果建立(a,b,d,c)的索引則都可以使用到旺拉，a、b棵磷、d的順序可以任意調(diào)整蛾狗。
  2.=和in可以亂序，比如 a=1 and b=2 and c=3 建立(a,b,c)索引可以任意順序仪媒，MySQL的查詢優(yōu)化器會幫你優(yōu)化成索引可以識別的形式沉桌。

  根據(jù)我們了解的可以得出結(jié)論：

  只要無法進行排序比較大小的谢鹊，就無法走聯(lián)合索引。

  可以再看幾個語句：

  SELECT * FROM user WHERE age=1 and height = 2
  

  這條語句是可以走idx_obj索引的留凭，因為它可以通過比較 (12?<365)佃扼。

  SELECT * FROM user WHERE age=1 and weight=7
  

  這條語句也是可以走ind_obj索引的，因為它也可以通過比較(1?7<365)蔼夜，走左子樹兼耀，但是實際上weight并沒有用到索引，因為根據(jù)最左匹配原則求冷，如果有兩頁的age都等于1瘤运，那么會去比較height，但是height在這里并不作為查詢條件匠题，所以MySQL會將這兩頁全都加載到內(nèi)存中進行最后的weight字段的比較拯坟，進行掃描查詢。

  SELECT * FROM user where age>1
  

  這條語句不會走索引韭山，但是可以走索引郁季。這句話是什么意思呢？這條SQL很特殊掠哥，由于其存在可以比較的索引巩踏，所以它走索引也可以查詢出結(jié)果，但是由于這種情況是范圍查詢并且是全字段查詢续搀，如果走索引塞琼，還需要進行回表，MySQL查詢優(yōu)化器就會認為走索引的效率比全表掃描還要低禁舷，所以MySQL會去優(yōu)化它彪杉，讓他直接進行全表掃描。

  SELECT * FROM user WEHRE age=1 and height>2 and weight=7
  

  這條語句是可以走索引的牵咙，因為它可以通過age進行比較派近，但是weight不會用到索引，因為height是范圍查找洁桌，與第二條語句類似渴丸，如果有兩頁的height都大于2，那么MySQL會將兩頁的數(shù)據(jù)都加載進內(nèi)存另凌，然后再來通過weight匹配正確的數(shù)據(jù)谱轨。

• 為什么InnoDB只有一個聚簇索引，而不將所有索引都使用聚簇索引吠谢？

  因為聚簇索引是將索引和數(shù)據(jù)都存放在葉子節(jié)點中土童，如果所有的索引都用聚簇索引，則每一個索引都將保存一份數(shù)據(jù)工坊，會造成數(shù)據(jù)的冗余献汗，在數(shù)據(jù)量很大的情況下敢订，這種數(shù)據(jù)冗余是很消耗資源的。

補充兩個關于索引的點

這兩個點也是上次寫關于索引的博客時漏下的罢吃，這里補上楚午。

1. 什么情況下會發(fā)生明明創(chuàng)建了索引，但是執(zhí)行的時候并沒有通過索引呢刃麸？
   科普時間——查詢優(yōu)化器 一條SQL語句的查詢醒叁，可以有不同的執(zhí)行方案司浪，至于最終選擇哪種方案泊业，需要通過優(yōu)化器進行選擇，選擇執(zhí)行成本最低的方案啊易。 在一條單表查詢語句真正執(zhí)行之前吁伺，MySQL的查詢優(yōu)化器會找出執(zhí)行該語句所有可能使用的方案，對比之后找出成本最低的方案租谈。這個成本最低的方案就是所謂的執(zhí)行計劃篮奄。 優(yōu)化過程大致如下： 1、根據(jù)搜索條件割去，找出所有可能使用的索引 2窟却、計算全表掃描的代價 3、計算使用不同索引執(zhí)行查詢的代價 4呻逆、對比各種執(zhí)行方案的代價夸赫，找出成本最低的那一個
   。
   參考鏈接：https://juejin.im/post/5d23ef4ce51d45572c0600bc

   根據(jù)我們剛才的那張表的非聚簇索引咖城，這條語句就是由于查詢優(yōu)化器的作用茬腿，造成沒有走索引：

   SELECT * FROM user where age>1
   

2. 在稀疏索引情況下通常需要通過葉子節(jié)點的指針回表查詢數(shù)據(jù)，什么情況下不需要回表宜雀？
   科普時間——覆蓋索引 覆蓋索引（covering index）指一個查詢語句的執(zhí)行只用從索引中就能夠取得切平，不必從數(shù)據(jù)表中讀取。也可以稱之為實現(xiàn)了索引覆蓋辐董。 當一條查詢語句符合覆蓋索引條件時悴品，MySQL只需要通過索引就可以返回查詢所需要的數(shù)據(jù)，這樣避免了查到索引后再返回表操作简烘，減少I/O提高效率苔严。 如，表covering_index_sample中有一個普通索引 idx_key1_key2(key1,key2)夸研。當我們通過SQL語句：select key2 from covering_index_sample where key1 = 'keytest';的時候邦蜜，就可以通過覆蓋索引查詢，無需回表亥至。
   參考鏈接：https://juejin.im/post/5d23ef4ce51d45572c0600bc

   例如:

   SELECT age FROM user where age = 1
   

   這句話就不需要進行回表查詢悼沈。

結(jié)語

本篇文章著重聊了一下關于MySQL的索引結(jié)構(gòu)贱迟，從零開始慢慢構(gòu)建了一個B+樹索引，并且根據(jù)這個過程談了B+樹是如何一步一步去優(yōu)化查詢效率的絮供。

簡單地歸納一下就是：

排序：優(yōu)化查詢的根本衣吠，插入時進行排序?qū)嶋H上就是為了優(yōu)化查詢的效率。

頁：用于減少IO次數(shù)壤靶，還可以利用程序局部性原理缚俏，來稍微提高查詢效率。

頁目錄：用于規(guī)避鏈表的軟肋贮乳，避免在查詢時進行鏈表的掃描忧换。

多頁：數(shù)據(jù)量增加的情況下開辟新頁來保存數(shù)據(jù)。

目錄頁：“特殊的頁目錄”向拆，其中保存的數(shù)據(jù)是頁的地址亚茬。查詢時可以通過目錄頁快速定位到頁，避免多頁的掃描浓恳。

歡迎大家訪問我的個人博客：Object's Blog