索引可以說(shuō)是每個(gè)工程師的必備技能點(diǎn)，明白索引的原理對(duì)于寫出高質(zhì)量的 SQL 至關(guān)重要，今天我們就從 0 到 1 來(lái)理解下索引的原理，相信大家看完不光對(duì)索引還會(huì)對(duì) MySQL 中 InnoDB 存儲(chǔ)引擎的最小存儲(chǔ)單位「頁(yè)」會(huì)有更深刻的認(rèn)識(shí)

從實(shí)際需求出發(fā)

假設(shè)有如下用戶表:

CREATETABLE`user`(
`id`int(11)unsignedNOTNULLAUTO_INCREMENT,
`name`int(11)DEFAULTNULLCOMMENT'姓名',
`age`tinyint(3)unsignedDEFAULTNULLCOMMENT'年齡',
`height`int(11)DEFAULTNULLCOMMENT'身高',
PRIMARYKEY(`id`)
)ENGINE=InnoDBDEFAULTCHARSET=utf8COMMENT='用戶表';

可以看到存儲(chǔ)引擎使用的是 InnoDB，我們先來(lái)看針對(duì)此表而言工作中比較常用的 SQL 語(yǔ)句都有哪此，畢竟技術(shù)是要為業(yè)務(wù)需求服務(wù)的，

1.select*fromuserwhereid=xxx
2.select*fromuserorderbyidasc/desc
3.select*fromuserwhereage=xxx
4.selectagefromuserwhereage=xxx
5.selectagefromuserorderbyageasc/desc

既然要查詢那我們首先插入一些數(shù)據(jù)吧，畢竟沒(méi)有數(shù)據(jù)何來(lái)查詢

insertintouser('name','age','height')values('張三',20,170);
insertintouser('name','age','height')values('李四',21,171);
insertintouser('name','age','height')values('王五',22,172);
insertintouser('name','age','height')values('趙六',23,173);
insertintouser('name','age','height')values('錢七',24,174);

插入后表中的數(shù)據(jù)如下：

不知你有沒(méi)發(fā)現(xiàn)我們?cè)诓迦氲臅r(shí)候并沒(méi)有指定 id 值，但 InnoDB 為每條記錄默認(rèn)添加了一個(gè) id 值，而且這個(gè) id 值是遞增的，每插入一條記錄，id 遞增 1，id 為什么要遞增呢，主要是為了查詢方便，每條記錄按 id 由小到大的順序用鏈表連接起來(lái)，這樣每次查找 id = xxx 的值就從 id = 1 開始依次往后查找即可

現(xiàn)在假設(shè)我們要執(zhí)行以下 SQL 語(yǔ)句，MySQL 會(huì)怎么查詢呢

select*fromuserwhereid=3

頁(yè)

如前所述，首先從 id 最小的記錄也就是 id = 1 讀起，每次讀一條記錄，將其 id 值與要查詢的值比較，連續(xù)讀三次記錄于是找到了記錄 3，注意這個(gè)讀的操作，是首先需要把存儲(chǔ)在磁盤的記錄讀取到內(nèi)存然后再比較 id 的，從磁盤讀到內(nèi)存算一次 IO，也就是說(shuō)此過(guò)程中產(chǎn)生了三次 IO，如果只是幾條記錄還好，但如果要比較的條數(shù)多的話對(duì)性能是非常嚴(yán)重的挑戰(zhàn)，如果我要查詢?yōu)?id = 100 的記錄那豈不是要產(chǎn)生 100 次 IO？既然瓶頸在 IO，那該怎么改進(jìn)呢，很簡(jiǎn)單，我們現(xiàn)在的設(shè)計(jì)一次 IO 只能讀一條記錄，那改為一次 IO 能讀取 100 條甚至更多不就只產(chǎn)生一次 IO 了嗎，這背后的思想就是程序局部性原理：當(dāng)用到了某項(xiàng)數(shù)據(jù)時(shí)，很可能會(huì)用到與之相鄰的數(shù)據(jù)，所以干脆把相依的數(shù)據(jù)一起加載進(jìn)去（你從 id = 1 開始讀，那很可能用到 id = 1 緊隨其后的元素，于是干脆把 id = 1 ~ id = 100 的記錄都加載進(jìn)去）

