問各位小可愛一個(gè)問題：MySQL 中 B 樹和 B+ 樹的區(qū)別？

B 樹和 B+ 樹是兩種數(shù)據(jù)結(jié)構(gòu)，構(gòu)建了磁盤中的高速索引結(jié)構(gòu)，因此不僅 MySQL 在用，MongoDB、Oracle 等也在用，基本屬于數(shù)據(jù)庫的標(biāo)配常規(guī)操作。

數(shù)據(jù)庫要經(jīng)常和磁盤與內(nèi)存打交道，為了提升性能，通常需要自己去構(gòu)建類似文件系統(tǒng)的結(jié)構(gòu)。今天主要來看看數(shù)據(jù)庫是如何利用磁盤空間設(shè)計(jì)索引的？

行存儲(chǔ)和列存儲(chǔ)

在學(xué)習(xí)構(gòu)建磁盤數(shù)據(jù)的索引結(jié)構(gòu)前，我們先通過行存儲(chǔ)、列存儲(chǔ)的學(xué)習(xí)來了解一些基本的存儲(chǔ)概念，幫助你建立一個(gè)基本的認(rèn)知。

目前數(shù)據(jù)庫存儲(chǔ)一張表格主要是行存儲(chǔ)（Row Storage）和列存儲(chǔ)（Column Storage）兩種存儲(chǔ)方式。行存儲(chǔ)將表格看作一個(gè)個(gè)記錄，每個(gè)記錄是一行。以包含訂單號(hào)、金額、下單時(shí)間 3 項(xiàng)的表為例，行存儲(chǔ)如下圖所示：

如上圖所示，在計(jì)算機(jī)中沒有真正的行的概念。行存儲(chǔ)本質(zhì)就是數(shù)據(jù)一個(gè)接著一個(gè)排列，一行數(shù)據(jù)后面馬上跟著另一行數(shù)據(jù)。如果訂單表很大，一個(gè)磁盤塊（Block）存不下，那么實(shí)際上就是每個(gè)塊存儲(chǔ)一定的行數(shù)。類似下圖這樣的結(jié)構(gòu)：

行存儲(chǔ)更新一行的操作，往往可以在一個(gè)塊（Block）中進(jìn)行。而查詢數(shù)據(jù)，聚合數(shù)據(jù)（比如求 4 月份的訂單數(shù)），往往需要跨塊（Block）。因此，行存儲(chǔ)優(yōu)點(diǎn)很明顯，更新快、單條記錄的數(shù)據(jù)集中，適合事務(wù)。但缺點(diǎn)也很明顯，查詢慢。

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

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

優(yōu)勢(shì)其實(shí)是在查詢和聚合運(yùn)算。

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

總結(jié)一下，行存儲(chǔ)、列存儲(chǔ)，最終都需要把數(shù)據(jù)存到磁盤塊。行存儲(chǔ)記錄一個(gè)接著一個(gè)，列存儲(chǔ)一列接著一列。前面我們提到行存儲(chǔ)適合更新及事務(wù)處理，更新好理解，因?yàn)橐粋€(gè)訂單可以在相同的 Block 中更新，那么為什么適合事務(wù)呢？

其實(shí)適合不適合是相對(duì)的，說行存儲(chǔ)適合是因?yàn)榱写鎯?chǔ)非常不適合事務(wù)。試想一下，你更新一個(gè)表的若干個(gè)數(shù)據(jù)，如果要在不同塊中更新，就可能產(chǎn)生多次更新操作。更新次數(shù)越多，保證一致性越麻煩。在單機(jī)環(huán)境我們可以上鎖，可以用阻塞隊(duì)列，可以用屏障……但是分布式場(chǎng)景中保證一致性（特別是強(qiáng)一致性）開銷很大。因此我們說行存儲(chǔ)適合事務(wù)，而列存儲(chǔ)不適合。

索引

接下來，我們?cè)谛写鎯?chǔ)、列存儲(chǔ)的基礎(chǔ)上，討論如何創(chuàng)建一些更高效的查詢結(jié)構(gòu)，這種結(jié)構(gòu)通常稱為索引。 我們經(jīng)常會(huì)遇到根據(jù)一個(gè)訂單編號(hào)查訂單的情況，比如說select * from order where id=1000000，這個(gè)時(shí)候就需要用到索引。而下面我將試圖通過二分查找的場(chǎng)景，和你一起討論 索引是什么。

