「為什么 MySQL 采用 B+ 樹作為索引？」這句話，是不是在面試時經(jīng)常出現(xiàn)。

要解釋這個問題，其實不單單要從數(shù)據(jù)結(jié)構(gòu)的角度出發(fā)，還要考慮磁盤 I/O 操作次數(shù)，因為 MySQL 的數(shù)據(jù)是存儲在磁盤中的嘛。

這次，就跟大家一層一層的分析這個問題，圖中包含大量的動圖來幫助大家理解，相信看完你就拿捏這道題目了！

怎樣的索引的數(shù)據(jù)結(jié)構(gòu)是好的？
MySQL 的數(shù)據(jù)是持久化的，意味著數(shù)據(jù)（索引+記錄）是保存到磁盤上的，因為這樣即使設(shè)備斷電了，數(shù)據(jù)也不會丟失。

磁盤是一個慢的離譜的存儲設(shè)備，有多離譜呢？

人家內(nèi)存的訪問速度是納秒級別的，而磁盤訪問的速度是毫秒級別的，也就是說讀取同樣大小的數(shù)據(jù)，磁盤中讀取的速度比從內(nèi)存中讀取的速度要慢上萬倍，甚至幾十萬倍。

磁盤讀寫的最小單位是扇區(qū)，扇區(qū)的大小只有 512B 大小，操作系統(tǒng)一次會讀寫多個扇區(qū)，所以操作系統(tǒng)的最小讀寫單位是塊（Block）。Linux 中的塊大小為4KB，也就是一次磁盤  I/O 操作會直接讀寫 8 個扇區(qū)。

由于數(shù)據(jù)庫的索引是保存到磁盤上的，因此當(dāng)我們通過索引查找某行數(shù)據(jù)的時候，就需要先從磁盤讀取索引到內(nèi)存，再通過索引從磁盤中找到某行數(shù)據(jù)，然后讀入到內(nèi)存，也就是說查詢過程中會發(fā)生多次磁盤 I/O，而磁盤 I/O 次數(shù)越多，所消耗的時間也就越大。

所以，我們希望索引的數(shù)據(jù)結(jié)構(gòu)能在盡可能少的磁盤的 I/O 操作中完成查詢工作，因為磁盤  I/O 操作越少，所消耗的時間也就越小。

另外，MySQL 是支持范圍查找的，所以索引的數(shù)據(jù)結(jié)構(gòu)不僅要能高效地查詢某一個記錄，而且也要能高效地執(zhí)行范圍查找。

所以，要設(shè)計一個適合 MySQL 索引的數(shù)據(jù)結(jié)構(gòu)，至少滿足以下要求：

能在盡可能少的磁盤的 I/O 操作中完成查詢工作；

要能高效地查詢某一個記錄，也要能高效地執(zhí)行范圍查找；

分析完要求后，我們針對每一個數(shù)據(jù)結(jié)構(gòu)分析一下。

什么是二分查找？
索引數(shù)據(jù)最好能按順序排列，這樣可以使用「二分查找法」高效定位數(shù)據(jù)。

假設(shè)我們現(xiàn)在用數(shù)組來存儲索引，比如下面有一個排序的數(shù)組，如果要從中找出數(shù)字 3，最簡單辦法就是從頭依次遍歷查詢，這種方法的時間復(fù)雜度是 O(n)，查詢效率并不高。因為該數(shù)組是有序的，所以我們可以采用二分查找法，比如下面這張采用二分法的查詢過程圖：

可以看到，二分查找法每次都把查詢的范圍減半，這樣時間復(fù)雜度就降到了 O(logn)，但是每次查找都需要不斷計算中間位置。

什么是二分查找樹？
用數(shù)組來實現(xiàn)線性排序的數(shù)據(jù)雖然簡單好用，但是插入新元素的時候性能太低。

因為插入一個元素，需要將這個元素之后的所有元素后移一位，如果這個操作發(fā)生在磁盤中呢？這必然是災(zāi)難性的。因為磁盤的速度比內(nèi)存慢幾十萬倍，所以我們不能用一種線性結(jié)構(gòu)將磁盤排序。

其次，有序的數(shù)組在使用二分查找的時候，每次查找都要不斷計算中間的位置。

那我們能不能設(shè)計一個非線形且天然適合二分查找的數(shù)據(jù)結(jié)構(gòu)呢？

