我會(huì)談?wù)剬?duì)于索引結(jié)構(gòu)我自己的看法，以及分享如何從零開(kāi)始一層一層向上最終理解索引結(jié)構(gòu)。
從一個(gè)簡(jiǎn)單的表開(kāi)始
createtableuser(idintprimarykey,ageint,heightint,weightint,namevarchar(32))engine=innoDb;
相信只要入門(mén)數(shù)據(jù)庫(kù)的同學(xué)都可以理解這個(gè)語(yǔ)句，我們也將從這個(gè)最簡(jiǎn)單的表開(kāi)始，一步步地理解MySQL的索引結(jié)構(gòu)。
首先，我們往這個(gè)表中插入一些數(shù)據(jù)。
INSERTINTOuser(id,age,height,weight,name)VALUES(2,1,2,7,'小吉');INSERTINTOuser(id,age,height,weight,name)VALUES(5,2,1,8,'小尼');INSERTINTOuser(id,age,height,weight,name)VALUES(1,4,3,1,'小泰');INSERTINTOuser(id,age,height,weight,name)VALUES(4,1,5,2,'小美');INSERTINTOuser(id,age,height,weight,name)VALUES(3,5,6,7,'小蔡');
我們來(lái)查一下，看看這些數(shù)據(jù)是否已經(jīng)放入表中。
select*fromuser;
可以看到，數(shù)據(jù)已經(jīng)完整地放到了我們創(chuàng)建的user表中。
但是不知道大家發(fā)現(xiàn)了什么沒(méi)有，好像發(fā)生了一件非常詭異的事情，我們插入的數(shù)據(jù)好像亂序了…
MySQL好像悄悄的給我們按照id排了個(gè)序。
為什么會(huì)出現(xiàn)MySQL在我們沒(méi)有顯式排序的情況下，默默幫我們排了序呢？它是在什么時(shí)候進(jìn)行排序的？
頁(yè)的引入
不知道大家畢業(yè)多長(zhǎng)時(shí)間了，作為一個(gè)剛學(xué)完操作系統(tǒng)不久的學(xué)渣，頁(yè)的概念依舊在腦中還沒(méi)有變涼。其實(shí)MySQL中也有類(lèi)似頁(yè)的邏輯存儲(chǔ)單位，聽(tīng)我慢慢道來(lái)。
在操作系統(tǒng)的概念中，當(dāng)我們往磁盤(pán)中取數(shù)據(jù)，假設(shè)要取出的數(shù)據(jù)的大小是1KB，但是操作系統(tǒng)并不會(huì)只取出這1kb的數(shù)據(jù)，而是會(huì)取出4KB的數(shù)據(jù)，因?yàn)椴僮飨到y(tǒng)的一個(gè)頁(yè)表項(xiàng)的大小是4KB。
那為什么我們只需要1KB的數(shù)據(jù)，但是操作系統(tǒng)要取出4KB的數(shù)據(jù)呢？
這就涉及到一個(gè)程序局部性的概念，具體的概念我背不清了，大概就是“一個(gè)程序在訪問(wèn)了一條數(shù)據(jù)之后，在之后會(huì)有極大的可能再次訪問(wèn)這條數(shù)據(jù)和訪問(wèn)這條數(shù)據(jù)的相鄰數(shù)據(jù)”
所以索性直接加載4KB的數(shù)據(jù)到內(nèi)存中，下次要訪問(wèn)這一頁(yè)的數(shù)據(jù)時(shí)，直接從內(nèi)存中找，可以減少磁盤(pán)IO次數(shù)，我們知道，磁盤(pán)IO是影響程序性能主要的因素，因?yàn)榇疟P(pán)IO和內(nèi)存IO的速度是不可同日而語(yǔ)的。
或許看完上面那一大段描述，還是有些抽象，所以我們索性回到數(shù)據(jù)庫(kù)層面中，重新理解頁(yè)的概念。
拋開(kāi)所有東西不談，假設(shè)還是我們剛才插入的那些數(shù)據(jù)，我們現(xiàn)在要找id = 5的數(shù)據(jù)
依照最原始的方式，我們一定會(huì)想到的就是——遍歷，沒(méi)錯(cuò)，這也是我們剛開(kāi)始學(xué)計(jì)算機(jī)的時(shí)候最常用的尋找數(shù)據(jù)的方式。
那么我們就來(lái)看看，以遍歷的方式，我們找到id=5的數(shù)據(jù)，需要經(jīng)歷幾次磁盤(pán)IO。
首先，我們得先從id=1的數(shù)據(jù)開(kāi)始讀起，然后判斷是否是我們需要的數(shù)據(jù)，如果不是，就再取id=2的數(shù)據(jù)，再進(jìn)行判斷，循環(huán)往復(fù)。
毋庸置疑，在MySQL幫我們排好序之后，我們需要經(jīng)歷五次磁盤(pán)IO，才能將5號(hào)數(shù)據(jù)找到并讀出來(lái)。
那么我們?cè)賮?lái)看看引入頁(yè)的概念之后，我們是如何讀數(shù)據(jù)的。
在引入頁(yè)的概念之后，MySQL會(huì)將多條數(shù)據(jù)存在一個(gè)叫“頁(yè)”的數(shù)據(jù)結(jié)構(gòu)中，當(dāng)MySQL讀取id=1的數(shù)據(jù)時(shí)，會(huì)將id=1數(shù)據(jù)所在的頁(yè)整頁(yè)讀到內(nèi)存中，然后在內(nèi)存中進(jìn)行遍歷判斷
由于內(nèi)存的IO速度比磁盤(pán)高很多，所以相對(duì)于磁盤(pán)IO，幾乎可以忽略不計(jì)，那么我們來(lái)看看這樣讀取數(shù)據(jù)我們需要經(jīng)歷幾次磁盤(pán)IO（假設(shè)每一頁(yè)可以存4條數(shù)據(jù)）。
那么我們第一次會(huì)讀取id=1的數(shù)據(jù)，并且將id=1到id=4的數(shù)據(jù)全部讀到內(nèi)存中，這是第一次磁盤(pán)IO，第二次將讀取id=5的數(shù)據(jù)到內(nèi)存中，這是第二次磁盤(pán)IO。所以我們只需要經(jīng)歷2次磁盤(pán)IO就可以找到id=5的這條數(shù)據(jù)。
但其實(shí)，在MySQL的InnoDb引擎中，頁(yè)的大小是16KB，是操作系統(tǒng)的4倍，而int類(lèi)型的數(shù)據(jù)是4個(gè)字節(jié)，其它類(lèi)型的數(shù)據(jù)的字節(jié)數(shù)通常也在4000字節(jié)以?xún)?nèi)，所以一頁(yè)是可以存放很多很多條數(shù)據(jù)的，而MySQL的數(shù)據(jù)正是以頁(yè)為基本單位組合而成的。
上圖就是我們目前為止所理解的頁(yè)的結(jié)構(gòu)，他包含我們的多條數(shù)據(jù)，另外，MySQL的數(shù)據(jù)以頁(yè)組成，那么它有指向下一頁(yè)的指針和指向上一頁(yè)的指針。
那么說(shuō)到這里，其實(shí)可以回答第一個(gè)問(wèn)題了，MySQL實(shí)際上就是在我們插入數(shù)據(jù)的時(shí)候，就幫我們?cè)陧?yè)中排好了序，至于為什么要排序，這里先賣(mài)個(gè)關(guān)子，接著往下看。
排序?qū)π阅艿挠绊?/h2>
上文中我們提了一個(gè)問(wèn)題，為什么數(shù)據(jù)庫(kù)在插入數(shù)據(jù)時(shí)要對(duì)其進(jìn)行排序呢？我們按正常順序插入數(shù)據(jù)不是也挺好的嗎？
這就要涉及到一個(gè)數(shù)據(jù)庫(kù)查詢(xún)流程的問(wèn)題了，無(wú)論如何，我們是絕對(duì)不會(huì)去平白無(wú)故地在插入數(shù)據(jù)時(shí)增加一個(gè)操作來(lái)讓流程復(fù)雜化的，所以插入數(shù)據(jù)時(shí)排序一定有其目的，就是優(yōu)化查詢(xún)的效率。
而我們不難看出，頁(yè)內(nèi)部存放數(shù)據(jù)的模塊，實(shí)質(zhì)上就是一個(gè)鏈表的結(jié)構(gòu)，鏈表的特點(diǎn)也就是增刪快，查詢(xún)慢，所以?xún)?yōu)化查詢(xún)的效率是必須的。
基于單頁(yè)模式存儲(chǔ)的查詢(xún)流程
還是基于我們第一節(jié)中的那張頁(yè)圖來(lái)談，我們插入了五條數(shù)據(jù)，id分別是從1-5，那么假設(shè)我要找一個(gè)表中不存在的id，假設(shè)id=-1，那么現(xiàn)在的查詢(xún)流程就是：
將id=1的這一整頁(yè)數(shù)據(jù)取出，進(jìn)行逐個(gè)比對(duì)，那么當(dāng)我們找到id=1的這條數(shù)據(jù)時(shí)，發(fā)現(xiàn)這個(gè)id大于我們所需要找的哪個(gè)id，由于數(shù)據(jù)庫(kù)在插入數(shù)據(jù)時(shí)，已經(jīng)進(jìn)行過(guò)排序了，那么在id=1的數(shù)據(jù)后面，都是id>1的數(shù)據(jù)，所以我們就不需要再繼續(xù)往下尋找了。
如果在插入時(shí)沒(méi)有進(jìn)行排序，那毋庸置疑，我們需要再繼續(xù)往下進(jìn)行尋找，逐條查找直到到結(jié)尾也沒(méi)有找到這條數(shù)據(jù)，才能返回不存在這條數(shù)據(jù)。
當(dāng)然，這只是排序優(yōu)化的冰山一角，接著往下看。
上述頁(yè)模式可能帶來(lái)的問(wèn)題
說(shuō)完了排序，下面就來(lái)分析一下我們?cè)诘谝还?jié)中的那幅圖，對(duì)于大數(shù)據(jù)量下有什么弊端，或者換一個(gè)說(shuō)法，我們可以怎么對(duì)這個(gè)模式進(jìn)行優(yōu)化。
我們不難看出，在現(xiàn)階段我們了解的頁(yè)模式中，只有一個(gè)功能，就是在查詢(xún)某條數(shù)據(jù)的時(shí)候直接將一整頁(yè)的數(shù)據(jù)加載到內(nèi)存中，以減少硬盤(pán)IO次數(shù)，從而提高性能。
但是，我們也可以看到，現(xiàn)在的頁(yè)模式內(nèi)部，實(shí)際上是采用了鏈表的結(jié)構(gòu)，前一條數(shù)據(jù)指向后一條數(shù)據(jù)，本質(zhì)上還是通過(guò)數(shù)據(jù)的逐條比較來(lái)取出特定的數(shù)據(jù)。
那么假設(shè)，我們這一頁(yè)中有一百萬(wàn)條數(shù)據(jù)，我們要查的數(shù)據(jù)正好在最后一個(gè)，那么我們是不是一定要從前往后找到這一條數(shù)據(jù)呢？
如果是這樣，我們需要查找的次數(shù)就達(dá)到了一百萬(wàn)次，即使是在內(nèi)存中查找，這個(gè)效率也是不高的。那么，有什么辦法來(lái)優(yōu)化這種情況下的查找效率呢？
頁(yè)目錄的引入
我們可以打個(gè)比方，我們?cè)诳磿?shū)的時(shí)候，如果要找到某一節(jié)，而這一節(jié)我們并不知道在哪一頁(yè)，我們是不是就要從前往后，一節(jié)一節(jié)地去尋找我們需要的內(nèi)容的頁(yè)碼呢？
答案是否定的，因?yàn)樵跁?shū)的前面，存在目錄，它會(huì)告訴你這一節(jié)在哪一頁(yè)，例如，第一節(jié)在第1頁(yè)、第二節(jié)在第13頁(yè)。在數(shù)據(jù)庫(kù)的頁(yè)中，實(shí)際上也使用了這種目錄的結(jié)構(gòu)，這就是頁(yè)目錄。
那么引入頁(yè)目錄之后，我們所理解的頁(yè)結(jié)構(gòu)，就變成了這樣：
分析一下這張圖，實(shí)際上頁(yè)目錄就像是我們?cè)诳磿?shū)的時(shí)候書(shū)本的目錄一樣，目錄項(xiàng)1就相當(dāng)于第一節(jié)，目錄項(xiàng)2就相當(dāng)于第二節(jié)，而每一條數(shù)據(jù)就相當(dāng)于書(shū)本的每一頁(yè)
這張圖就可以解釋成，第一節(jié)從第一頁(yè)開(kāi)始，第二節(jié)從第三頁(yè)開(kāi)始，而實(shí)際上，每個(gè)目錄項(xiàng)會(huì)存放自己這個(gè)目錄項(xiàng)當(dāng)中最小的id，也就是說(shuō)，目錄項(xiàng)1中會(huì)存放1，而目錄項(xiàng)2會(huì)存放3。
那么對(duì)比一下數(shù)據(jù)庫(kù)在沒(méi)有頁(yè)目錄時(shí)候的查找流程，假設(shè)要查找id=3的數(shù)據(jù)，在沒(méi)有頁(yè)目錄的情況下，需要查找id=1、id=2、id=3，三次才能找到該數(shù)據(jù)，而如果有頁(yè)目錄之后，只需要先查看一下id=3存在于哪個(gè)目錄項(xiàng)下，然后直接通過(guò)目錄項(xiàng)進(jìn)行數(shù)據(jù)的查找即可
如果在該目錄項(xiàng)下沒(méi)有找到這條數(shù)據(jù)，那么就可以直接確定這條數(shù)據(jù)不存在，這樣就大大提升了數(shù)據(jù)庫(kù)的查找效率，但是這種頁(yè)目錄的實(shí)現(xiàn)，首先就需要基于數(shù)據(jù)是在已經(jīng)進(jìn)行過(guò)排序的的場(chǎng)景下，才可以發(fā)揮其作用，所以看到這里，大家應(yīng)該明白第二個(gè)問(wèn)題了，為什么數(shù)據(jù)庫(kù)在插入時(shí)會(huì)進(jìn)行排序，這才是真正發(fā)揮排序的作用的地方。
頁(yè)的擴(kuò)展
在上文中，我們基本上說(shuō)明白了MySQL數(shù)據(jù)庫(kù)中頁(yè)的概念，以及它是如何基于頁(yè)來(lái)減少磁盤(pán)IO次數(shù)的，以及排序是如何優(yōu)化查詢(xún)的效率的。
那么我們現(xiàn)在再來(lái)思考第三個(gè)問(wèn)題：在開(kāi)頭說(shuō)頁(yè)的概念的時(shí)候，我們有說(shuō)過(guò)，MySQL中每一頁(yè)的大小只有16KB，不會(huì)隨著數(shù)據(jù)的插入而自動(dòng)擴(kuò)容，所以這16KB不可能存下我們所有的數(shù)據(jù)，那么必定會(huì)有多個(gè)頁(yè)來(lái)存儲(chǔ)數(shù)據(jù)，那么在多頁(yè)的情況下，MySQL中又是怎么組織這些頁(yè)的呢？
針對(duì)這個(gè)問(wèn)題，我們繼續(xù)來(lái)畫(huà)出我們現(xiàn)在所了解的多頁(yè)的結(jié)構(gòu)圖：
可以看到，在數(shù)據(jù)不斷變多的情況下，MySQL會(huì)再去開(kāi)辟新的頁(yè)來(lái)存放新的數(shù)據(jù)，而每個(gè)頁(yè)都有指向下一頁(yè)的指針和指向上一頁(yè)的指針，將所有頁(yè)組織起來(lái)（這里修改了一下數(shù)據(jù)，將每一列的數(shù)據(jù)都放到了數(shù)據(jù)區(qū)中，其中第一個(gè)空格之前的代表id），第一頁(yè)中存放id為1-5的數(shù)據(jù)，第二頁(yè)存放id為6-10的數(shù)據(jù)，第三頁(yè)存放id為11-15的數(shù)據(jù)
需要注意的是在開(kāi)辟新頁(yè)的時(shí)候，我們插入的數(shù)據(jù)不一定是放在新開(kāi)辟的頁(yè)上，而是要進(jìn)行所有頁(yè)的數(shù)據(jù)比較，來(lái)決定這條插入的數(shù)據(jù)放在哪一頁(yè)上，而完成數(shù)據(jù)插入之后，最終的多頁(yè)結(jié)構(gòu)就會(huì)像上圖中畫(huà)的那樣。
多頁(yè)模式
在多頁(yè)模式下，MySQL終于可以完成多數(shù)據(jù)的存儲(chǔ)了，就是采用開(kāi)辟新頁(yè)的方式，將多條數(shù)據(jù)放在不同的頁(yè)中，然后同樣采用鏈表的數(shù)據(jù)結(jié)構(gòu)，將每一頁(yè)連接起來(lái)。
那么可以思考第四個(gè)問(wèn)題：多頁(yè)情況下是否對(duì)查詢(xún)效率有影響呢？
多頁(yè)模式對(duì)于查詢(xún)效率的影響
針對(duì)這個(gè)問(wèn)題，既然問(wèn)出來(lái)了，那么答案是肯定的，多頁(yè)會(huì)對(duì)查詢(xún)效率產(chǎn)生一定的影響，影響主要就體現(xiàn)在，多頁(yè)其本質(zhì)也是一個(gè)鏈表結(jié)構(gòu)，只要是鏈表結(jié)構(gòu)，查詢(xún)效率一定不會(huì)高。
假設(shè)數(shù)據(jù)又非常多條，數(shù)據(jù)庫(kù)就會(huì)開(kāi)辟非常多的新頁(yè)，而這些新頁(yè)就會(huì)像鏈表一樣連接在一起，當(dāng)我們要在這么多頁(yè)中查詢(xún)某條數(shù)據(jù)時(shí)，它還是會(huì)從頭節(jié)點(diǎn)遍歷到存在我們要查找的那條數(shù)據(jù)所存在的頁(yè)上，我們好不容易通過(guò)頁(yè)目錄優(yōu)化了頁(yè)中數(shù)據(jù)的查詢(xún)效率，現(xiàn)在又出現(xiàn)了以頁(yè)為單位的鏈表，這不是前功盡棄了嗎？
如何優(yōu)化多頁(yè)模式
由于多頁(yè)模式會(huì)影響查詢(xún)的效率，那么肯定需要有一種方式來(lái)優(yōu)化多頁(yè)模式下的查詢(xún)。相信有同學(xué)已經(jīng)猜出來(lái)了，既然我們可以用頁(yè)目錄來(lái)優(yōu)化頁(yè)內(nèi)的數(shù)據(jù)區(qū)，那么我們也可以采取類(lèi)似的方式來(lái)優(yōu)化這種多頁(yè)的情況。
是的，頁(yè)內(nèi)數(shù)據(jù)區(qū)和多頁(yè)模式本質(zhì)上都是鏈表，那么的確可以采用相同的方式來(lái)對(duì)其進(jìn)行優(yōu)化，它就是目錄頁(yè)。
所以我們對(duì)比頁(yè)內(nèi)數(shù)據(jù)區(qū)，來(lái)分析如何優(yōu)化多頁(yè)結(jié)構(gòu)。在單頁(yè)時(shí)，我們采用了頁(yè)目錄的目錄項(xiàng)來(lái)指向一行數(shù)據(jù)，這條數(shù)據(jù)就是存在于這個(gè)目錄項(xiàng)中的最小數(shù)據(jù)，那么就可以通過(guò)頁(yè)目錄來(lái)查找所需數(shù)據(jù)。
所以對(duì)于多頁(yè)結(jié)構(gòu)也可以采用這種方式，使用一個(gè)目錄項(xiàng)來(lái)指向某一頁(yè)，而這個(gè)目錄項(xiàng)存放的就是這一頁(yè)中存放的最小數(shù)據(jù)的索引值。和頁(yè)目錄不同的地方在于，這種目錄管理的級(jí)別是頁(yè)，而頁(yè)目錄管理的級(jí)別是行。
那么分析到這里，我們多頁(yè)模式的結(jié)構(gòu)就會(huì)是下圖所示的這樣：
存在一個(gè)目錄頁(yè)來(lái)管理頁(yè)目錄，目錄頁(yè)中的數(shù)據(jù)存放的就是指向的那一頁(yè)中最小的數(shù)據(jù)。
這里要注意的一點(diǎn)是：其實(shí)目錄頁(yè)的本質(zhì)也是頁(yè)，普通頁(yè)中存的數(shù)據(jù)是項(xiàng)目數(shù)據(jù)，而目錄頁(yè)中存的數(shù)據(jù)是普通頁(yè)的地址。
假設(shè)我們要查找id=19的數(shù)據(jù)，那么按照以前的查找方式，我們需要從第一頁(yè)開(kāi)始查找，發(fā)現(xiàn)不存在那么再到第二頁(yè)查找，一直找到第四頁(yè)才能找到id=19的數(shù)據(jù)
但是如果有了目錄頁(yè)，就可以使用id=19與目錄頁(yè)中存放的數(shù)據(jù)進(jìn)行比較，發(fā)現(xiàn)19大于任何一條數(shù)據(jù)，于是進(jìn)入id=16指向的頁(yè)進(jìn)行查找，直接然后再通過(guò)頁(yè)內(nèi)的頁(yè)目錄行級(jí)別的數(shù)據(jù)的查找，很快就可以找到id為19的數(shù)據(jù)了。
隨著數(shù)據(jù)越來(lái)越多，這種結(jié)構(gòu)的效率相對(duì)于普通的多頁(yè)模式，優(yōu)勢(shì)也就越來(lái)越明顯。
回歸正題，相信有對(duì)MySQL比較了解的同學(xué)已經(jīng)發(fā)現(xiàn)了，我們畫(huà)的最終的這幅圖，就是MySQL中的一種索引結(jié)構(gòu)——B+樹(shù)。
B+樹(shù)的引入
B+樹(shù)的特點(diǎn)我在《令人脫發(fā)的數(shù)據(jù)庫(kù)底層設(shè)計(jì)》已經(jīng)有詳細(xì)敘述過(guò)了，在這里就不重復(fù)敘述
我們接著往下聊，我們將我們畫(huà)的存在目錄頁(yè)的多頁(yè)模式圖宏觀化，可以形成下面的這張圖：
這就是我們兜兜轉(zhuǎn)轉(zhuǎn)由簡(jiǎn)到繁形成的一顆B+樹(shù)。和常規(guī)B+樹(shù)有些許不同，這是一棵MySQL意義上的B+樹(shù)，MySQL的一種索引結(jié)構(gòu)，其中的每個(gè)節(jié)點(diǎn)就可以理解為是一個(gè)頁(yè)，而葉子節(jié)點(diǎn)也就是數(shù)據(jù)頁(yè)，除了葉子節(jié)點(diǎn)以外的節(jié)點(diǎn)就是目錄頁(yè)。
這一點(diǎn)在圖中也可以看出來(lái)，非葉子節(jié)點(diǎn)只存放了索引，而只有葉子節(jié)點(diǎn)中存放了真實(shí)的數(shù)據(jù)，這也是符合B+樹(shù)的特點(diǎn)的。
B+樹(shù)的優(yōu)勢(shì)
由于葉子節(jié)點(diǎn)上存放了所有的數(shù)據(jù)，并且有指針相連，每個(gè)葉子節(jié)點(diǎn)在邏輯上是相連的，所以對(duì)于范圍查找比較友好。
B+樹(shù)的所有數(shù)據(jù)都在葉子節(jié)點(diǎn)上，所以B+樹(shù)的查詢(xún)效率穩(wěn)定，一般都是查詢(xún)3次。
B+樹(shù)有利于數(shù)據(jù)庫(kù)的掃描。
B+樹(shù)有利于磁盤(pán)的IO，因?yàn)樗膶痈呋静粫?huì)因?yàn)閿?shù)據(jù)擴(kuò)大而增高（三層樹(shù)結(jié)構(gòu)大概可以存放兩千萬(wàn)數(shù)據(jù)量。
頁(yè)的完整結(jié)構(gòu)
說(shuō)完了頁(yè)的概念和頁(yè)是如何一步一步地組合稱(chēng)為B+樹(shù)的結(jié)構(gòu)之后，相信大家對(duì)于頁(yè)都有了一個(gè)比較清楚的認(rèn)知，所以這里就要開(kāi)始說(shuō)說(shuō)官方概念了
基于我們上文所說(shuō)的，給出一個(gè)完整的頁(yè)結(jié)構(gòu)，也算是對(duì)上文中自己理解頁(yè)結(jié)構(gòu)的一種補(bǔ)充。
上圖為 Page 數(shù)據(jù)結(jié)構(gòu)，F(xiàn)ile Header 字段用于記錄 Page 的頭信息，其中比較重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段，通過(guò)這兩個(gè)字段，我們可以找到該頁(yè)的上一頁(yè)和下一頁(yè)，實(shí)際上所有頁(yè)通過(guò)兩個(gè)字段可以形成一條雙向鏈表。
Page Header 字段用于記錄 Page 的狀態(tài)信息。接下來(lái)的 Infimum 和 Supremum 是兩個(gè)偽行記錄，Infimum（下確界）記錄比該頁(yè)中任何主鍵值都要小的值，Supremum （上確界）記錄比該頁(yè)中任何主鍵值都要大的值，這個(gè)偽記錄分別構(gòu)成了頁(yè)中記錄的邊界。
User Records 中存放的是實(shí)際的數(shù)據(jù)行記錄，具體的行記錄結(jié)構(gòu)將在本文的第二節(jié)中詳細(xì)介紹。Free Space 中存放的是空閑空間，被刪除的行記錄會(huì)被記錄成空閑空間。Page Directory 記錄著與二叉查找相關(guān)的信息。File Trailer 存儲(chǔ)用于檢測(cè)數(shù)據(jù)完整性的校驗(yàn)和等數(shù)據(jù)。
引用來(lái)源：https://www.cnblogs.com/bdsir/p/8745553.html
基于B+樹(shù)聊聊MySQL的其它知識(shí)點(diǎn)
看到這里，我們已經(jīng)了解了MySQL從單條數(shù)據(jù)開(kāi)始，到通過(guò)頁(yè)來(lái)減少磁盤(pán)IO次數(shù)，并且在頁(yè)中實(shí)現(xiàn)了頁(yè)目錄來(lái)優(yōu)化頁(yè)中的查詢(xún)效率，然后使用多頁(yè)模式來(lái)存儲(chǔ)大量的數(shù)據(jù)，最終使用目錄頁(yè)來(lái)實(shí)現(xiàn)多頁(yè)模式的查詢(xún)效率并形成我們口中的索引結(jié)構(gòu)——B+樹(shù)。既然說(shuō)到這里了，那我們就來(lái)聊聊MySQL的其他知識(shí)點(diǎn)。
聚簇索引和非聚簇索引
關(guān)于聚簇索引和非聚簇索引在[令人脫發(fā)的數(shù)據(jù)庫(kù)底層設(shè)計(jì)]這篇文章中已經(jīng)有了詳細(xì)的介紹，這里簡(jiǎn)單地說(shuō)說(shuō)
所謂聚簇索引，就是將索引和數(shù)據(jù)放到一起，找到索引也就找到了數(shù)據(jù)，我們剛才看到的B+樹(shù)索引就是一種聚簇索引，而非聚簇索引就是將數(shù)據(jù)和索引分開(kāi)，查找時(shí)需要先查找到索引，然后通過(guò)索引回表找到相應(yīng)的數(shù)據(jù)。InnoDB有且只有一個(gè)聚簇索引，而MyISAM中都是非聚簇索引。
聯(lián)合索引的最左前綴匹配原則
在MySQL數(shù)據(jù)庫(kù)中不僅可以對(duì)某一列建立索引，還可以對(duì)多列建立一個(gè)聯(lián)合索引，而聯(lián)合索引存在一個(gè)最左前綴匹配原則的概念，如果基于B+樹(shù)來(lái)理解這個(gè)最左前綴匹配原則，相對(duì)來(lái)說(shuō)就會(huì)容易很很多了。
首先我們基于文首的這張表建立一個(gè)聯(lián)合索引：
createindexidx_objonuser(ageasc,heightasc,weightasc)
我們已經(jīng)了解了索引的數(shù)據(jù)結(jié)構(gòu)是一顆B+樹(shù)，也了解了B+樹(shù)優(yōu)化查詢(xún)效率的其中一個(gè)因素就是對(duì)數(shù)據(jù)進(jìn)行了排序，那么我們?cè)趧?chuàng)建idx_obj這個(gè)索引的時(shí)候，也就相當(dāng)于創(chuàng)建了一顆B+樹(shù)索引，而這個(gè)索引就是依據(jù)聯(lián)合索引的成員來(lái)進(jìn)行排序，這里是age,height,weight。
看過(guò)我之前那篇博客的同學(xué)知道，InnoDB中只要有主鍵被定義，那么主鍵列被作為一個(gè)聚簇索引，而其它索引都將被作為非聚簇索引，所以自然而然的，這個(gè)索引就會(huì)是一個(gè)非聚簇索引。
所以根據(jù)這些我們可以得出結(jié)論：
- idx_obj這個(gè)索引會(huì)根據(jù)age,height,weight進(jìn)行排序
- idx_obj這個(gè)索引是一個(gè)非聚簇索引，查詢(xún)時(shí)需要回表
根據(jù)這兩個(gè)結(jié)論，首先需要了解的就是，如何排序？
單列排序很簡(jiǎn)單，比大小嘛，誰(shuí)都會(huì)，但是多列排序是基于什么原則的呢（重點(diǎn)）？
實(shí)際上在MySQL中，聯(lián)合索引的排序有這么一個(gè)原則，從左往右依次比較大小，就拿剛才建立的索引舉例子，他會(huì)先去比較age的大小，如果age的大小相同，那么比較height的大小，如果height也無(wú)法比較大小， 那么就比較weight的大小，最終對(duì)這個(gè)索引進(jìn)行排序。
那么根據(jù)這個(gè)排序我們也可以畫(huà)出一個(gè)B+樹(shù)，這里就不像上文畫(huà)的那么詳細(xì)了，簡(jiǎn)化一下：
數(shù)據(jù)：
B+樹(shù)：
注意：此時(shí)由于是非聚簇索引，所以葉子節(jié)點(diǎn)不在有數(shù)據(jù)，而是存了一個(gè)主鍵索引，最終會(huì)通過(guò)主鍵索引來(lái)回表查詢(xún)數(shù)據(jù)。
B+樹(shù)的結(jié)構(gòu)有了，就可以通過(guò)這個(gè)來(lái)理解最左前綴匹配原則了。
我們先寫(xiě)一個(gè)查詢(xún)語(yǔ)句
SELECT*FROMuserWHEREage=1andheight=2andweight=7
毋庸置疑，這條語(yǔ)句一定會(huì)走idx_obj這個(gè)索引。
那么我們?cè)倏匆粋€(gè)語(yǔ)句：
SELECT*FROMuserWHEREheight=2andweight=7
思考一下，這條SQL會(huì)走索引嗎？
答案是否定的，那么我們分析的方向就是，為什么這條語(yǔ)句不會(huì)走索引。
上文中我們提到了一個(gè)多列的排序原則，是從左到右進(jìn)行比較然后排序的，而我們的idx_obj這個(gè)索引從左到右依次是age,height,weight，所以當(dāng)我們使用height和weight來(lái)作為查詢(xún)條件時(shí)，由于age的缺失，那么就無(wú)法從age來(lái)進(jìn)行比較了。
看到這里可能有小伙伴會(huì)有疑問(wèn)，那如果直接用height和weight來(lái)進(jìn)行比較不可以嗎？
顯然是不可以的，可以舉個(gè)例子，我們把缺失的這一列寫(xiě)作一個(gè)問(wèn)號(hào)，那么這條語(yǔ)句的查詢(xún)條件就變成了?27，那么我們從這課B+樹(shù)的根節(jié)點(diǎn)開(kāi)始，根節(jié)點(diǎn)上有127和365，那么以height和weight來(lái)進(jìn)行比較的話(huà)，走的一定是127這一邊
但是如果缺失的列數(shù)字是大于3的呢？比如427，527，627，那么如果走索引來(lái)查詢(xún)數(shù)據(jù)，將會(huì)丟失數(shù)據(jù)，錯(cuò)誤查詢(xún)。所以這種情況下是絕對(duì)不會(huì)走索引進(jìn)行查詢(xún)的。這就是最左前綴匹配原則的成因。
- 最左前綴匹配原則，MySQL會(huì)一直向右匹配直到遇到范圍查詢(xún)（>、<、between、like）就停止匹配，比如 a="3" and="" b="4" c="">5 and d=6,如果建立(a,b,c,d)順序的索引，d是無(wú)法使用索引的，如果建立(a,b,d,c)的索引則都可以使用到，a、b、d的順序可以任意調(diào)整。
- =和in可以亂序，比如 a=1 and b=2 and c=3 建立(a,b,c)索引可以任意順序，MySQL的查詢(xún)優(yōu)化器會(huì)幫你優(yōu)化成索引可以識(shí)別的形式。
根據(jù)我們了解的可以得出結(jié)論：
只要無(wú)法進(jìn)行排序比較大小的，就無(wú)法走聯(lián)合索引。
可以再看幾個(gè)語(yǔ)句：
SELECT*FROMuserWHEREage=1andheight=2
這條語(yǔ)句是可以走idx_obj索引的，因?yàn)樗梢酝ㄟ^(guò)比較 (12?<365)。
SELECT*FROMuserWHEREage=1andweight=7
這條語(yǔ)句也是可以走ind_obj索引的，因?yàn)樗部梢酝ㄟ^(guò)比較(1?7<365)，走左子樹(shù)，但是實(shí)際上weight并沒(méi)有用到索引
因?yàn)楦鶕?jù)最左匹配原則，如果有兩頁(yè)的age都等于1，那么會(huì)去比較height，但是height在這里并不作為查詢(xún)條件，所以MySQL會(huì)將這兩頁(yè)全都加載到內(nèi)存中進(jìn)行最后的weight字段的比較，進(jìn)行掃描查詢(xún)。
SELECT*FROMuserwhereage>1
這條語(yǔ)句不會(huì)走索引，但是可以走索引。這句話(huà)是什么意思呢？
這條SQL很特殊，由于其存在可以比較的索引，所以它走索引也可以查詢(xún)出結(jié)果，但是由于這種情況是范圍查詢(xún)并且是全字段查詢(xún)，如果走索引，還需要進(jìn)行回表，MySQL查詢(xún)優(yōu)化器就會(huì)認(rèn)為走索引的效率比全表掃描還要低，所以MySQL會(huì)去優(yōu)化它，讓他直接進(jìn)行全表掃描。
SELECT*FROMuserWEHREage=1andheight>2andweight=7
這條語(yǔ)句是可以走索引的，因?yàn)樗梢酝ㄟ^(guò)age進(jìn)行比較，但是weight不會(huì)用到索引，因?yàn)閔eight是范圍查找，與第二條語(yǔ)句類(lèi)似，如果有兩頁(yè)的height都大于2，那么MySQL會(huì)將兩頁(yè)的數(shù)據(jù)都加載進(jìn)內(nèi)存，然后再來(lái)通過(guò)weight匹配正確的數(shù)據(jù)。
為什么InnoDB只有一個(gè)聚簇索引，而不將所有索引都使用聚簇索引？
因?yàn)榫鄞厮饕菍⑺饕蛿?shù)據(jù)都存放在葉子節(jié)點(diǎn)中，如果所有的索引都用聚簇索引，則每一個(gè)索引都將保存一份數(shù)據(jù)，會(huì)造成數(shù)據(jù)的冗余，在數(shù)據(jù)量很大的情況下，這種數(shù)據(jù)冗余是很消耗資源的。
補(bǔ)充兩個(gè)關(guān)于索引的點(diǎn)
這兩個(gè)點(diǎn)也是上次寫(xiě)關(guān)于索引的博客時(shí)漏下的，這里補(bǔ)上。
1.什么情況下會(huì)發(fā)生明明創(chuàng)建了索引，但是執(zhí)行的時(shí)候并沒(méi)有通過(guò)索引呢？
科普時(shí)間：查詢(xún)優(yōu)化器 一條SQL語(yǔ)句的查詢(xún)，可以有不同的執(zhí)行方案，至于最終選擇哪種方案，需要通過(guò)優(yōu)化器進(jìn)行選擇，選擇執(zhí)行成本最低的方案。
在一條單表查詢(xún)語(yǔ)句真正執(zhí)行之前，MySQL的查詢(xún)優(yōu)化器會(huì)找出執(zhí)行該語(yǔ)句所有可能使用的方案，對(duì)比之后找出成本最低的方案。這個(gè)成本最低的方案就是所謂的執(zhí)行計(jì)劃。
優(yōu)化過(guò)程大致如下：
1、根據(jù)搜索條件，找出所有可能使用的索引
2、計(jì)算全表掃描的代價(jià)
3、計(jì)算使用不同索引執(zhí)行查詢(xún)的代價(jià)
4、對(duì)比各種執(zhí)行方案的代價(jià)，找出成本最低的那一個(gè) 。
根據(jù)我們剛才的那張表的非聚簇索引，這條語(yǔ)句就是由于查詢(xún)優(yōu)化器的作用，造成沒(méi)有走索引：
SELECT*FROMuserwhereage>1
2.在稀疏索引情況下通常需要通過(guò)葉子節(jié)點(diǎn)的指針回表查詢(xún)數(shù)據(jù)，什么情況下不需要回表？
科普時(shí)間：覆蓋索引 覆蓋索引（covering index）指一個(gè)查詢(xún)語(yǔ)句的執(zhí)行只用從索引中就能夠取得，不必從數(shù)據(jù)表中讀取。也可以稱(chēng)之為實(shí)現(xiàn)了索引覆蓋。
當(dāng)一條查詢(xún)語(yǔ)句符合覆蓋索引條件時(shí)，MySQL只需要通過(guò)索引就可以返回查詢(xún)所需要的數(shù)據(jù)，這樣避免了查到索引后再返回表操作，減少I(mǎi)/O提高效率。
如，表covering_index_sample中有一個(gè)普通索引 idx_key1_key2(key1,key2)。當(dāng)我們通過(guò)SQL語(yǔ)句：select key2 from covering_index_sample where key1 = 'keytest';的時(shí)候，就可以通過(guò)覆蓋索引查詢(xún)，無(wú)需回表。
例如:
SELECTageFROMuserwhereage=1
這句話(huà)就不需要進(jìn)行回表查詢(xún)。
結(jié)語(yǔ)
本篇文章著重聊了一下關(guān)于MySQL的索引結(jié)構(gòu)，從零開(kāi)始慢慢構(gòu)建了一個(gè)B+樹(shù)索引，并且根據(jù)這個(gè)過(guò)程談了B+樹(shù)是如何一步一步去優(yōu)化查詢(xún)效率的。
簡(jiǎn)單地歸納一下就是：
排序：優(yōu)化查詢(xún)的根本，插入時(shí)進(jìn)行排序?qū)嶋H上就是為了優(yōu)化查詢(xún)的效率。
頁(yè)：用于減少I(mǎi)O次數(shù)，還可以利用程序局部性原理，來(lái)稍微提高查詢(xún)效率。
頁(yè)目錄：用于規(guī)避鏈表的軟肋，避免在查詢(xún)時(shí)進(jìn)行鏈表的掃描。
多頁(yè)：數(shù)據(jù)量增加的情況下開(kāi)辟新頁(yè)來(lái)保存數(shù)據(jù)。
目錄頁(yè)：“特殊的頁(yè)目錄”，其中保存的數(shù)據(jù)是頁(yè)的地址。查詢(xún)時(shí)可以通過(guò)目錄頁(yè)快速定位到頁(yè)，避免多頁(yè)的掃描。