在億級(jí)的訂單 ID 中查找某個(gè)編號(hào)，很容易想到二分查找。要理解二分查找，最需要關(guān)心的是算法的進(jìn)步機(jī)制。這個(gè)算法每進(jìn)行一次查找，都會(huì)讓問題的規(guī)模減半。當(dāng)然，也有場(chǎng)景限制，二分查找只能應(yīng)用在排序好的數(shù)據(jù)上。

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

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

所以按照這個(gè)思路，我們需要做的是將數(shù)據(jù)按照訂單 ID 排好序，查詢的時(shí)候就可以應(yīng)用二分查找了。而且按照二分查找的思路，也可以進(jìn)行范圍查找。比如要查找 [a,b] 之間的數(shù)據(jù)，可以先通過二分查找找到 a 的序號(hào)，再二分找到 b 的序號(hào)，兩個(gè)序號(hào)之間的數(shù)據(jù)就是目標(biāo)結(jié)果。

但是直接在原始數(shù)據(jù)上排序，我們可能會(huì)把數(shù)據(jù)弄亂，常規(guī)做法是設(shè)計(jì)冗余數(shù)據(jù)描述這種排序關(guān)系——這就是索引。下面我通過一個(gè)簡(jiǎn)單的例子告訴你為什么不能在原始數(shù)據(jù)上直接排序。

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

訂單 ID 列：10005 10001 ……

訂單金額列：99.00 100.00 ……

可以看到，訂單（10001）是第 2 個(gè)訂單。但是進(jìn)行排序后，訂單（10001）會(huì)到第 1 個(gè)位置。這樣會(huì)弄亂訂單 ID（10001）和 金額（100.00）對(duì)應(yīng)的關(guān)系。

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

以上這種專門用來進(jìn)行數(shù)據(jù)查詢的額外數(shù)據(jù)，就是索引。索引中的一個(gè)數(shù)據(jù)，也稱作索引條目。上面的索引條目一個(gè)接著一個(gè)，每個(gè)索引條目是 <訂單 ID, 序號(hào)> 的二元組。

如果你考慮是行存儲(chǔ)（比如 MySQL），那么依然可以生成上面的索引，訂單 ID 和序號(hào)（行號(hào)）關(guān)聯(lián)。如果有多個(gè)索引，就需要?jiǎng)?chuàng)造多個(gè)上面的數(shù)據(jù)結(jié)構(gòu)。如果有復(fù)合索引，比如 <訂單狀態(tài)、日期、序號(hào)> 作為一個(gè)索引條目，其實(shí)就是先按照訂單狀態(tài)，再按照日期排序的索引。

所以復(fù)合索引，無非就是多消耗一些空間，排序維度多一些。而且你可以看出復(fù)合索引和單列索引完全是獨(dú)立關(guān)系，所以我們可以認(rèn)為每創(chuàng)造一組索引，就創(chuàng)造了一份冗余的數(shù)據(jù)。也創(chuàng)造了一種特別的查詢方式。

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

二叉搜索樹

線性排序的數(shù)據(jù)雖然好用，但是插入新元素的時(shí)候性能太低。如果是內(nèi)存操作，插入一個(gè)元素，需要將這個(gè)元素之后的所有元素后移一位。但如果這個(gè)操作發(fā)生在磁盤中呢？這必然是災(zāi)難性的。因?yàn)榇疟P的速度比內(nèi)存慢至少 10-1000 倍，如果是機(jī)械硬盤可能慢幾十萬到百萬倍。

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

如下圖所示，二叉搜索樹的特點(diǎn)是一個(gè)節(jié)點(diǎn)的左子樹的所有節(jié)點(diǎn)都小于這個(gè)節(jié)點(diǎn)，右子樹的所有節(jié)點(diǎn)都大于這個(gè)節(jié)點(diǎn)。而且，因?yàn)樗饕龡l目較少，確實(shí)可以考慮在查詢的時(shí)候，先將足夠大的樹導(dǎo)入內(nèi)存，然后再進(jìn)行搜索。搜索的算法是遞歸的，與二分查找非常類似，每次計(jì)算可以將問題規(guī)模減半。當(dāng)然，具體有多少數(shù)據(jù)可以導(dǎo)入內(nèi)存，受實(shí)際可以使用的內(nèi)存數(shù)量的限制。