有的，請看下圖這個神奇的操作，找到所有二分查找中用到的所有中間節(jié)點，把他們用指針連起來，并將最中間的節(jié)點作為根節(jié)點。

怎么樣？是不是變成了二叉樹，不過它不是普通的二叉樹，它是一個二叉查找樹。

二叉查找樹的特點是一個節(jié)點的左子樹的所有節(jié)點都小于這個節(jié)點，右子樹的所有節(jié)點都大于這個節(jié)點，這樣我們在查詢數(shù)據(jù)時，不需要計算中間節(jié)點的位置了，只需將查找的數(shù)據(jù)與節(jié)點的數(shù)據(jù)進(jìn)行比較。

假設(shè)，我們查找索引值為 key 的節(jié)點：

如果 key 大于根節(jié)點，則在右子樹中進(jìn)行查找；

如果 key 小于根節(jié)點，則在左子樹中進(jìn)行查找；

如果 key 等于根節(jié)點，也就是找到了這個節(jié)點，返回根節(jié)點即可。

二叉查找樹查找某個節(jié)點的動圖演示如下，比如要查找節(jié)點 3 ：

另外，二叉查找樹解決了插入新節(jié)點的問題，因為二叉查找樹是一個跳躍結(jié)構(gòu)，不必連續(xù)排列。這樣在插入的時候，新節(jié)點可以放在任何位置，不會像線性結(jié)構(gòu)那樣插入一個元素，所有元素都需要向后排列。

下面是二叉查找樹插入某個節(jié)點的動圖演示：

 

因此，二叉查找樹解決了連續(xù)結(jié)構(gòu)插入新元素開銷很大的問題，同時又保持著天然的二分結(jié)構(gòu)。

那是不是二叉查找樹就可以作為索引的數(shù)據(jù)結(jié)構(gòu)了呢？

不行不行，二叉查找樹存在一個極端情況，會導(dǎo)致它變成一個瘸子！

當(dāng)每次插入的元素都是二叉查找樹中最大的元素，二叉查找樹就會退化成了一條鏈表，查找數(shù)據(jù)的時間復(fù)雜度變成了 O(n)，如下動圖演示：

由于樹是存儲在磁盤中的，訪問每個節(jié)點，都對應(yīng)一次磁盤 I/O 操作（假設(shè)一個節(jié)點的大小「小于」操作系統(tǒng)的最小讀寫單位塊的大小），也就是說樹的高度就等于每次查詢數(shù)據(jù)時磁盤 IO 操作的次數(shù)，所以樹的高度越高，就會影響查詢性能。

二叉查找樹由于存在退化成鏈表的可能性，會使得查詢操作的時間復(fù)雜度從 O(logn)降低為 O(n)。

而且會隨著插入的元素越多，樹的高度也變高，意味著需要磁盤 IO 操作的次數(shù)就越多，這樣導(dǎo)致查詢性能嚴(yán)重下降，再加上不能范圍查詢，所以不適合作為數(shù)據(jù)庫的索引結(jié)構(gòu)。

什么是自平衡二叉樹？
為了解決二叉查找樹會在極端情況下退化成鏈表的問題，后面就有人提出平衡二叉查找樹（AVL 樹）。

主要是在二叉查找樹的基礎(chǔ)上增加了一些條件約束：每個節(jié)點的左子樹和右子樹的高度差不能超過 1。也就是說節(jié)點的左子樹和右子樹仍然為平衡二叉樹，這樣查詢操作的時間復(fù)雜度就會一直維持在 O(logn) 。

下圖是每次插入的元素都是平衡二叉查找樹中最大的元素，可以看到，它會維持自平衡：

除了平衡二叉查找樹，還有很多自平衡的二叉樹，比如紅黑樹，它也是通過一些約束條件來達(dá)到自平衡，不過紅黑樹的約束條件比較復(fù)雜，不是本篇的重點重點，大家可以看《數(shù)據(jù)結(jié)構(gòu)》相關(guān)的書籍來了解紅黑樹的約束條件。

下面是紅黑樹插入節(jié)點的過程，這左旋右旋的操作，就是為了自平衡。

不管平衡二叉查找樹還是紅黑樹，都會隨著插入的元素增多，而導(dǎo)致樹的高度變高，這就意味著磁盤 I/O 操作次數(shù)多，會影響整體數(shù)據(jù)查詢的效率。