當(dāng)然一次 IO 的讀取記錄也并不是多多益善，總不能為了一條查詢記錄而把很多無(wú)關(guān)的數(shù)據(jù)都加載到內(nèi)存吧，那會(huì)造成資源的極大浪費(fèi)，于是我們采用了一個(gè)比較折中的方案，我們規(guī)定一次 IO 讀取 16 K 的數(shù)據(jù)，假設(shè)為 100 條數(shù)據(jù)好了，這樣如果我們要查詢 id = 100 的記錄，只產(chǎn)生了一次 IO 讀（id=1~id=100 的記錄），比起原來(lái)的 100 次 IO 提升了 100 倍的性能

我們把這 16KB 的記錄組合稱為一個(gè)頁(yè)

頁(yè)目錄

一次 IO 會(huì)讀取一個(gè)頁(yè)，然后再在內(nèi)存里查找頁(yè)里的記錄，在內(nèi)存里查找確實(shí)比磁盤快多了，但我們?nèi)圆粷M意，因?yàn)槿绻檎?id = 100 的記錄，要先從 id = 1 的記錄比較起，然后是id=2，…，id=100，需要比較 100 次，能否更快一點(diǎn)？

可以參照二分查找，先查找 id = (1+100)/2 = 50，由于 50 < 100，接著在 ?50~100 的記錄中查，然后再在 75~100 中查，這樣經(jīng)過(guò) 7 次就可找到 id = 100 次的記錄，比起原來(lái)的 100 次比較又提升了不少性能。但現(xiàn)在問(wèn)題來(lái)了，第一次要找到 id = ?50 的記錄又得從 id = 1 開始遍歷 50 次才能找到，能否一下就定位到 id=50 的記錄呢，如果不能，哪怕第一次從 id = 30 或 40 開始查找也行啊

有什么數(shù)據(jù)結(jié)構(gòu)能滿足這種需求呢，還記得跳表不，每隔 n 個(gè)元素抽出一個(gè)組成一級(jí)索引，每隔 2*n 個(gè)元素組成二級(jí)索引。。。

如圖示，以建立一級(jí)索引為例，我們?cè)诓檎业臅r(shí)候先在一級(jí)索引查找，在一級(jí)索引里定位到了再到鏈表里查找，比如我們要找 7 這個(gè)數(shù)字，如果不用跳表直接在鏈表里查，需要比較 7 次，而如果用了跳表我們先在一級(jí)索引查找，發(fā)現(xiàn)只要比較 3 次，減少了四次，所以我們可以利用跳表的思想來(lái)減少查詢次數(shù)，具體操作如下，每 4 個(gè)元素為一組組成一個(gè)槽（slot），槽只記錄本組元素最大的那條記錄以及記錄本組有幾條記錄

現(xiàn)在假設(shè)我們想要定位 id = 9 的那條記錄，該怎么做呢，很簡(jiǎn)單：首先定位記錄在哪個(gè)槽，然后遍歷此槽中的元素

定位在哪個(gè)槽，首先取最小槽和最大槽對(duì)應(yīng)的 id（分別為 4， 12），先通過(guò)二分查找取它們的中間值為 (4+12)/2 = 8，8 小于 9，且槽 2 的最大 id 為 12，所以可知 id = 9 的記錄在槽 2 里

遍歷槽 2 中的元素，現(xiàn)在問(wèn)題來(lái)了，我們知道每條記錄都構(gòu)成了一個(gè)單鏈表，而每個(gè)槽指向的是此分組中的最大 id 值，該怎么從此槽的第一個(gè)元素開始遍歷呢，很簡(jiǎn)單，從槽 1 開始遍歷不就行了，因?yàn)樗赶蛟氐南乱粋€(gè)元素即為槽 2 的起始元素，遍歷后發(fā)現(xiàn)槽 2 的 第一個(gè)元素即為我們找到的 id 為 9 的元素

