你管這破玩意叫?B ?樹?

大家好，我是小林。
之前分享過「索引為什么能提高查詢性能」這篇文章，這次帶大家從 0 到 1 來理解下索引的原理，相信大家看完不光對索引，還會對 MySQL 中 InnoDB 存儲引擎的最小存儲單位「頁」會有更深刻的認(rèn)識。6000 字的車，大家坐穩(wěn)了！

從實際需求出發(fā)

假設(shè)有如下用戶表:CREATE?TABLE?`user`?(
??`id`?int(11)?unsigned?NOT?NULL?AUTO_INCREMENT,
??`name`?int(11)?DEFAULT?NULL?COMMENT?'姓名',
??`age`?tinyint(3)?unsigned?DEFAULT?NULL?COMMENT?'年齡',
??`height`?int(11)?DEFAULT?NULL?COMMENT?'身高',
??PRIMARY?KEY?(`id`)
)?ENGINE=InnoDB?DEFAULT?CHARSET=utf8?COMMENT='用戶表';
可以看到存儲引擎使用的是 InnoDB，我們先來看針對此表而言工作中比較常用的 SQL 語句都有哪此，畢竟技術(shù)是要為業(yè)務(wù)需求服務(wù)的，1.?select?*?from?user?where?id?=?xxx
2.?select?*?from?user?order?by?id?asc/desc
3.?select?*?from?user?where?age?=?xxx
4.?select?age?from?user?where?age?=?xxx
5.?select?age?from?user?order?by?age?asc/desc
既然要查詢那我們首先插入一些數(shù)據(jù)吧，畢竟沒有數(shù)據(jù)何來查詢insert?into?user?('name',?'age',?'height')?values?('張三',?20,?170);
insert?into?user?('name',?'age',?'height')?values?('李四',?21,?171);
insert?into?user?('name',?'age',?'height')?values?('王五',?22,?172);
insert?into?user?('name',?'age',?'height')?values?('趙六',?23,?173);
insert?into?user?('name',?'age',?'height')?values?('錢七',?24,?174);
插入后表中的數(shù)據(jù)如下：

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

現(xiàn)在假設(shè)我們要執(zhí)行以下 SQL 語句，MySQL 會怎么查詢呢select?*?from?user?where?id?=?3

頁

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

我們把這 16KB 的記錄組合稱為一個頁

頁目錄

一次 IO 會讀取一個頁，然后再在內(nèi)存里查找頁里的記錄，在內(nèi)存里查找確實比磁盤快多了，但我們?nèi)圆粷M意，因為如果要查找 id = 100 的記錄，要先從 ?id = 1 的記錄比較起，然后是id=2，…，id=100，需要比較 100 次，能否更快一點？可以參照二分查找，先查找 id = (1 100)/2 ?= 50，由于 50 < 100，接著在 ?50~100 的記錄中查，然后再在 75~100 中查，這樣經(jīng)過 7 次就可找到 id = 100 次的記錄，比起原來的 100 次比較又提升了不少性能。但現(xiàn)在問題來了，第一次要找到 id = ?50 的記錄又得從 id = 1 開始遍歷 50 次才能找到，能否一下就定位到 id=50 的記錄呢，如果不能，哪怕第一次從 id = 30 或 40 開始查找也行啊有什么數(shù)據(jù)結(jié)構(gòu)能滿足這種需求呢，還記得跳表不，每隔 n 個元素抽出一個組成一級索引，每隔 2*n 個元素組成二級索引。。。

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

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

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

2. 遍歷槽 2 中的元素，現(xiàn)在問題來了，我們知道每條記錄都構(gòu)成了一個單鏈表，而每個槽指向的是此分組中的最大 id 值，該怎么從此槽的第一個元素開始遍歷呢，很簡單，從槽 1 開始遍歷不就行了，因為它指向元素的下一個元素即為槽 2 的起始元素，遍歷后發(fā)現(xiàn)槽 2 的 第一個元素即為我們找到的 id 為 9 的元素

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

B 樹的誕生

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

