問各位小可愛一個問題：MySQL 中 B 樹和 B+ 樹的區別？

B 樹和 B+ 樹是兩種數據結構，構建了磁盤中的高速索引結構，因此不僅 MySQL 在用，MongoDB、Oracle 等也在用，基本屬于數據庫的標配常規操作。

數據庫要經常和磁盤與內存打交道，為了提升性能，通常需要自己去構建類似文件系統的結構。今天主要來看看數據庫是如何利用磁盤空間設計索引的？

行存儲和列存儲

在學習構建磁盤數據的索引結構前，我們先通過行存儲、列存儲的學習來了解一些基本的存儲概念，幫助你建立一個基本的認知。

目前數據庫存儲一張表格主要是行存儲（Row Storage）和列存儲（Column Storage）兩種存儲方式。行存儲將表格看作一個個記錄，每個記錄是一行。以包含訂單號、金額、下單時間 3 項的表為例，行存儲如下圖所示：

如上圖所示，在計算機中沒有真正的行的概念。行存儲本質就是數據一個接著一個排列，一行數據后面馬上跟著另一行數據。如果訂單表很大，一個磁盤塊（Block）存不下，那么實際上就是每個塊存儲一定的行數。類似下圖這樣的結構：

行存儲更新一行的操作，往往可以在一個塊（Block）中進行。而查詢數據，聚合數據（比如求 4 月份的訂單數），往往需要跨塊（Block）。因此，行存儲優點很明顯，更新快、單條記錄的數據集中，適合事務。但缺點也很明顯，查詢慢。

還有一種表格的存儲方式是列存儲（Column Storage），列存儲中數據是一列一列存的。還以訂單表為例，如下圖所示：

你可以看到訂單號在一起、姓名在一起、時間在一起、金額也在一起——每個列的數據都聚集在一起。乍一看這樣的結構很低效，比如說你想取出第一條訂單，需要取第 1 列的第 1 個數據1001，然后取第 2 列的第 1 個數據小明，以此類推，需要 4 次磁盤讀取。特別是更新某一條記錄的時候，需要更新多處，速度很慢。那么列存儲優勢在哪里呢？

優勢其實是在查詢和聚合運算。

在列存儲中同一列數據總是存放在一起，比如要查找某個時間段，很有可能在一個塊中就可以找到，因為時間是集中存儲的。假設磁盤塊的大小是 4KB，一條記錄是 100 字節， 那么 4KB 可以存 40 條記錄；但是存儲時間戳只需要一個 32 位整數，4KB 可以存儲 1000 個時間。更關鍵的是，我們可以把一片連續的硬盤空間通過 DMA 技術直接映射到內存，這樣就大大減少了搜索需要的時間。所以有時候在行存儲需要幾分鐘的搜索操作，在列存儲中只需幾秒鐘就可以完成。

總結一下，行存儲、列存儲，最終都需要把數據存到磁盤塊。行存儲記錄一個接著一個，列存儲一列接著一列。前面我們提到行存儲適合更新及事務處理，更新好理解，因為一個訂單可以在相同的 Block 中更新，那么為什么適合事務呢？

其實適合不適合是相對的，說行存儲適合是因為列存儲非常不適合事務。試想一下，你更新一個表的若干個數據，如果要在不同塊中更新，就可能產生多次更新操作。更新次數越多，保證一致性越麻煩。在單機環境我們可以上鎖，可以用阻塞隊列，可以用屏障……但是分布式場景中保證一致性（特別是強一致性）開銷很大。因此我們說行存儲適合事務，而列存儲不適合。

索引

接下來，我們在行存儲、列存儲的基礎上，討論如何創建一些更高效的查詢結構，這種結構通常稱為索引。 我們經常會遇到根據一個訂單編號查訂單的情況，比如說select * from order where id=1000000，這個時候就需要用到索引。而下面我將試圖通過二分查找的場景，和你一起討論 索引是什么。

