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