可以看到通過(guò)這種方式在頁(yè)內(nèi)很快把我們的元素定位出來(lái)了，MySQL 規(guī)定每個(gè)槽中的元素在 1~8 條，所以只要定位了在哪個(gè)槽，剩下的比較就不是什么問(wèn)題了，當(dāng)然一個(gè)頁(yè)裝的記錄終究是有限的，如果頁(yè)滿了，就要要開辟另外的頁(yè)來(lái)裝記錄了，頁(yè)與頁(yè)之間通過(guò)鏈表連接起來(lái)，但注意看下圖，為啥要用雙向鏈表連接起來(lái)呢，別忘了最開頭我們列出的 「order by id asc 」和「order by id desc 」這兩個(gè)查詢條件，也就是說(shuō)記錄需要同時(shí)支持正序與逆序查找，這就是為什么要使用雙向鏈表的原因

B+ 樹的誕生

現(xiàn)在問(wèn)題來(lái)了，如果有很多頁(yè)，該怎么定位元素呢，如果元素剛好在前幾個(gè)頁(yè)還好，大不了遍歷前幾個(gè)頁(yè)也很快，但如果要查 id = 100w 這樣的元素一頁(yè)頁(yè)遍歷的話就要遍歷 1w 頁(yè)（假設(shè)每頁(yè) 100 條記錄），那顯然是不可接受的，如何改進(jìn)呢，其實(shí)之前建的頁(yè)內(nèi)目錄已經(jīng)給了我們啟發(fā)，既然在頁(yè)內(nèi)我們可以通過(guò)為記錄建頁(yè)目錄的形式來(lái)先定位元素在哪個(gè)槽然后再找，那針對(duì)多頁(yè)，能否先定位元素在哪個(gè)頁(yè)呢，也就是說(shuō)我們可以為頁(yè)也建立一個(gè)目錄，這個(gè)目錄里的每一條記錄都對(duì)應(yīng)著頁(yè)及頁(yè)中的最小記錄，當(dāng)然這個(gè)目錄也是以頁(yè)的形式存在的，為了便于區(qū)分 ，我們把針對(duì)頁(yè)生成的目錄對(duì)應(yīng)的頁(yè)稱為目錄頁(yè)，而之前存儲(chǔ)完整記錄的頁(yè)稱為數(shù)據(jù)頁(yè)

畫外音：目錄頁(yè)與數(shù)據(jù)頁(yè)一樣，內(nèi)部也是有槽的，上文為了方便展示，沒(méi)有畫出，目錄頁(yè)和數(shù)據(jù)除了記錄數(shù)據(jù)不一樣，其他結(jié)構(gòu)都是一致的

現(xiàn)在如果要查找 id = xxx 的記錄就很簡(jiǎn)單了，只要先到目錄頁(yè)中定位它的起始頁(yè)然后再依次查找即可，由于不管是目錄頁(yè)還是數(shù)據(jù)頁(yè)里面都有槽，所以無(wú)論是定位目錄頁(yè)的頁(yè)碼還是定位數(shù)據(jù)頁(yè)中的記錄都是非常快的。

當(dāng)然了，隨著頁(yè)的增多，目錄頁(yè)存放的記錄也越來(lái)越多，目錄頁(yè)也終歸會(huì)滿的，那就再建一個(gè)目錄頁(yè)吧，于是現(xiàn)在問(wèn)題來(lái)了，怎么定位要找的 id 是在哪個(gè)目錄頁(yè)呢，再次制定針對(duì)目錄頁(yè)的目錄頁(yè)不就行了，如下

看到上面這個(gè)結(jié)構(gòu)你想到了什么？沒(méi)錯(cuò)，這就是一顆 B+ 樹！到此相信你已經(jīng)明白了 B+ 樹的演進(jìn)之路，也明白了它的原理，可以看到這顆 B+ 樹有三層，我們把最頂層的目錄頁(yè)稱為根節(jié)點(diǎn)，最下層的存儲(chǔ)完整記錄的頁(yè)稱為葉子節(jié)點(diǎn)，