在億級的訂單 ID 中查找某個編號，很容易想到二分查找。要理解二分查找，最需要關心的是算法的進步機制。這個算法每進行一次查找，都會讓問題的規模減半。當然，也有場景限制，二分查找只能應用在排序好的數據上。

比如我們要在下面排序好的數組中查找 3：1,3,5,8,11,12,15,19,21,25

數組中一共有 10 個元素，因此我們第一次查找從數組正中間的元素找起。如果數組正中間有兩個元素，就取左邊的那個——對于這個例子是 11。我們比較 11 和 3 的值，因為 11 大于 3，因此可以排除包括 11 在內的所有 11 右邊的元素。相當于我們通過一次運算將數據的規模減半。假設我們有 240 （1T 數據）個元素需要查詢（規模已經相當大了，萬億級別），用二分查找只需要 40 次運算。

所以按照這個思路，我們需要做的是將數據按照訂單 ID 排好序，查詢的時候就可以應用二分查找了。而且按照二分查找的思路，也可以進行范圍查找。比如要查找 [a,b] 之間的數據，可以先通過二分查找找到 a 的序號，再二分找到 b 的序號，兩個序號之間的數據就是目標結果。

但是直接在原始數據上排序，我們可能會把數據弄亂，常規做法是設計冗余數據描述這種排序關系——這就是索引。下面我通過一個簡單的例子告訴你為什么不能在原始數據上直接排序。

假設我們有一個訂單表，里面有訂單 ID 和金額。使用列存儲做演示如下：

訂單 ID 列：10005 10001 ……

訂單金額列：99.00 100.00 ……

可以看到，訂單（10001）是第 2 個訂單。但是進行排序后，訂單（10001）會到第 1 個位置。這樣會弄亂訂單 ID（10001）和 金額（100.00）對應的關系。

因此我們必須用空間換時間，額外將訂單列拷貝一份排序：10001，2，10005， 1

以上這種專門用來進行數據查詢的額外數據，就是索引。索引中的一個數據，也稱作索引條目。上面的索引條目一個接著一個，每個索引條目是 <訂單 ID, 序號> 的二元組。

如果你考慮是行存儲（比如 MySQL），那么依然可以生成上面的索引，訂單 ID 和序號（行號）關聯。如果有多個索引，就需要創造多個上面的數據結構。如果有復合索引，比如 <訂單狀態、日期、序號> 作為一個索引條目，其實就是先按照訂單狀態，再按照日期排序的索引。

所以復合索引，無非就是多消耗一些空間，排序維度多一些。而且你可以看出復合索引和單列索引完全是獨立關系，所以我們可以認為每創造一組索引，就創造了一份冗余的數據。也創造了一種特別的查詢方式。

接下來，請分析一個非常核心的問題：上面的索引是一個連續的、從小到大的索引，那么應不應該使用這種從小到大排序的索引呢？例如，我們需要查詢訂單，就事先創建另一個根據訂單 ID 從小到大排序的索引，當用戶查找某個訂單的時候，無論是行存儲、還是列存儲，我們就用二分查找查詢對應的索引條目。這種方式，我們姑且稱為線性排序索引——看似很不錯的一個方式，但是并不是非常好的一種做法。

二叉搜索樹

線性排序的數據雖然好用，但是插入新元素的時候性能太低。如果是內存操作，插入一個元素，需要將這個元素之后的所有元素后移一位。但如果這個操作發生在磁盤中呢？這必然是災難性的。因為磁盤的速度比內存慢至少 10-1000 倍，如果是機械硬盤可能慢幾十萬到百萬倍。

所以我們不能用一種線性結構將磁盤排序。那么樹呢？比如二叉搜索樹（Binary Serach Tree）行不行呢？利用磁盤的空間形成一個二叉搜索樹，例如將訂單 ID 作為二叉搜索樹的 Key。