在上面的二叉搜索樹中，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)分成 Key 和 Value。Key 就是索引值，比如訂單 ID 創(chuàng)建索引，那么 Key 就是訂單 ID。值中至少需要序號(hào)（對(duì)行存儲(chǔ)也就是行號(hào)）。這樣，如果們想找 18 對(duì)應(yīng)的行，就可以先通過二叉搜索樹找到對(duì)應(yīng)的行號(hào)，然后再去對(duì)應(yīng)的行讀取數(shù)據(jù)。

二叉搜索樹是一個(gè)天生的二分查找結(jié)構(gòu)，每次查找都可以減少一半的問題規(guī)模。而且二叉搜索樹解決了插入新節(jié)點(diǎn)的問題，因?yàn)槎嫠阉鳂涫且粋€(gè)跳躍結(jié)構(gòu)，不必在內(nèi)存中連續(xù)排列。這樣在插入的時(shí)候，新節(jié)點(diǎn)可以放在任何位置，不會(huì)像線性結(jié)構(gòu)那樣插入一個(gè)元素，所有元素都需要向后排列。

那么回到本質(zhì)問題，在使用磁盤的時(shí)候，二叉搜索樹是不是一種合理的查詢結(jié)構(gòu)？

當(dāng)然還不算，因此還需要繼續(xù)優(yōu)化我們的算法。二叉搜索樹，在內(nèi)存中是一個(gè)高效的數(shù)據(jù)結(jié)構(gòu)。這是因?yàn)閮?nèi)存速度快，不僅可以隨機(jī)存取，還可以高頻操作。注意 CPU 緩存的穿透率只有 5% 左右，也就是 95% 的操作是在更快的 CPU 緩存中執(zhí)行的。而且即便穿透，內(nèi)存操作也是在納秒級(jí)別可以完成。

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

B 樹和 B+ 樹

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

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

一個(gè)更好的方案，就是繼續(xù)沿用樹狀結(jié)構(gòu)，利用好磁盤的分塊讓每個(gè)節(jié)點(diǎn)多一些數(shù)據(jù)，并且允許子節(jié)點(diǎn)也多一些，樹就會(huì)更矮。因?yàn)闃涞母叨葲Q定了搜索的次數(shù)。

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

B-Tree 是一種遞歸的搜索結(jié)構(gòu)，與二叉搜索樹非常類似。不同的是，B 樹中的父節(jié)點(diǎn)中的數(shù)據(jù)會(huì)對(duì)子樹進(jìn)行區(qū)段分割。比如上圖中節(jié)點(diǎn) 1 有 3 個(gè)子節(jié)點(diǎn)，并用數(shù)字 9,30 對(duì)子樹的區(qū)間進(jìn)行了劃分。

上圖中的 B 樹是一個(gè) 3-4 B 樹，3 指的是每個(gè)非葉子節(jié)點(diǎn)允許最大 3 個(gè)索引，4 指的是每個(gè)節(jié)點(diǎn)最多允許 4 個(gè)子節(jié)點(diǎn)，4 也指每個(gè)葉子節(jié)點(diǎn)可以存 4 個(gè)索引。上面只是一個(gè)例子，在實(shí)際的操作中，子節(jié)點(diǎn)有幾十個(gè)、甚至上百個(gè)索引也很常見，因?yàn)槲覀兿Ｍ麡渥儼?，好減少磁盤操作。

B 樹的每個(gè)節(jié)點(diǎn)是一個(gè)索引條目（例如：一個(gè) <訂單 ID，序號(hào)> 的組合），如果是行數(shù)據(jù)庫可以索引到一條存儲(chǔ)在磁盤上的記錄。

繼承 B 樹：B+ 樹

為了達(dá)到最高的效率，實(shí)戰(zhàn)中我們往往使用的是一種繼承于 B 樹設(shè)計(jì)的結(jié)構(gòu)，稱為 B+ 樹。B+ 樹只有葉子節(jié)點(diǎn)才映射數(shù)據(jù)，下圖中是對(duì) B 樹設(shè)計(jì)的一種改進(jìn)，節(jié)點(diǎn) 1 為冗余節(jié)點(diǎn)，它不存儲(chǔ)數(shù)據(jù)，只劃定子樹數(shù)據(jù)的范圍。你可以看到節(jié)點(diǎn) 1 的索引 Key：12 和 30，在節(jié)點(diǎn) 3 和 4 中也有一份。