比如，下面這個平衡二叉查找樹的高度為 5，那么在訪問最底部的節(jié)點時，就需要磁盤 5 次 I/O 操作。

根本原因是因為它們都是二叉樹，也就是每個節(jié)點只能保存 2 個子節(jié)點 ，如果我們把二叉樹改成 M 叉樹（M>2）呢？

比如，當(dāng) M=3 時，在同樣的節(jié)點個數(shù)情況下，三叉樹比二叉樹的樹高要矮。

因此，當(dāng)樹的節(jié)點越多的時候，并且樹的分叉數(shù) M 越大的時候，M 叉樹的高度會遠(yuǎn)小于二叉樹的高度。

什么是 B 樹
自平衡二叉樹雖然能保持查詢操作的時間復(fù)雜度在O(logn)，但是因為它本質(zhì)上是一個二叉樹，每個節(jié)點只能有 2 個子節(jié)點，那么當(dāng)節(jié)點個數(shù)越多的時候，樹的高度也會相應(yīng)變高，這樣就會增加磁盤的 I/O 次數(shù)，從而影響數(shù)據(jù)查詢的效率。

為了解決降低樹的高度的問題，后面就出來了 B 樹，它不再限制一個節(jié)點就只能有 2 個子節(jié)點，而是允許 M 個子節(jié)點 (M>2)，從而降低樹的高度。

B 樹的每一個節(jié)點最多可以包括 M 個子節(jié)點，M 稱為 B 樹的階，所以 B 樹就是一個多叉樹。

假設(shè) M = 3，那么就是一棵 3 階的 B 樹，特點就是每個節(jié)點最多有 2 個（M-1個）數(shù)據(jù)和最多有 3 個（M個）子節(jié)點，超過這些要求的話，就會分裂節(jié)點，比如下面的的動圖：

我們來看看一棵 3 階的 B 樹的查詢過程是怎樣的？

假設(shè)我們在上圖一棵 3 階的 B 樹中要查找的索引值是 9 的記錄那么步驟可以分為以下幾步：

與根節(jié)點的索引(4，8）進(jìn)行比較，9 大于 8，那么往右邊的子節(jié)點走；

然后該子節(jié)點的索引為（10，12），因為 9 小于 10，所以會往該節(jié)點的左邊子節(jié)點走；

走到索引為9的節(jié)點，然后我們找到了索引值 9 的節(jié)點。

可以看到，一棵 3 階的 B 樹在查詢?nèi)~子節(jié)點中的數(shù)據(jù)時，由于樹的高度是 3 ，所以在查詢過程中會發(fā)生 3 次磁盤 I/O 操作。

而如果同樣的節(jié)點數(shù)量在平衡二叉樹的場景下，樹的高度就會很高，意味著磁盤 I/O 操作會更多。所以，B 樹在數(shù)據(jù)查詢中比平衡二叉樹效率要高。

但是 B 樹的每個節(jié)點都包含數(shù)據(jù)（索引+記錄），而用戶的記錄數(shù)據(jù)的大小很有可能遠(yuǎn)遠(yuǎn)超過了索引數(shù)據(jù)，這就需要花費更多的磁盤 I/O 操作次數(shù)來讀到「有用的索引數(shù)據(jù)」。

而且，在我們查詢位于底層的某個節(jié)點（比如 A 記錄）過程中，「非 A 記錄節(jié)點」里的記錄數(shù)據(jù)會從磁盤加載到內(nèi)存，但是這些記錄數(shù)據(jù)是沒用的，我們只是想讀取這些節(jié)點的索引數(shù)據(jù)來做比較查詢，而「非 A 記錄節(jié)點」里的記錄數(shù)據(jù)對我們是沒用的，這樣不僅增多磁盤 I/O 操作次數(shù)，也占用內(nèi)存資源。

另外，如果使用 B 樹來做范圍查詢的話，需要使用中序遍歷，這會涉及多個節(jié)點的磁盤 I/O  問題，從而導(dǎo)致整體速度下降。

什么是 B+ 樹？
B+ 樹就是對 B 樹做了一個升級，MySQL 中索引的數(shù)據(jù)結(jié)構(gòu)就是采用了 B+ 樹，B+ 樹結(jié)構(gòu)如下圖：

B+ 樹與 B 樹差異的點，主要是以下這幾點：

葉子節(jié)點（最底部的節(jié)點）才會存放實際數(shù)據(jù)（索引+記錄），非葉子節(jié)點只會存放索引；