如下圖所示，二叉搜索樹的特點是一個節點的左子樹的所有節點都小于這個節點，右子樹的所有節點都大于這個節點。而且，因為索引條目較少，確實可以考慮在查詢的時候，先將足夠大的樹導入內存，然后再進行搜索。搜索的算法是遞歸的，與二分查找非常類似，每次計算可以將問題規模減半。當然，具體有多少數據可以導入內存，受實際可以使用的內存數量的限制。

在上面的二叉搜索樹中，每個節點的數據分成 Key 和 Value。Key 就是索引值，比如訂單 ID 創建索引，那么 Key 就是訂單 ID。值中至少需要序號（對行存儲也就是行號）。這樣，如果們想找 18 對應的行，就可以先通過二叉搜索樹找到對應的行號，然后再去對應的行讀取數據。

二叉搜索樹是一個天生的二分查找結構，每次查找都可以減少一半的問題規模。而且二叉搜索樹解決了插入新節點的問題，因為二叉搜索樹是一個跳躍結構，不必在內存中連續排列。這樣在插入的時候，新節點可以放在任何位置，不會像線性結構那樣插入一個元素，所有元素都需要向后排列。

那么回到本質問題，在使用磁盤的時候，二叉搜索樹是不是一種合理的查詢結構？

當然還不算，因此還需要繼續優化我們的算法。二叉搜索樹，在內存中是一個高效的數據結構。這是因為內存速度快，不僅可以隨機存取，還可以高頻操作。注意 CPU 緩存的穿透率只有 5% 左右，也就是 95% 的操作是在更快的 CPU 緩存中執行的。而且即便穿透，內存操作也是在納秒級別可以完成。

但是，這個邏輯在磁盤中是不存在的，磁盤的速度慢太多了。我們可以嘗試把盡可能多的二叉搜索樹讀入磁盤，但是如果數據量大，只能讀入一部分呢？因此我們還需要繼續改進算法。

B 樹和 B+ 樹

二叉搜索樹解決了連續結構插入新元素開銷很大的問題，同時又保持著天然的二分結構。但是，當需要索引的數據量很大，無法在一個磁盤 Block 中存下整棵二叉搜索樹的時候。每一次遞歸向下的搜索，實際都是讀取不同的磁盤塊。這個時候二叉搜索樹的開銷很大。

試想一個一萬億條訂單的表，進行 40 次查找找到答案，在內存中不是問題，要考慮到 CPU 緩存有 90% 以上的命中率（當然前提是內存足夠大）。通常情況下我們沒有這么大的內存空間，如果 40 次查找發生在磁盤上，也是非常耗時的。那么有沒有更好的方案呢？

一個更好的方案，就是繼續沿用樹狀結構，利用好磁盤的分塊讓每個節點多一些數據，并且允許子節點也多一些，樹就會更矮。因為樹的高度決定了搜索的次數。

上圖中我們構造的樹被稱為 B 樹（B-Tree），開頭說過，B 這個字母具體是哪個單詞或者人名的縮寫，至今有爭議，具體你可以查查資料。

B-Tree 是一種遞歸的搜索結構，與二叉搜索樹非常類似。不同的是，B 樹中的父節點中的數據會對子樹進行區段分割。比如上圖中節點 1 有 3 個子節點，并用數字 9,30 對子樹的區間進行了劃分。

上圖中的 B 樹是一個 3-4 B 樹，3 指的是每個非葉子節點允許最大 3 個索引，4 指的是每個節點最多允許 4 個子節點，4 也指每個葉子節點可以存 4 個索引。上面只是一個例子，在實際的操作中，子節點有幾十個、甚至上百個索引也很常見，因為我們希望樹變矮，好減少磁盤操作。

B 樹的每個節點是一個索引條目（例如：一個 <訂單 ID，序號> 的組合），如果是行數據庫可以索引到一條存儲在磁盤上的記錄。

