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