現(xiàn)在我們?cè)賮?lái)看一下如何查找 id = 55 的記錄，首先會(huì)加載根節(jié)點(diǎn)，發(fā)現(xiàn)應(yīng)該在頁(yè)碼 30 的頁(yè)中去找，于是加載頁(yè) 30，在頁(yè) 30 中又發(fā)現(xiàn)應(yīng)該在頁(yè) 4 中查中，于是再次把頁(yè) 4 加載進(jìn)內(nèi)存中，然后在頁(yè) 4 中依次遍歷查找，可以看到總共經(jīng)歷了 3 次 IO（B+樹有幾層就會(huì)有幾次 IO），頁(yè)讀取之后會(huì)緩存在內(nèi)存中，再讀的話如果命中內(nèi)存中的頁(yè)就會(huì)直接從內(nèi)存中獲取。有人可能會(huì)問(wèn)，如果 B+ 樹層數(shù)很多，那豈不是可能會(huì)有很多次 IO，我們簡(jiǎn)單的算一下，假設(shè)數(shù)據(jù)頁(yè)可以存儲(chǔ) 100 條記錄，目錄頁(yè)可以存儲(chǔ) 1000 條記錄（目錄頁(yè)由于只存儲(chǔ)了主鍵，不存儲(chǔ)完整的數(shù)據(jù)，所以可以存儲(chǔ)更多的記錄），那么

如果B+樹只有 1 層，也就是只有 1 個(gè)用于存放用戶記錄的節(jié)點(diǎn)，最多能存放100條記錄。

如果B+樹有 2 層，最多能存放1000×100=100000條記錄。

如果B+樹有 3 層，最多能存放1000×1000×100=100000000條記錄。

如果B+樹有 4 層，最多能存放1000×1000×1000×100=100000000000條記錄！

所以一般3~4 層的 B+ 樹足以滿足我們的要求，而且每次讀取后會(huì)緩存在內(nèi)存中（當(dāng)然也會(huì)根據(jù)一定的算法被換出內(nèi)存），所以整體來(lái)看 3~4 層 B+ 樹足以滿足我們需求

聚簇索引與非聚簇索引

相信你已經(jīng)發(fā)現(xiàn)了，上文中我們舉的 B+ 樹的例子針對(duì)的是 id 也就是主鍵的索引，不難發(fā)現(xiàn)主鍵索引中的葉子結(jié)點(diǎn)存儲(chǔ)了完整的 SQL 記錄，我們把這種存儲(chǔ)了完整記錄的索引稱為聚簇索引，只要你定義了主鍵，那么主鍵索引就是聚簇索引。

那么如果是非主鍵的列創(chuàng)建的索引又是怎樣的形式呢，非葉子節(jié)點(diǎn)的形式完全一樣，但葉子節(jié)點(diǎn)的存儲(chǔ)則有些不同，非主鍵列索引葉子節(jié)點(diǎn)上存儲(chǔ)的是索引列及主鍵值，比如我們假設(shè)對(duì) age 這個(gè)列建立了索引，那么它的索引樹如下

可以看到非葉子節(jié)點(diǎn)保存的是「age 值 + 頁(yè)碼」，而葉子節(jié)點(diǎn)保存的是 「age 值+主鍵值」,那么你可能就會(huì)疑惑了，如下 SQL 是怎么取出完整記錄的呢

select*fromuserwhereage=xxx