繼承 B 樹：B+ 樹

為了達到最高的效率，實戰中我們往往使用的是一種繼承于 B 樹設計的結構，稱為 B+ 樹。B+ 樹只有葉子節點才映射數據，下圖中是對 B 樹設計的一種改進，節點 1 為冗余節點，它不存儲數據，只劃定子樹數據的范圍。你可以看到節點 1 的索引 Key：12 和 30，在節點 3 和 4 中也有一份。

樹的形成：插入

下面我以一棵 2-3 B+ 樹來演示 B+ 樹的插入過程。2 指的是 B+ 樹每個非葉子節點允許 2 個數據，葉子節點最多允許 3 個索引，每個節點允許最多 3 個子節點。我們要在 2-3 B+ 樹中依次插入 3,6,9,12,19,15,26,8,30。

插入 3,6,9 過程很簡單，都寫入一個節點即可，因為葉子節點最多允許每個 3 個索引。

接下來我們插入 12，會發生一次過載，然后節點就需要拆分，這個時候按照 B+ 樹的設計會產生冗余節點。

然后插入 15 非常簡單，直接加入即可：

接下來插入 19， 這個時候下圖中紅色部分發生過載：

因此需要拆分節點數據，我們從中間把紅色的節點拆開，15 作為冗余的索引寫入父節點，就形成下圖的情況：

接著插入 26， 寫入到對應位置即可。

接下來，插入 8 到對應位置即可。

然后我們插入 30，此時右邊節點發生過載：

解決完一次過載問題之后，因為 26 會浮上去，根節點又發生了過載：

再次解決過載，拆分紅色部分，得到最后結果：

在上述過程中，B+ 樹始終可以保持平衡狀態，而且所有葉子節點都在同一層級。更復雜的數學證明，我就不在這里講解了。

插入和刪除效率

B+ 樹有大量的冗余節點，比如刪除一個節點的時候，可以直接從葉子節點中刪除，甚至可以不動非葉子節點。這樣刪除非常快。B 樹則不同，B 樹沒有冗余節點，刪除節點的時候非常復雜。比如刪除根節點中的數據，可能涉及復雜的樹的變形。

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

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

搜索：鏈表的作用

B 樹和 B+ 樹搜索原理基本一致。先從根節點查找，然后對比目標數據的范圍，最后遞歸的進入子節點查找。

你可能會注意到，B+ 樹所有葉子節點間還有一個鏈表進行連接。這種設計對范圍查找非常有幫助，比如說我們想知道 1 月 20 日和 1 月 22 日之間的訂單，這個時候可以先查找到 1 月 20 日所在的葉子節點，然后利用鏈表向右遍歷，直到找到 1 月22 日的節點。這樣我們就進一步節省搜索需要的時間。

總結

這一講我們學習了在數據庫中如何利用文件系統造索引。無論是行存儲還是列存儲，構造索引的過程都是類似的。索引有很多做法，除了 B+ 樹，還有 HashTable、倒排表等。如果是存儲海量數據的數據庫，我們的思考點需要放在 I/O 的效率上。如果把今天的知識放到分布式數據庫上，那除了需要節省磁盤讀寫還需要節省網絡 I/O。

好了，現在回到文章的開頭：MySQL 中的 B 樹和 B+ 樹有什么區別？

【解析】B+ 樹繼承于 B 樹，都限定了節點中數據數目和子節點的數目。B 樹所有節點都可以映射數據，B+ 樹只有葉子節點可以映射數據。

單獨看這部分設計，看不出 B+ 樹的優勢。為了只有葉子節點可以映射數據，B+ 樹創造了很多冗余的索引（所有非葉子節點都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，而且可以自動平衡，因此 B+ 樹的所有葉子節點總是在一個層級上。所以 B+ 樹可以用一條鏈表串聯所有的葉子節點，也就是索引數據，這讓 B+ 樹的范圍查找和聚合運算更快。