樹的形成：插入

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

插入 3,6,9 過程很簡(jiǎn)單，都寫入一個(gè)節(jié)點(diǎn)即可，因?yàn)槿~子節(jié)點(diǎn)最多允許每個(gè) 3 個(gè)索引。

接下來我們插入 12，會(huì)發(fā)生一次過載，然后節(jié)點(diǎn)就需要拆分，這個(gè)時(shí)候按照 B+ 樹的設(shè)計(jì)會(huì)產(chǎn)生冗余節(jié)點(diǎn)。

然后插入 15 非常簡(jiǎn)單，直接加入即可：

接下來插入 19， 這個(gè)時(shí)候下圖中紅色部分發(fā)生過載：

因此需要拆分節(jié)點(diǎn)數(shù)據(jù)，我們從中間把紅色的節(jié)點(diǎn)拆開，15 作為冗余的索引寫入父節(jié)點(diǎn)，就形成下圖的情況：

接著插入 26， 寫入到對(duì)應(yīng)位置即可。

接下來，插入 8 到對(duì)應(yīng)位置即可。

然后我們插入 30，此時(shí)右邊節(jié)點(diǎn)發(fā)生過載：

解決完一次過載問題之后，因?yàn)?26 會(huì)浮上去，根節(jié)點(diǎn)又發(fā)生了過載：

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

在上述過程中，B+ 樹始終可以保持平衡狀態(tài)，而且所有葉子節(jié)點(diǎn)都在同一層級(jí)。更復(fù)雜的數(shù)學(xué)證明，我就不在這里講解了。

插入和刪除效率

B+ 樹有大量的冗余節(jié)點(diǎn)，比如刪除一個(gè)節(jié)點(diǎn)的時(shí)候，可以直接從葉子節(jié)點(diǎn)中刪除，甚至可以不動(dòng)非葉子節(jié)點(diǎn)。這樣刪除非常快。B 樹則不同，B 樹沒有冗余節(jié)點(diǎn)，刪除節(jié)點(diǎn)的時(shí)候非常復(fù)雜。比如刪除根節(jié)點(diǎn)中的數(shù)據(jù)，可能涉及復(fù)雜的樹的變形。

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

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

搜索：鏈表的作用

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

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

總結(jié)

這一講我們學(xué)習(xí)了在數(shù)據(jù)庫中如何利用文件系統(tǒng)造索引。無論是行存儲(chǔ)還是列存儲(chǔ)，構(gòu)造索引的過程都是類似的。索引有很多做法，除了 B+ 樹，還有 HashTable、倒排表等。如果是存儲(chǔ)海量數(shù)據(jù)的數(shù)據(jù)庫，我們的思考點(diǎn)需要放在 I/O 的效率上。如果把今天的知識(shí)放到分布式數(shù)據(jù)庫上，那除了需要節(jié)省磁盤讀寫還需要節(jié)省網(wǎng)絡(luò) I/O。

好了，現(xiàn)在回到文章的開頭：MySQL 中的 B 樹和 B+ 樹有什么區(qū)別？

【解析】B+ 樹繼承于 B 樹，都限定了節(jié)點(diǎn)中數(shù)據(jù)數(shù)目和子節(jié)點(diǎn)的數(shù)目。B 樹所有節(jié)點(diǎn)都可以映射數(shù)據(jù)，B+ 樹只有葉子節(jié)點(diǎn)可以映射數(shù)據(jù)。

單獨(dú)看這部分設(shè)計(jì)，看不出 B+ 樹的優(yōu)勢(shì)。為了只有葉子節(jié)點(diǎn)可以映射數(shù)據(jù)，B+ 樹創(chuàng)造了很多冗余的索引（所有非葉子節(jié)點(diǎn)都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，而且可以自動(dòng)平衡，因此 B+ 樹的所有葉子節(jié)點(diǎn)總是在一個(gè)層級(jí)上。所以 B+ 樹可以用一條鏈表串聯(lián)所有的葉子節(jié)點(diǎn)，也就是索引數(shù)據(jù)，這讓 B+ 樹的范圍查找和聚合運(yùn)算更快。