所有索引都會在葉子節(jié)點出現(xiàn)，葉子節(jié)點之間構(gòu)成一個有序鏈表；

非葉子節(jié)點的索引也會同時存在在子節(jié)點中，并且是在子節(jié)點中所有索引的最大（或最?。?。

非葉子節(jié)點中有多少個子節(jié)點，就有多少個索引；

下面通過三個方面，比較下 B+ 和 B 樹的性能區(qū)別。

1、單點查詢

B 樹進(jìn)行單個索引查詢時，最快可以在 O(1) 的時間代價內(nèi)就查到，而從平均時間代價來看，會比 B+ 樹稍快一些。

但是 B 樹的查詢波動會比較大，因為每個節(jié)點即存索引又存記錄，所以有時候訪問到了非葉子節(jié)點就可以找到索引，而有時需要訪問到葉子節(jié)點才能找到索引。

B+ 樹的非葉子節(jié)點不存放實際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲即存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點的磁盤 I/O次數(shù)會更少。

2、插入和刪除效率

B+ 樹有大量的冗余節(jié)點，這樣使得刪除一個節(jié)點的時候，可以直接從葉子節(jié)點中刪除，甚至可以不動非葉子節(jié)點，這樣刪除非?？欤?/p>

比如下面這個動圖是刪除 B+ 樹某個葉子節(jié)點節(jié)點的過程：

注意，：B+ 樹對于非葉子節(jié)點的子節(jié)點和索引的個數(shù)，定義方式可能會有不同，有的是說非葉子節(jié)點的子節(jié)點的個數(shù)為 M 階，而索引的個數(shù)為 M-1（這個是維基百科里的定義），因此我本文關(guān)于 B+ 樹的動圖都是基于這個。但是我在前面介紹 B+ 樹與 B+ 樹的差異時，說的是「非葉子節(jié)點中有多少個子節(jié)點，就有多少個索引」，主要是 MySQL 用到的 B+ 樹就是這個特性。

甚至，B+ 樹在刪除根節(jié)點的時候，由于存在冗余的節(jié)點，所以不會發(fā)生復(fù)雜的樹的變形，比如下面這個動圖是刪除 B+ 樹根節(jié)點的過程：

B 樹則不同，B 樹沒有冗余節(jié)點，刪除節(jié)點的時候非常復(fù)雜，比如刪除根節(jié)點中的數(shù)據(jù)，可能涉及復(fù)雜的樹的變形，比如下面這個動圖是刪除 B 樹根節(jié)點的過程：

B+ 樹的插入也是一樣，有冗余節(jié)點，插入可能存在節(jié)點的分裂（如果節(jié)點飽和），但是最多只涉及樹的一條路徑。而且 B+ 樹會自動平衡，不需要像更多復(fù)雜的算法，類似紅黑樹的旋轉(zhuǎn)操作等。

因此，B+ 樹的插入和刪除效率更高。

3、范圍查詢

B 樹和 B+ 樹等值查詢原理基本一致，先從根節(jié)點查找，然后對比目標(biāo)數(shù)據(jù)的范圍，最后遞歸的進(jìn)入子節(jié)點查找。

因為 B+ 樹所有葉子節(jié)點間還有一個鏈表進(jìn)行連接，這種設(shè)計對范圍查找非常有幫助，比如說我們想知道 12 月 1 日和 12 月 12 日之間的訂單，這個時候可以先查找到 12 月 1 日所在的葉子節(jié)點，然后利用鏈表向右遍歷，直到找到 12 月12 日的節(jié)點，這樣就不需要從根節(jié)點查詢了，進(jìn)一步節(jié)省查詢需要的時間。

而 B 樹沒有將所有葉子節(jié)點用鏈表串聯(lián)起來的結(jié)構(gòu)，因此只能通過樹的遍歷來完成范圍查詢，這會涉及多個節(jié)點的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。

因此，存在大量范圍檢索的場景，適合使用 B+樹，比如數(shù)據(jù)庫。而對于大量的單個索引查詢的場景，可以考慮 B 樹，比如 nosql 的MongoDB。

MySQL 中的 B+ 樹

MySQL 的存儲方式根據(jù)存儲引擎的不同而不同，我們最常用的就是 Innodb 存儲引擎，它就是采用了 B+ 樹作為了索引的數(shù)據(jù)結(jié)構(gòu)。