第一步大家都知道，上述 SQL 可以命中 age 列對(duì)應(yīng)的索引，然后找到葉子節(jié)點(diǎn)上對(duì)應(yīng)的記錄（如果有的話），但葉子節(jié)點(diǎn)上的記錄只有 age 和 id 這兩列，而你用的是 select *，意味著要查找 user 的所有列信息，該怎么辦呢，答案是根據(jù)拿到的 id 再到聚簇索引找 id 對(duì)應(yīng)的完整記錄，這就是我們所說(shuō)的回表，如果回表多的話顯然會(huì)造成一定的性能問(wèn)題，因?yàn)?id 可能分布在不同的頁(yè)中，這意味著要將不同的頁(yè)從磁盤讀入內(nèi)存，這些頁(yè)很可能不是相鄰的，也就意味著會(huì)造成大量的隨機(jī) IO，會(huì)嚴(yán)重地影響性能，看到這相信大家不難明白一道高頻面試題：為什么設(shè)置了命中了索引但還是造成了全表掃描，其中一個(gè)原因就是雖然命中了索引但在葉子節(jié)點(diǎn)查詢到記錄后還要大量的回表，導(dǎo)致優(yōu)化器認(rèn)為這種情況還不如全表掃描會(huì)更快些

有人可能會(huì)問(wèn)，為啥都二級(jí)索引不存儲(chǔ)完整的記錄呢，當(dāng)然是為了節(jié)省空間，畢竟完整的數(shù)據(jù)是很耗空間的，如果每加一個(gè)索引都要額外存儲(chǔ)完整的記錄，那會(huì)造成很多數(shù)據(jù)冗余。

怎么避免這種情況呢？索引覆蓋，如果如下 SQL 滿足你的需求，那么就建議采用如下形式

selectagefromuserwhereage=xxx
selectage,idfromuserwhereage=xxx

不難發(fā)現(xiàn)這種 SQL 的特點(diǎn)是要獲取的列（age）就是索引列本身（包括 id），這樣在根據(jù) age 的索引查到葉子節(jié)上對(duì)應(yīng)的記錄后，由于記錄本身就包含了這些列，就不需要回表了，能提升性能

磁盤預(yù)讀

接下來(lái)我們討論一個(gè)網(wǎng)上很多人搞不拎清的一個(gè)問(wèn)題，我們知道操作系統(tǒng)是以頁(yè)為單位來(lái)管理內(nèi)存的，在 Linux 中，一頁(yè)的大小默認(rèn)為 4 KB，也就是說(shuō)無(wú)論是從磁盤載入數(shù)據(jù)到內(nèi)存還是將內(nèi)存寫回磁盤，操作系統(tǒng)都會(huì)以頁(yè)為單位進(jìn)行操作，哪怕你只對(duì)一個(gè)空文件只寫入了一個(gè)字節(jié)，操作系統(tǒng)也會(huì)為其分配一個(gè)頁(yè)的大?。?4 KB）

如圖示，向磁盤寫入了兩個(gè) byte ，但操作系統(tǒng)依然為其分配了一個(gè)頁(yè)（4 KB）的大小

innoDB 也是以頁(yè)為單位來(lái)存儲(chǔ)與讀取的，而 innoDB 頁(yè)的默認(rèn)大小為 16 KB，那么網(wǎng)上很多人的疑問(wèn)是這是否意味著它需要執(zhí)行 4 次 IO 才能把 innoDB 的頁(yè)讀完呢?不是的，只需要一次 IO，為什么？這需要理解一點(diǎn)磁盤讀取數(shù)據(jù)的工作原理

磁盤的構(gòu)造

首先我們來(lái)看看磁盤的物理結(jié)構(gòu)

硬盤內(nèi)部主要部件為磁盤盤片、傳動(dòng)磁臂、讀寫磁頭和轉(zhuǎn)軸，數(shù)據(jù)主要寫入磁盤的盤片上的，盤片又是由若干個(gè)扇區(qū)構(gòu)成的，數(shù)據(jù)寫入讀取都是以扇區(qū)為基本單位的，另外以盤片中心為圓心，把盤片分成若干個(gè)同心圓，那每一個(gè)劃分圓的“線條”，就稱為磁道

那么數(shù)據(jù)是如何讀取與寫入的呢，主要有三步