畫外音：目錄頁與數(shù)據(jù)頁一樣，內(nèi)部也是有槽的，上文為了方便展示，沒有畫出，目錄頁和數(shù)據(jù)除了記錄數(shù)據(jù)不一樣，其他結(jié)構(gòu)都是一致的現(xiàn)在如果要查找 id = xxx 的記錄就很簡單了，只要先到目錄頁中定位它的起始頁然后再依次查找即可，由于不管是目錄頁還是數(shù)據(jù)頁里面都有槽，所以無論是定位目錄頁的頁碼還是定位數(shù)據(jù)頁中的記錄都是非常快的。當(dāng)然了，隨著頁的增多，目錄頁存放的記錄也越來越多，目錄頁也終歸會滿的，那就再建一個目錄頁吧，于是現(xiàn)在問題來了，怎么定位要找的 id 是在哪個目錄頁呢，再次制定針對目錄頁的目錄頁不就行了，如下：

看到上面這個結(jié)構(gòu)你想到了什么？沒錯，這就是一顆 B 樹！到此相信你已經(jīng)明白了 B 樹的演進(jìn)之路，也明白了它的原理，可以看到這顆 B 樹有三層，我們把最頂層的目錄頁稱為根節(jié)點，最下層的存儲完整記錄的頁稱為葉子節(jié)點。現(xiàn)在我們再來看一下如何查找 ?id = 55 的記錄，首先會加載根節(jié)點，發(fā)現(xiàn)應(yīng)該在頁碼 30 的頁中去找，于是加載頁 30，在頁 30 中又發(fā)現(xiàn)應(yīng)該在頁 4 中查中，于是再次把頁 4 加載進(jìn)內(nèi)存中，然后在頁 4 中依次遍歷查找，可以看到總共經(jīng)歷了 3 次 IO（B 樹有幾層就會有幾次 IO），頁讀取之后會緩存在內(nèi)存中，再讀的話如果命中內(nèi)存中的頁就會直接從內(nèi)存中獲取。有人可能會問，如果 B 樹層數(shù)很多，那豈不是可能會有很多次 IO，我們簡單的算一下，假設(shè)數(shù)據(jù)頁可以存儲 100 條記錄，目錄頁可以存儲 1000 條記錄（目錄頁由于只存儲了主鍵，不存儲完整的數(shù)據(jù)，所以可以存儲更多的記錄），那么

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

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

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

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

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

聚簇索引與非聚簇索引

相信你已經(jīng)發(fā)現(xiàn)了，上文中我們舉的 B 樹的例子針對的是 id 也就是主鍵的索引，不難發(fā)現(xiàn)主鍵索引中的葉子結(jié)點存儲了完整的 SQL 記錄，我們把這種存儲了完整記錄的索引稱為聚簇索引，只要你定義了主鍵，那么主鍵索引就是聚簇索引。那么如果是非主鍵的列創(chuàng)建的索引又是怎樣的形式呢，非葉子節(jié)點的形式完全一樣，但葉子節(jié)點的存儲則有些不同，非主鍵列索引葉子節(jié)點上存儲的是索引列及主鍵值，比如我們假設(shè)對 age 這個列建立了索引，那么它的索引樹如下

