「為什么 MySQL 采用 B+ 樹作為索引？」這句話，是不是在面試時(shí)經(jīng)常出現(xiàn)。
要解釋這個(gè)問題，其實(shí)不單單要從數(shù)據(jù)結(jié)構(gòu)的角度出發(fā)，還要考慮磁盤 I/O 操作次數(shù)，因?yàn)?MySQL 的數(shù)據(jù)是存儲(chǔ)在磁盤中的嘛。
這次，就跟大家一層一層的分析這個(gè)問題，圖中包含大量的動(dòng)圖來(lái)幫助大家理解，相信看完你就拿捏這道題目了！
怎樣的索引的數(shù)據(jù)結(jié)構(gòu)是好的？
MySQL 的數(shù)據(jù)是持久化的，意味著數(shù)據(jù)（索引+記錄）是保存到磁盤上的，因?yàn)檫@樣即使設(shè)備斷電了，數(shù)據(jù)也不會(huì)丟失。
磁盤是一個(gè)慢的離譜的存儲(chǔ)設(shè)備，有多離譜呢？
人家內(nèi)存的訪問速度是納秒級(jí)別的，而磁盤訪問的速度是毫秒級(jí)別的，也就是說(shuō)讀取同樣大小的數(shù)據(jù)，磁盤中讀取的速度比從內(nèi)存中讀取的速度要慢上萬(wàn)倍，甚至幾十萬(wàn)倍。
磁盤讀寫的最小單位是扇區(qū)，扇區(qū)的大小只有 512B 大小，操作系統(tǒng)一次會(huì)讀寫多個(gè)扇區(qū)，所以操作系統(tǒng)的最小讀寫單位是塊（Block）。Linux 中的塊大小為4KB，也就是一次磁盤 I/O 操作會(huì)直接讀寫 8 個(gè)扇區(qū)。
由于數(shù)據(jù)庫(kù)的索引是保存到磁盤上的，因此當(dāng)我們通過索引查找某行數(shù)據(jù)的時(shí)候，就需要先從磁盤讀取索引到內(nèi)存，再通過索引從磁盤中找到某行數(shù)據(jù)，然后讀入到內(nèi)存，也就是說(shuō)查詢過程中會(huì)發(fā)生多次磁盤 I/O，而磁盤 I/O 次數(shù)越多，所消耗的時(shí)間也就越大。
所以，我們希望索引的數(shù)據(jù)結(jié)構(gòu)能在盡可能少的磁盤的 I/O 操作中完成查詢工作，因?yàn)榇疟P I/O 操作越少，所消耗的時(shí)間也就越小。
另外，MySQL 是支持范圍查找的，所以索引的數(shù)據(jù)結(jié)構(gòu)不僅要能高效地查詢某一個(gè)記錄，而且也要能高效地執(zhí)行范圍查找。
所以，要設(shè)計(jì)一個(gè)適合 MySQL 索引的數(shù)據(jù)結(jié)構(gòu)，至少滿足以下要求：
能在盡可能少的磁盤的 I/O 操作中完成查詢工作；
要能高效地查詢某一個(gè)記錄，也要能高效地執(zhí)行范圍查找；
分析完要求后，我們針對(duì)每一個(gè)數(shù)據(jù)結(jié)構(gòu)分析一下。
什么是二分查找？
索引數(shù)據(jù)最好能按順序排列，這樣可以使用「二分查找法」高效定位數(shù)據(jù)。
假設(shè)我們現(xiàn)在用數(shù)組來(lái)存儲(chǔ)索引，比如下面有一個(gè)排序的數(shù)組，如果要從中找出數(shù)字 3，最簡(jiǎn)單辦法就是從頭依次遍歷查詢，這種方法的時(shí)間復(fù)雜度是 O(n)，查詢效率并不高。因?yàn)樵摂?shù)組是有序的，所以我們可以采用二分查找法，比如下面這張采用二分法的查詢過程圖：
可以看到，二分查找法每次都把查詢的范圍減半，這樣時(shí)間復(fù)雜度就降到了 O(logn)，但是每次查找都需要不斷計(jì)算中間位置。
什么是二分查找樹？
用數(shù)組來(lái)實(shí)現(xiàn)線性排序的數(shù)據(jù)雖然簡(jiǎn)單好用，但是插入新元素的時(shí)候性能太低。
因?yàn)椴迦胍粋€(gè)元素，需要將這個(gè)元素之后的所有元素后移一位，如果這個(gè)操作發(fā)生在磁盤中呢？這必然是災(zāi)難性的。因?yàn)榇疟P的速度比內(nèi)存慢幾十萬(wàn)倍，所以我們不能用一種線性結(jié)構(gòu)將磁盤排序。
其次，有序的數(shù)組在使用二分查找的時(shí)候，每次查找都要不斷計(jì)算中間的位置。
那我們能不能設(shè)計(jì)一個(gè)非線形且天然適合二分查找的數(shù)據(jù)結(jié)構(gòu)呢？
有的，請(qǐng)看下圖這個(gè)神奇的操作，找到所有二分查找中用到的所有中間節(jié)點(diǎn)，把他們用指針連起來(lái)，并將最中間的節(jié)點(diǎn)作為根節(jié)點(diǎn)。
怎么樣？是不是變成了二叉樹，不過它不是普通的二叉樹，它是一個(gè)二叉查找樹。
二叉查找樹的特點(diǎn)是一個(gè)節(jié)點(diǎn)的左子樹的所有節(jié)點(diǎn)都小于這個(gè)節(jié)點(diǎn)，右子樹的所有節(jié)點(diǎn)都大于這個(gè)節(jié)點(diǎn)，這樣我們?cè)诓樵償?shù)據(jù)時(shí)，不需要計(jì)算中間節(jié)點(diǎn)的位置了，只需將查找的數(shù)據(jù)與節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行比較。
假設(shè)，我們查找索引值為 key 的節(jié)點(diǎn)：
如果 key 大于根節(jié)點(diǎn)，則在右子樹中進(jìn)行查找；
如果 key 小于根節(jié)點(diǎn)，則在左子樹中進(jìn)行查找；
如果 key 等于根節(jié)點(diǎn)，也就是找到了這個(gè)節(jié)點(diǎn)，返回根節(jié)點(diǎn)即可。
二叉查找樹查找某個(gè)節(jié)點(diǎn)的動(dòng)圖演示如下，比如要查找節(jié)點(diǎn) 3 ：
另外，二叉查找樹解決了插入新節(jié)點(diǎn)的問題，因?yàn)槎娌檎覙涫且粋€(gè)跳躍結(jié)構(gòu)，不必連續(xù)排列。這樣在插入的時(shí)候，新節(jié)點(diǎn)可以放在任何位置，不會(huì)像線性結(jié)構(gòu)那樣插入一個(gè)元素，所有元素都需要向后排列。
下面是二叉查找樹插入某個(gè)節(jié)點(diǎn)的動(dòng)圖演示：
因此，二叉查找樹解決了連續(xù)結(jié)構(gòu)插入新元素開銷很大的問題，同時(shí)又保持著天然的二分結(jié)構(gòu)。
那是不是二叉查找樹就可以作為索引的數(shù)據(jù)結(jié)構(gòu)了呢？
不行不行，二叉查找樹存在一個(gè)極端情況，會(huì)導(dǎo)致它變成一個(gè)瘸子！
當(dāng)每次插入的元素都是二叉查找樹中最大的元素，二叉查找樹就會(huì)退化成了一條鏈表，查找數(shù)據(jù)的時(shí)間復(fù)雜度變成了 O(n)，如下動(dòng)圖演示：
由于樹是存儲(chǔ)在磁盤中的，訪問每個(gè)節(jié)點(diǎn)，都對(duì)應(yīng)一次磁盤 I/O 操作（假設(shè)一個(gè)節(jié)點(diǎn)的大小「小于」操作系統(tǒng)的最小讀寫單位塊的大小），也就是說(shuō)樹的高度就等于每次查詢數(shù)據(jù)時(shí)磁盤 IO 操作的次數(shù)，所以樹的高度越高，就會(huì)影響查詢性能。
二叉查找樹由于存在退化成鏈表的可能性，會(huì)使得查詢操作的時(shí)間復(fù)雜度從 O(logn)降低為 O(n)。
而且會(huì)隨著插入的元素越多，樹的高度也變高，意味著需要磁盤 IO 操作的次數(shù)就越多，這樣導(dǎo)致查詢性能嚴(yán)重下降，再加上不能范圍查詢，所以不適合作為數(shù)據(jù)庫(kù)的索引結(jié)構(gòu)。
什么是自平衡二叉樹？
為了解決二叉查找樹會(huì)在極端情況下退化成鏈表的問題，后面就有人提出平衡二叉查找樹（AVL 樹）。
主要是在二叉查找樹的基礎(chǔ)上增加了一些條件約束：每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差不能超過 1。也就是說(shuō)節(jié)點(diǎn)的左子樹和右子樹仍然為平衡二叉樹，這樣查詢操作的時(shí)間復(fù)雜度就會(huì)一直維持在 O(logn) 。
下圖是每次插入的元素都是平衡二叉查找樹中最大的元素，可以看到，它會(huì)維持自平衡：
除了平衡二叉查找樹，還有很多自平衡的二叉樹，比如紅黑樹，它也是通過一些約束條件來(lái)達(dá)到自平衡，不過紅黑樹的約束條件比較復(fù)雜，不是本篇的重點(diǎn)重點(diǎn)，大家可以看《數(shù)據(jù)結(jié)構(gòu)》相關(guān)的書籍來(lái)了解紅黑樹的約束條件。
下面是紅黑樹插入節(jié)點(diǎn)的過程，這左旋右旋的操作，就是為了自平衡。
不管平衡二叉查找樹還是紅黑樹，都會(huì)隨著插入的元素增多，而導(dǎo)致樹的高度變高，這就意味著磁盤 I/O 操作次數(shù)多，會(huì)影響整體數(shù)據(jù)查詢的效率。
比如，下面這個(gè)平衡二叉查找樹的高度為 5，那么在訪問最底部的節(jié)點(diǎn)時(shí)，就需要磁盤 5 次 I/O 操作。
根本原因是因?yàn)樗鼈兌际嵌鏄洌簿褪敲總€(gè)節(jié)點(diǎn)只能保存 2 個(gè)子節(jié)點(diǎn) ，如果我們把二叉樹改成 M 叉樹（M>2）呢？
比如，當(dāng) M=3 時(shí)，在同樣的節(jié)點(diǎn)個(gè)數(shù)情況下，三叉樹比二叉樹的樹高要矮。
因此，當(dāng)樹的節(jié)點(diǎn)越多的時(shí)候，并且樹的分叉數(shù) M 越大的時(shí)候，M 叉樹的高度會(huì)遠(yuǎn)小于二叉樹的高度。
什么是 B 樹
自平衡二叉樹雖然能保持查詢操作的時(shí)間復(fù)雜度在O(logn)，但是因?yàn)樗举|(zhì)上是一個(gè)二叉樹，每個(gè)節(jié)點(diǎn)只能有 2 個(gè)子節(jié)點(diǎn)，那么當(dāng)節(jié)點(diǎn)個(gè)數(shù)越多的時(shí)候，樹的高度也會(huì)相應(yīng)變高，這樣就會(huì)增加磁盤的 I/O 次數(shù)，從而影響數(shù)據(jù)查詢的效率。
為了解決降低樹的高度的問題，后面就出來(lái)了 B 樹，它不再限制一個(gè)節(jié)點(diǎn)就只能有 2 個(gè)子節(jié)點(diǎn)，而是允許 M 個(gè)子節(jié)點(diǎn) (M>2)，從而降低樹的高度。
B 樹的每一個(gè)節(jié)點(diǎn)最多可以包括 M 個(gè)子節(jié)點(diǎn)，M 稱為 B 樹的階，所以 B 樹就是一個(gè)多叉樹。
假設(shè) M = 3，那么就是一棵 3 階的 B 樹，特點(diǎn)就是每個(gè)節(jié)點(diǎn)最多有 2 個(gè)（M-1個(gè)）數(shù)據(jù)和最多有 3 個(gè)（M個(gè)）子節(jié)點(diǎn)，超過這些要求的話，就會(huì)分裂節(jié)點(diǎn)，比如下面的的動(dòng)圖：
我們來(lái)看看一棵 3 階的 B 樹的查詢過程是怎樣的？
假設(shè)我們?cè)谏蠄D一棵 3 階的 B 樹中要查找的索引值是 9 的記錄那么步驟可以分為以下幾步：
與根節(jié)點(diǎn)的索引(4，8）進(jìn)行比較，9 大于 8，那么往右邊的子節(jié)點(diǎn)走；
然后該子節(jié)點(diǎn)的索引為（10，12），因?yàn)?9 小于 10，所以會(huì)往該節(jié)點(diǎn)的左邊子節(jié)點(diǎn)走；
走到索引為9的節(jié)點(diǎn)，然后我們找到了索引值 9 的節(jié)點(diǎn)。
可以看到，一棵 3 階的 B 樹在查詢?nèi)~子節(jié)點(diǎn)中的數(shù)據(jù)時(shí)，由于樹的高度是 3 ，所以在查詢過程中會(huì)發(fā)生 3 次磁盤 I/O 操作。
而如果同樣的節(jié)點(diǎn)數(shù)量在平衡二叉樹的場(chǎng)景下，樹的高度就會(huì)很高，意味著磁盤 I/O 操作會(huì)更多。所以，B 樹在數(shù)據(jù)查詢中比平衡二叉樹效率要高。
但是 B 樹的每個(gè)節(jié)點(diǎn)都包含數(shù)據(jù)（索引+記錄），而用戶的記錄數(shù)據(jù)的大小很有可能遠(yuǎn)遠(yuǎn)超過了索引數(shù)據(jù)，這就需要花費(fèi)更多的磁盤 I/O 操作次數(shù)來(lái)讀到「有用的索引數(shù)據(jù)」。
而且，在我們查詢位于底層的某個(gè)節(jié)點(diǎn)（比如 A 記錄）過程中，「非 A 記錄節(jié)點(diǎn)」里的記錄數(shù)據(jù)會(huì)從磁盤加載到內(nèi)存，但是這些記錄數(shù)據(jù)是沒用的，我們只是想讀取這些節(jié)點(diǎn)的索引數(shù)據(jù)來(lái)做比較查詢，而「非 A 記錄節(jié)點(diǎn)」里的記錄數(shù)據(jù)對(duì)我們是沒用的，這樣不僅增多磁盤 I/O 操作次數(shù)，也占用內(nèi)存資源。
另外，如果使用 B 樹來(lái)做范圍查詢的話，需要使用中序遍歷，這會(huì)涉及多個(gè)節(jié)點(diǎn)的磁盤 I/O 問題，從而導(dǎo)致整體速度下降。
什么是 B+ 樹？
B+ 樹就是對(duì) B 樹做了一個(gè)升級(jí)，MySQL 中索引的數(shù)據(jù)結(jié)構(gòu)就是采用了 B+ 樹，B+ 樹結(jié)構(gòu)如下圖：
B+ 樹與 B 樹差異的點(diǎn)，主要是以下這幾點(diǎn)：
葉子節(jié)點(diǎn)（最底部的節(jié)點(diǎn)）才會(huì)存放實(shí)際數(shù)據(jù)（索引+記錄），非葉子節(jié)點(diǎn)只會(huì)存放索引；
所有索引都會(huì)在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)之間構(gòu)成一個(gè)有序鏈表；
非葉子節(jié)點(diǎn)的索引也會(huì)同時(shí)存在在子節(jié)點(diǎn)中，并且是在子節(jié)點(diǎn)中所有索引的最大（或最小）。
非葉子節(jié)點(diǎn)中有多少個(gè)子節(jié)點(diǎn)，就有多少個(gè)索引；
下面通過三個(gè)方面，比較下 B+ 和 B 樹的性能區(qū)別。
1、單點(diǎn)查詢
B 樹進(jìn)行單個(gè)索引查詢時(shí)，最快可以在 O(1) 的時(shí)間代價(jià)內(nèi)就查到，而從平均時(shí)間代價(jià)來(lái)看，會(huì)比 B+ 樹稍快一些。
但是 B 樹的查詢波動(dòng)會(huì)比較大，因?yàn)槊總€(gè)節(jié)點(diǎn)即存索引又存記錄，所以有時(shí)候訪問到了非葉子節(jié)點(diǎn)就可以找到索引，而有時(shí)需要訪問到葉子節(jié)點(diǎn)才能找到索引。
B+ 樹的非葉子節(jié)點(diǎn)不存放實(shí)際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲(chǔ)即存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點(diǎn)可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點(diǎn)的磁盤 I/O次數(shù)會(huì)更少。
2、插入和刪除效率
B+ 樹有大量的冗余節(jié)點(diǎn)，這樣使得刪除一個(gè)節(jié)點(diǎn)的時(shí)候，可以直接從葉子節(jié)點(diǎn)中刪除，甚至可以不動(dòng)非葉子節(jié)點(diǎn)，這樣刪除非?？?，
比如下面這個(gè)動(dòng)圖是刪除 B+ 樹某個(gè)葉子節(jié)點(diǎn)節(jié)點(diǎn)的過程：
注意，：B+ 樹對(duì)于非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)和索引的個(gè)數(shù)，定義方式可能會(huì)有不同，有的是說(shuō)非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)為 M 階，而索引的個(gè)數(shù)為 M-1（這個(gè)是維基百科里的定義），因此我本文關(guān)于 B+ 樹的動(dòng)圖都是基于這個(gè)。但是我在前面介紹 B+ 樹與 B+ 樹的差異時(shí)，說(shuō)的是「非葉子節(jié)點(diǎn)中有多少個(gè)子節(jié)點(diǎn)，就有多少個(gè)索引」，主要是 MySQL 用到的 B+ 樹就是這個(gè)特性。
甚至，B+ 樹在刪除根節(jié)點(diǎn)的時(shí)候，由于存在冗余的節(jié)點(diǎn)，所以不會(huì)發(fā)生復(fù)雜的樹的變形，比如下面這個(gè)動(dòng)圖是刪除 B+ 樹根節(jié)點(diǎn)的過程：
B 樹則不同，B 樹沒有冗余節(jié)點(diǎn)，刪除節(jié)點(diǎn)的時(shí)候非常復(fù)雜，比如刪除根節(jié)點(diǎn)中的數(shù)據(jù)，可能涉及復(fù)雜的樹的變形，比如下面這個(gè)動(dòng)圖是刪除 B 樹根節(jié)點(diǎn)的過程：
B+ 樹的插入也是一樣，有冗余節(jié)點(diǎn)，插入可能存在節(jié)點(diǎn)的分裂（如果節(jié)點(diǎn)飽和），但是最多只涉及樹的一條路徑。而且 B+ 樹會(huì)自動(dòng)平衡，不需要像更多復(fù)雜的算法，類似紅黑樹的旋轉(zhuǎn)操作等。
因此，B+ 樹的插入和刪除效率更高。
3、范圍查詢
B 樹和 B+ 樹等值查詢?cè)砘疽恢?，先從根?jié)點(diǎn)查找，然后對(duì)比目標(biāo)數(shù)據(jù)的范圍，最后遞歸的進(jìn)入子節(jié)點(diǎn)查找。
因?yàn)?B+ 樹所有葉子節(jié)點(diǎn)間還有一個(gè)鏈表進(jìn)行連接，這種設(shè)計(jì)對(duì)范圍查找非常有幫助，比如說(shuō)我們想知道 12 月 1 日和 12 月 12 日之間的訂單，這個(gè)時(shí)候可以先查找到 12 月 1 日所在的葉子節(jié)點(diǎn)，然后利用鏈表向右遍歷，直到找到 12 月12 日的節(jié)點(diǎn)，這樣就不需要從根節(jié)點(diǎn)查詢了，進(jìn)一步節(jié)省查詢需要的時(shí)間。
而 B 樹沒有將所有葉子節(jié)點(diǎn)用鏈表串聯(lián)起來(lái)的結(jié)構(gòu)，因此只能通過樹的遍歷來(lái)完成范圍查詢，這會(huì)涉及多個(gè)節(jié)點(diǎn)的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。
因此，存在大量范圍檢索的場(chǎng)景，適合使用 B+樹，比如數(shù)據(jù)庫(kù)。而對(duì)于大量的單個(gè)索引查詢的場(chǎng)景，可以考慮 B 樹，比如 nosql 的MongoDB。
MySQL 中的 B+ 樹
MySQL 的存儲(chǔ)方式根據(jù)存儲(chǔ)引擎的不同而不同，我們最常用的就是 Innodb 存儲(chǔ)引擎，它就是采用了 B+ 樹作為了索引的數(shù)據(jù)結(jié)構(gòu)。
下圖就是 Innodb 里的 B+ 樹：
但是 Innodb 使用的 B+ 樹有一些特別的點(diǎn)，比如：
B+ 樹的葉子節(jié)點(diǎn)之間是用「雙向鏈表」進(jìn)行連接，這樣的好處是既能向右遍歷，也能向左遍歷。
B+ 樹點(diǎn)節(jié)點(diǎn)內(nèi)容是數(shù)據(jù)頁(yè)，數(shù)據(jù)頁(yè)里存放了用戶的記錄以及各種信息，每個(gè)數(shù)據(jù)頁(yè)默認(rèn)大小是 16 KB。
Innodb 根據(jù)索引類型不同，分為聚集和二級(jí)索引。他們區(qū)別在于，聚集索引的葉子節(jié)點(diǎn)存放的是實(shí)際數(shù)據(jù)，所有完整的用戶記錄都存放在聚集索引的葉子節(jié)點(diǎn)，而二級(jí)索引的葉子節(jié)點(diǎn)存放的是主鍵值，而不是實(shí)際數(shù)據(jù)。
因?yàn)楸淼臄?shù)據(jù)都是存放在聚集索引的葉子節(jié)點(diǎn)里，所以 InnoDB 存儲(chǔ)引擎一定會(huì)為表創(chuàng)建一個(gè)聚集索引，且由于數(shù)據(jù)在物理上只會(huì)保存一份，所以聚簇索引只能有一個(gè)，而二級(jí)索引可以創(chuàng)建多個(gè)。
總結(jié)
MySQL 是會(huì)將數(shù)據(jù)持久化在硬盤，而存儲(chǔ)功能是由 MySQL 存儲(chǔ)引擎實(shí)現(xiàn)的，所以討論 MySQL 使用哪種數(shù)據(jù)結(jié)構(gòu)作為索引，實(shí)際上是在討論存儲(chǔ)引使用哪種數(shù)據(jù)結(jié)構(gòu)作為索引，InnoDB 是 MySQL 默認(rèn)的存儲(chǔ)引擎，它就是采用了 B+ 樹作為索引的數(shù)據(jù)結(jié)構(gòu)。
要設(shè)計(jì)一個(gè) MySQL 的索引數(shù)據(jù)結(jié)構(gòu)，不僅僅考慮數(shù)據(jù)結(jié)構(gòu)增刪改的時(shí)間復(fù)雜度，更重要的是要考慮磁盤 I/0 的操作次數(shù)。因?yàn)樗饕陀涗浂际谴娣旁谟脖P，硬盤是一個(gè)非常慢的存儲(chǔ)設(shè)備，我們?cè)诓樵償?shù)據(jù)的時(shí)候，最好能在盡可能少的磁盤 I/0 的操作次數(shù)內(nèi)完成。
二分查找樹雖然是一個(gè)天然的二分結(jié)構(gòu)，能很好的利用二分查找快速定位數(shù)據(jù)，但是它存在一種極端的情況，每當(dāng)插入的元素都是樹內(nèi)最大的元素，就會(huì)導(dǎo)致二分查找樹退化成一個(gè)鏈表，此時(shí)查詢復(fù)雜度就會(huì)從 O(logn)降低為 O(n)。
為了解決二分查找樹退化成鏈表的問題，就出現(xiàn)了自平衡二叉樹，保證了查詢操作的時(shí)間復(fù)雜度就會(huì)一直維持在 O(logn) 。但是它本質(zhì)上還是一個(gè)二叉樹，每個(gè)節(jié)點(diǎn)只能有 2 個(gè)子節(jié)點(diǎn)，隨著元素的增多，樹的高度會(huì)越來(lái)越高。
而樹的高度決定于磁盤 I/O 操作的次數(shù)，因?yàn)闃涫谴鎯?chǔ)在磁盤中的，訪問每個(gè)節(jié)點(diǎn)，都對(duì)應(yīng)一次磁盤 I/O 操作，也就是說(shuō)樹的高度就等于每次查詢數(shù)據(jù)時(shí)磁盤 IO 操作的次數(shù)，所以樹的高度越高，就會(huì)影響查詢性能。
B 樹和 B+ 都是通過多叉樹的方式，會(huì)將樹的高度變矮，所以這兩個(gè)數(shù)據(jù)結(jié)構(gòu)非常適合檢索存于磁盤中的數(shù)據(jù)。
但是 MySQL 默認(rèn)的存儲(chǔ)引擎 InnoDB 采用的是 B+ 作為索引的數(shù)據(jù)結(jié)構(gòu)，原因有：
B+ 樹的非葉子節(jié)點(diǎn)不存放實(shí)際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲(chǔ)即存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點(diǎn)可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點(diǎn)的磁盤 I/O次數(shù)會(huì)更少。
B+ 樹有大量的冗余節(jié)點(diǎn)（所有非葉子節(jié)點(diǎn)都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，比如刪除根節(jié)點(diǎn)的時(shí)候，不會(huì)像 B 樹那樣會(huì)發(fā)生復(fù)雜的樹的變化；
B+ 樹葉子節(jié)點(diǎn)之間用鏈表連接了起來(lái)，有利于范圍查詢，而 B 樹要實(shí)現(xiàn)范圍查詢，因此只能通過樹的遍歷來(lái)完成范圍查詢，這會(huì)涉及多個(gè)節(jié)點(diǎn)的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。