下圖就是 Innodb 里的 B+ 樹：

但是 Innodb 使用的  B+ 樹有一些特別的點，比如：

B+ 樹的葉子節(jié)點之間是用「雙向鏈表」進(jìn)行連接，這樣的好處是既能向右遍歷，也能向左遍歷。

B+ 樹點節(jié)點內(nèi)容是數(shù)據(jù)頁，數(shù)據(jù)頁里存放了用戶的記錄以及各種信息，每個數(shù)據(jù)頁默認(rèn)大小是 16 KB。

Innodb 根據(jù)索引類型不同，分為聚集和二級索引。他們區(qū)別在于，聚集索引的葉子節(jié)點存放的是實際數(shù)據(jù)，所有完整的用戶記錄都存放在聚集索引的葉子節(jié)點，而二級索引的葉子節(jié)點存放的是主鍵值，而不是實際數(shù)據(jù)。

因為表的數(shù)據(jù)都是存放在聚集索引的葉子節(jié)點里，所以 InnoDB 存儲引擎一定會為表創(chuàng)建一個聚集索引，且由于數(shù)據(jù)在物理上只會保存一份，所以聚簇索引只能有一個，而二級索引可以創(chuàng)建多個。

總結(jié)
MySQL 是會將數(shù)據(jù)持久化在硬盤，而存儲功能是由 MySQL 存儲引擎實現(xiàn)的，所以討論 MySQL 使用哪種數(shù)據(jù)結(jié)構(gòu)作為索引，實際上是在討論存儲引使用哪種數(shù)據(jù)結(jié)構(gòu)作為索引，InnoDB 是 MySQL 默認(rèn)的存儲引擎，它就是采用了 B+ 樹作為索引的數(shù)據(jù)結(jié)構(gòu)。

要設(shè)計一個 MySQL 的索引數(shù)據(jù)結(jié)構(gòu)，不僅僅考慮數(shù)據(jù)結(jié)構(gòu)增刪改的時間復(fù)雜度，更重要的是要考慮磁盤 I/0 的操作次數(shù)。因為索引和記錄都是存放在硬盤，硬盤是一個非常慢的存儲設(shè)備，我們在查詢數(shù)據(jù)的時候，最好能在盡可能少的磁盤 I/0 的操作次數(shù)內(nèi)完成。

二分查找樹雖然是一個天然的二分結(jié)構(gòu)，能很好的利用二分查找快速定位數(shù)據(jù)，但是它存在一種極端的情況，每當(dāng)插入的元素都是樹內(nèi)最大的元素，就會導(dǎo)致二分查找樹退化成一個鏈表，此時查詢復(fù)雜度就會從 O(logn)降低為 O(n)。

為了解決二分查找樹退化成鏈表的問題，就出現(xiàn)了自平衡二叉樹，保證了查詢操作的時間復(fù)雜度就會一直維持在 O(logn) 。但是它本質(zhì)上還是一個二叉樹，每個節(jié)點只能有 2 個子節(jié)點，隨著元素的增多，樹的高度會越來越高。

而樹的高度決定于磁盤  I/O 操作的次數(shù)，因為樹是存儲在磁盤中的，訪問每個節(jié)點，都對應(yīng)一次磁盤 I/O 操作，也就是說樹的高度就等于每次查詢數(shù)據(jù)時磁盤 IO 操作的次數(shù)，所以樹的高度越高，就會影響查詢性能。

B 樹和 B+ 都是通過多叉樹的方式，會將樹的高度變矮，所以這兩個數(shù)據(jù)結(jié)構(gòu)非常適合檢索存于磁盤中的數(shù)據(jù)。

但是 MySQL 默認(rèn)的存儲引擎 InnoDB 采用的是 B+ 作為索引的數(shù)據(jù)結(jié)構(gòu)，原因有：

B+ 樹的非葉子節(jié)點不存放實際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲即存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點的磁盤 I/O次數(shù)會更少。

B+ 樹有大量的冗余節(jié)點（所有非葉子節(jié)點都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，比如刪除根節(jié)點的時候，不會像 B 樹那樣會發(fā)生復(fù)雜的樹的變化；

B+ 樹葉子節(jié)點之間用鏈表連接了起來，有利于范圍查詢，而 B 樹要實現(xiàn)范圍查詢，因此只能通過樹的遍歷來完成范圍查詢，這會涉及多個節(jié)點的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。