可以看到非葉子節(jié)點保存的是「age 值 頁碼」，而葉子節(jié)點保存的是 「age 值 主鍵值」,那么你可能就會疑惑了，如下 SQL 是怎么取出完整記錄的呢select?*?from?user?where?age?=?xxx
第一步大家都知道，上述 SQL 可以命中 age 列對應(yīng)的索引，然后找到葉子節(jié)點上對應(yīng)的記錄（如果有的話），但葉子節(jié)點上的記錄只有 age 和 id 這兩列，而你用的是 select *，意味著要查找 user 的所有列信息，該怎么辦呢。答案是根據(jù)拿到的 id 再到聚簇索引找 id 對應(yīng)的完整記錄，這就是我們所說的回表，如果回表多的話顯然會造成一定的性能問題，因為 id 可能分布在不同的頁中，這意味著要將不同的頁從磁盤讀入內(nèi)存，這些頁很可能不是相鄰的，也就意味著會造成大量的隨機(jī) IO，會嚴(yán)重地影響性能。看到這相信大家不難明白一道高頻面試題：為什么設(shè)置了命中了索引但還是造成了全表掃描，其中一個原因就是雖然命中了索引但在葉子節(jié)點查詢到記錄后還要大量的回表，導(dǎo)致優(yōu)化器認(rèn)為這種情況還不如全表掃描會更快些有人可能會問，為啥都二級索引不存儲完整的記錄呢，當(dāng)然是為了節(jié)省空間，畢竟完整的數(shù)據(jù)是很耗空間的，如果每加一個索引都要額外存儲完整的記錄，那會造成很多數(shù)據(jù)冗余。怎么避免這種情況呢？索引覆蓋，如果如下 SQL 滿足你的需求，那么就建議采用如下形式select?age?from?user?where?age?=?xxx
select?age,id?from?user?where?age?=?xxx
不難發(fā)現(xiàn)這種 SQL 的特點是要獲取的列（age）就是索引列本身（包括 id），這樣在根據(jù) age 的索引查到葉子節(jié)上對應(yīng)的記錄后，由于記錄本身就包含了這些列，就不需要回表了，能提升性能。磁盤預(yù)讀接下來我們討論一個網(wǎng)上很多人搞不拎清的一個問題，我們知道操作系統(tǒng)是以頁為單位來管理內(nèi)存的，在 Linux 中，一頁的大小默認(rèn)為 4 KB，也就是說無論是從磁盤載入數(shù)據(jù)到內(nèi)存還是將內(nèi)存寫回磁盤，操作系統(tǒng)都會以頁為單位進(jìn)行操作，哪怕你只對一個空文件只寫入了一個字節(jié)，操作系統(tǒng)也會為其分配一個頁的大?。?4 KB）

如圖示，向磁盤寫入了兩個 byte ，但操作系統(tǒng)依然為其分配了一個頁（4 KB）的大小innoDB 也是以頁為單位來存儲與讀取的，而 innoDB 頁的默認(rèn)大小為 16 KB，那么網(wǎng)上很多人的疑問是這是否意味著它需要執(zhí)行 4 次 IO 才能把 innoDB 的頁讀完呢?不是的，只需要一次 IO，為什么？這需要理解一點磁盤讀取數(shù)據(jù)的工作原理

磁盤的構(gòu)造

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

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

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

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

3. 數(shù)據(jù)傳輸:經(jīng)過前面的兩步，磁頭終于開始讀寫數(shù)據(jù)了，目前IDE/ATA能達(dá)到133MB/s，SATA II可達(dá)到300MB/s的接口數(shù)據(jù)傳輸率，數(shù)據(jù)傳輸時間通常遠(yuǎn)小于前兩部分消耗時間。可忽略不計

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

如圖示：圖片來自著名學(xué)術(shù)期刊 ACM Queue 上的性能對比圖，可以看到磁盤順序 IO（Sequential Disk）的速度比內(nèi)存隨機(jī)讀寫（Random memory）還快那讀取 innoDB 中的一個頁為啥算一次 IO 呢，相信你已經(jīng)猜到了，因為這一個頁是連續(xù)分配的，也即意味著它們的扇區(qū)是相鄰的，所以它是順序 IO操作系統(tǒng)是以頁為單位來管理內(nèi)存的，它可以一次加載整數(shù)倍的頁，而 innoDB 的頁大小為 16KB，剛好是操作系統(tǒng)頁（4KB）的 4 倍。所以可以指定在讀取的起始地址連續(xù)讀取 4 個操作系統(tǒng)頁，即 16 KB，這就是我們說的磁盤預(yù)讀，至此相信大家不難明白為啥說讀取一頁其實只是一次 IO 而不是 4 次了

總結(jié)

看完本文相信大家能明白索引的由來了。此外對頁以及磁盤預(yù)讀對性能的提升應(yīng)該也有不少了解，其實 MySQL 的頁結(jié)構(gòu)與我們推演的結(jié)構(gòu)有些許出入。不過不影響整體的理解，如果大家有興趣深入了解 MySQL 的頁結(jié)構(gòu)，強烈建議大家看看文末的<MySQL是怎樣運行的>這本書，講解得非常細(xì)致

• 巨人的肩膀

1. 磁盤I/O那些事: https://tech.meituan.com/2017/05/19/about-desk-io.html

2. 帶你從頭到尾捋一遍MySQL索引結(jié)構(gòu): https://blog.51cto.com/u_12302929/3290492

3. MySQL 是怎樣運行的：從根兒上理解 MySQL