尋道：既然數(shù)據(jù)是保存在扇區(qū)上的，那我首先我們需要知道它到底是在哪個(gè)扇區(qū)上吧，這就需要先讓磁頭移動(dòng)到扇區(qū)所在的磁道上，我們把它稱為尋道時(shí)間，平均尋道時(shí)間一般在3-15ms

旋轉(zhuǎn)延遲: 磁盤移動(dòng)到扇區(qū)所在的磁盤上時(shí)，此時(shí)的磁頭對(duì)準(zhǔn)的還不一定我們想要的數(shù)據(jù)對(duì)應(yīng)的扇區(qū)，所以需要等待盤片旋轉(zhuǎn)片刻，等到我們想要的數(shù)據(jù)對(duì)應(yīng)的扇區(qū)落到磁頭下，旋轉(zhuǎn)延遲取決于磁盤轉(zhuǎn)速，通常用磁盤旋轉(zhuǎn)一周所需時(shí)間的1/2表示。比如：7200rpm的磁盤平均旋轉(zhuǎn)延遲大約為60*1000/7200/2 = 4.17ms，而轉(zhuǎn)速為15000rpm的磁盤其平均旋轉(zhuǎn)延遲為2ms

數(shù)據(jù)傳輸:經(jīng)過(guò)前面的兩步，磁頭終于開始讀寫數(shù)據(jù)了，目前IDE/ATA能達(dá)到133MB/s，SATA II可達(dá)到300MB/s的接口數(shù)據(jù)傳輸率，數(shù)據(jù)傳輸時(shí)間通常遠(yuǎn)小于前兩部分消耗時(shí)間?？珊雎圆挥?jì)

注意數(shù)據(jù)傳輸中的忽略不計(jì)是有前提的，即是需要讀取連續(xù)相鄰的扇區(qū)，也就是我們常說(shuō)的順序 IO，磁盤順序 IO 的讀寫速度可以媲美甚至超越內(nèi)存的隨機(jī) IO，所以這部分時(shí)間可以忽略不計(jì)，（大家熟知的 Kafka 之所以性能強(qiáng)悍，有一個(gè)重要原因就是利用了磁盤的順序讀寫），但如果要讀取的數(shù)據(jù)是分布在不同的扇區(qū)的話，也就變成了隨機(jī) IO，隨機(jī) IO 毫無(wú)疑問(wèn)增大了尋道時(shí)間和旋轉(zhuǎn)延遲，性能是非常堪憂的（典型代表就是上文提到的 回表時(shí)大量 id 分布在不同的頁(yè)上，造成了大量的隨機(jī) IO）

如圖示：圖片來(lái)自著名學(xué)術(shù)期刊 ACM Queue 上的性能對(duì)比圖，可以看到磁盤順序 IO（Sequential Disk）的速度比內(nèi)存隨機(jī)讀寫（Random memory）還快

那讀取 innoDB 中的一個(gè)頁(yè)為啥算一次 IO 呢，相信你已經(jīng)猜到了，因?yàn)檫@一個(gè)頁(yè)是連續(xù)分配的，也即意味著它們的扇區(qū)是相鄰的，所以它是順序 IO

操作系統(tǒng)是以頁(yè)為單位來(lái)管理內(nèi)存的，它可以一次加載整數(shù)倍的頁(yè)，而 innoDB 的頁(yè)大小為 16KB，剛好是操作系統(tǒng)頁(yè)（4KB）的 4 倍，所以可以指定在讀取的起始地址連續(xù)讀取 4 個(gè)操作系統(tǒng)頁(yè)，即 16 KB，這就是我們說(shuō)的磁盤預(yù)讀，至此相信大家不難明白為啥說(shuō)讀取一頁(yè)其實(shí)只是一次 IO 而不是 4 次了

總結(jié)

看完本文相信大家能明白索引的由來(lái)了，此外對(duì)頁(yè)以及磁盤預(yù)讀對(duì)性能的提升應(yīng)該也有不少了解，其實(shí) MySQL 的頁(yè)結(jié)構(gòu)與我們推演的結(jié)構(gòu)有些許出入，不過(guò)不影響整體的理解。