B-樹(shù)
定義：B-樹(shù)是一類(lèi)樹(shù)，包括 B-樹(shù)、B+樹(shù)、B* 樹(shù)等，是一棵自平衡的搜索樹(shù)，它類(lèi)似普通的平衡二叉樹(shù)，不同的一點(diǎn)是 B-樹(shù)允許每個(gè)節(jié)點(diǎn)有更多的子節(jié)點(diǎn)。B-樹(shù)是專(zhuān)門(mén)為外部存儲(chǔ)器設(shè)計(jì)的，如磁盤(pán)，它對(duì)于讀取和寫(xiě)入大塊數(shù)據(jù)有良好的性能，所以一般被用在文件系統(tǒng)及數(shù)據(jù)庫(kù)中。
為什么會(huì)出現(xiàn) B-樹(shù)這類(lèi)數(shù)據(jù)結(jié)構(gòu)？
傳統(tǒng)用來(lái)搜索的平衡二叉樹(shù)有很多，如 AVL 樹(shù)，紅黑樹(shù)等。這些樹(shù)在一般情況下查詢(xún)性能非常好，但當(dāng)數(shù)據(jù)非常大的時(shí)候它們就無(wú)能為力了。
原因是當(dāng)數(shù)據(jù)量非常大時(shí)，內(nèi)存不夠用，大部分?jǐn)?shù)據(jù)只能存放在磁盤(pán)上，只有需要的數(shù)據(jù)才加載到內(nèi)存中。一般而言?xún)?nèi)存訪問(wèn)的時(shí)間約為 50ns，而磁盤(pán)在 10ms 左右，相差了近 5 個(gè)數(shù)量級(jí)。這說(shuō)明程序大部分時(shí)間會(huì)阻塞在磁盤(pán) IO 上。
那么我們?nèi)绾翁岣叱绦蛐阅?？減少磁盤(pán) IO 次數(shù)。像 AVL 樹(shù)，紅黑樹(shù)這類(lèi)平衡二叉樹(shù)從設(shè)計(jì)上無(wú)法“迎合”磁盤(pán)。
平衡二叉樹(shù)是通過(guò)旋轉(zhuǎn)來(lái)保持平衡的，而旋轉(zhuǎn)是對(duì)整棵樹(shù)的操作，若部分加載到內(nèi)存中則無(wú)法完成旋轉(zhuǎn)操作。其次平衡二叉樹(shù)的高度相對(duì)較大為 log2n，這樣邏輯上很近的節(jié)點(diǎn)實(shí)際可能非常遠(yuǎn)，無(wú)法很好的利用磁盤(pán)預(yù)讀（局部性原理），所以這類(lèi)平衡二叉樹(shù)在數(shù)據(jù)庫(kù)和文件系統(tǒng)上的選擇就被 pass 了。
空間局部性原理：如果一個(gè)存儲(chǔ)器的某個(gè)位置被訪問(wèn)，那么將它附近的位置也會(huì)被訪問(wèn)。
從“迎合”磁盤(pán)的角度來(lái)看看 B-樹(shù)的設(shè)計(jì)。
索引的原理其實(shí)是不斷的縮小查找范圍，就如我們平時(shí)用字典查單詞一樣，先找首字母縮小范圍，再第二個(gè)字母等等。平衡二叉樹(shù)是每次將范圍分割為兩個(gè)區(qū)間。為了更快，B-樹(shù)每次將范圍分割為多個(gè)區(qū)間，區(qū)間越多，定位數(shù)據(jù)越快越精確。
那么如果節(jié)點(diǎn)為區(qū)間范圍，每個(gè)節(jié)點(diǎn)就較大了。所以新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)頁(yè)大小的空間（磁盤(pán)是按 block 分的，一般為 512 Byte。磁盤(pán) IO 一次讀取若干個(gè) block，我們稱(chēng)為一頁(yè)，具體大小和操作系統(tǒng)有關(guān)，一般為 4k，8k或 16k），計(jì)算機(jī)內(nèi)存分配是按頁(yè)對(duì)齊的，這樣就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)只需要一次 IO。
上圖是一棵簡(jiǎn)化的 B-樹(shù)，多叉的好處非常明顯，有效的降低了 B-樹(shù)的高度，為底數(shù)很大的 logn。一般一棵 B-樹(shù)的高度在 3 層左右。
B-樹(shù)的每個(gè)節(jié)點(diǎn)是 n 個(gè)有序的序列（a1, a2, a3, … , an），并將該節(jié)點(diǎn)的子節(jié)點(diǎn)分割成 n+1 個(gè)區(qū)間來(lái)進(jìn)行索引（X1< a1 < X2 < a2 < … < an < Xn+1）。
一個(gè) m 階的 B-樹(shù)滿(mǎn)足以下條件：
- 有 k 棵子樹(shù)的分支結(jié)點(diǎn)存在 k-1 個(gè)關(guān)鍵碼，關(guān)鍵碼按照遞增次序進(jìn)行排列；
- 根結(jié)點(diǎn)至少擁有兩顆子樹(shù)（存在子樹(shù)的情況下），至多擁有 m 棵子樹(shù)；
- 除了根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)至多擁有 m 棵子樹(shù)，其余每個(gè)分支結(jié)點(diǎn)至少擁有 m/2 棵子樹(shù)（即關(guān)鍵字?jǐn)?shù)量 n 需要滿(mǎn)足 ?m/2?-1 ≤ n ≤ m-1）；
- 所有的葉結(jié)點(diǎn)都在同一層；
B-樹(shù)的查找
我們來(lái)看看 B-樹(shù)的查找，假設(shè)每個(gè)節(jié)點(diǎn)有 n 個(gè) 關(guān)鍵字，被分割為 n+1 個(gè)區(qū)間，注意，每個(gè) 關(guān)鍵字緊跟著 data 域，這說(shuō)明 B-樹(shù)的關(guān)鍵字和 data 是聚合在一起的。一般而言，根節(jié)點(diǎn)在內(nèi)存中，B-樹(shù)以每個(gè)節(jié)點(diǎn)為一次磁盤(pán) IO，比如上圖中，若搜索關(guān)鍵字為 25 節(jié)點(diǎn)的 data，首先在根節(jié)點(diǎn)進(jìn)行二分查找（因?yàn)?keys 有序，二分最快），判斷關(guān)鍵字 25 小于關(guān)鍵字 50，所以定位到最左側(cè)的節(jié)點(diǎn)，此時(shí)進(jìn)行一次磁盤(pán) IO，將該節(jié)點(diǎn)從磁盤(pán)讀入內(nèi)存，接著繼續(xù)進(jìn)行上述過(guò)程，直到找到該關(guān)鍵字為止。
一個(gè)酷炫的網(wǎng)頁(yè)，可以自己插入刪除節(jié)點(diǎn)，觀察 B-樹(shù)的變化情況：
https://www.cs.usfca.edu/~galles/visualization/BTree.html
B-樹(shù)的插入規(guī)則
新結(jié)點(diǎn)一般插入在最底層，通過(guò)搜索找到對(duì)應(yīng)的結(jié)點(diǎn)進(jìn)行插入，根據(jù)即將插入的結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量又分為下面幾種情況：
- 如果該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)沒(méi)有到達(dá) m-1 個(gè)，那么直接插入即可；
- 如果該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)已到達(dá)了 m-1 個(gè)，無(wú)法滿(mǎn)足 B-樹(shù)的性質(zhì)，需要將其進(jìn)行分裂。分裂的規(guī)則是該結(jié)點(diǎn)分成兩半，將中間的關(guān)鍵字提升到父親結(jié)點(diǎn)中，這又可能導(dǎo)致父節(jié)點(diǎn)的分裂，那就繼續(xù)向上回溯（甚至是要對(duì)根結(jié)點(diǎn)進(jìn)行分裂，那么整棵樹(shù)都加了一層）。
過(guò)程如下：
B-樹(shù)的刪除規(guī)則
先通過(guò)搜索找到相應(yīng)的值，存在則進(jìn)行刪除：
- 如果該結(jié)點(diǎn)擁有關(guān)鍵字?jǐn)?shù)量仍然大于或等于 ?m/2?-1，則不做任何處理；
- 如果該結(jié)點(diǎn)在刪除關(guān)鍵字以后，關(guān)鍵字?jǐn)?shù)量小于 ?m/2?-1，則需要向兄弟結(jié)點(diǎn)借關(guān)鍵字，這又分為兄弟結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量是否足夠的情況：
- 如果兄弟結(jié)點(diǎn)借出一個(gè)關(guān)鍵字仍滿(mǎn)足 B-樹(shù)性質(zhì)，則將該節(jié)點(diǎn)與兄弟節(jié)點(diǎn)之間夾的父親結(jié)點(diǎn)關(guān)鍵字下移，兄弟結(jié)點(diǎn)的關(guān)鍵字上移；
- 如果兄弟結(jié)點(diǎn)的關(guān)鍵字在借出以后無(wú)法滿(mǎn)足情況，那么我們可以將該結(jié)點(diǎn)合并到兄弟結(jié)點(diǎn)中，合并之后的子結(jié)點(diǎn)數(shù)量少了一個(gè)，則需要將父親結(jié)點(diǎn)的關(guān)鍵字下放，如果父親結(jié)點(diǎn)不滿(mǎn)足性質(zhì)，繼續(xù)向上回溯；
過(guò)程如下：
B+樹(shù)
B+樹(shù)是 B-樹(shù)的變種，它與 B-樹(shù)的不同之處在于：
- 在 B+樹(shù)中，關(guān)鍵字的副本存儲(chǔ)在內(nèi)部節(jié)點(diǎn)，真正的關(guān)鍵字和 data 存儲(chǔ)在葉子節(jié)點(diǎn)上（所有的 data 都在最后一層）。
- n 個(gè)關(guān)鍵字的節(jié)點(diǎn)指針域?yàn)?n 而不是 n+1。
每個(gè)節(jié)點(diǎn)關(guān)鍵字的數(shù)量范圍依然是 ?m/2?-1 ~ m-1，順序遞增。
因?yàn)閮?nèi)節(jié)點(diǎn)并不存儲(chǔ) data，所以一般 B+樹(shù)的葉節(jié)點(diǎn)和內(nèi)節(jié)點(diǎn)大小不同。為了增加區(qū)間訪問(wèn)性，一般會(huì)對(duì) B+樹(shù)做一些優(yōu)化。如下圖帶順序訪問(wèn)的 B+樹(shù)：
B+樹(shù)的插入刪除類(lèi)似于 B-樹(shù)。
B-樹(shù)和 B+樹(shù)的區(qū)別
1、B+樹(shù)內(nèi)節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，所有 data 存儲(chǔ)在葉節(jié)點(diǎn)導(dǎo)致查詢(xún)時(shí)間復(fù)雜度固定為 logn。而 B-樹(shù)查詢(xún)時(shí)間復(fù)雜度不固定，與關(guān)鍵字在樹(shù)中的位置有關(guān)，最好為 O(1)。
如下所示 B-樹(shù)/B+樹(shù)查詢(xún)關(guān)鍵字為 50 的 data。
B-樹(shù)
關(guān)鍵字為 50 的節(jié)點(diǎn)就在第一層，B-樹(shù)只需要一次磁盤(pán) IO 即可完成查找。
B+樹(shù)
由于 B+樹(shù)所有的 data 域都在根節(jié)點(diǎn)，所以查詢(xún)關(guān)鍵字為 50 的節(jié)點(diǎn)必須從根節(jié)點(diǎn)索引到葉節(jié)點(diǎn)，時(shí)間復(fù)雜度固定為 O(logn)。
2、B+樹(shù)葉節(jié)點(diǎn)兩兩相連可大大增加區(qū)間訪問(wèn)性，可使用在范圍查詢(xún)等，而 B-樹(shù)每個(gè)節(jié)點(diǎn)關(guān)鍵字和 data 在一起，則無(wú)法區(qū)間查找。
根據(jù)空間局部性原理：如果一個(gè)存儲(chǔ)器的某個(gè)位置被訪問(wèn)，那么將它附近的位置也會(huì)被訪問(wèn)。
B+樹(shù)可以很好的利用局部性原理，若我們?cè)L問(wèn)節(jié)點(diǎn)關(guān)鍵字為 50，則關(guān)鍵字為 55、60、62 的節(jié)點(diǎn)將來(lái)也可能被訪問(wèn)，我們可以利用磁盤(pán)預(yù)讀原理提前將這些數(shù)據(jù)讀入內(nèi)存，減少了磁盤(pán) IO 的次數(shù)。
當(dāng)然 B+樹(shù)也能夠很好的完成范圍查詢(xún)。比如查詢(xún)關(guān)鍵字在 50~70 之間的節(jié)點(diǎn)。
3、B+樹(shù)更適合外部存儲(chǔ)。由于內(nèi)節(jié)點(diǎn)無(wú) data 域，每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確。
由于 B-樹(shù)節(jié)點(diǎn)內(nèi)部每個(gè)關(guān)鍵字都帶著 data 域，而 B+樹(shù)節(jié)點(diǎn)只存儲(chǔ) key 的副本，真實(shí)的關(guān)鍵字和 data 域都在葉子節(jié)點(diǎn)存儲(chǔ)。前面說(shuō)過(guò)磁盤(pán)是分 block 的，一次磁盤(pán) IO 會(huì)讀取若干個(gè) block，具體和操作系統(tǒng)有關(guān)，那么由于磁盤(pán) IO 數(shù)據(jù)大小是固定的，這就意味著B+樹(shù)單次磁盤(pán) IO 的信息量大于 B-樹(shù)，從這點(diǎn)來(lái)看 B+樹(shù)相對(duì) B-樹(shù)磁盤(pán) IO 次數(shù)少。
為什么 MongoDB 索引選擇 B-樹(shù)，而 Mysql（InnoDB 引擎）索引選擇 B+樹(shù)
MongoDB 是文檔型的數(shù)據(jù)庫(kù)，是一種 NoSQL，一般使用 XML 或 Json 格式來(lái)保存數(shù)據(jù)，歸屬于聚合型數(shù)據(jù)庫(kù)。被設(shè)計(jì)用在數(shù)據(jù)模型簡(jiǎn)單，性能要求高的場(chǎng)合。MongoDB 是聚合型數(shù)據(jù)庫(kù)（通常就是鍵值對(duì)），而 B-樹(shù)恰好關(guān)鍵字和 data 域聚合在一起。
Mysql 是一種關(guān)系型數(shù)據(jù)庫(kù)，區(qū)間訪問(wèn)是常見(jiàn)的一種情況，而 B-樹(shù)并不支持區(qū)間訪問(wèn)，B+樹(shù)由于數(shù)據(jù)全部存儲(chǔ)在葉子節(jié)點(diǎn)，并且通過(guò)指針串在一起，這樣就很容易的進(jìn)行區(qū)間遍歷甚至全部遍歷，且每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確。
