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