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)存訪(fǎng)問(wèn)的時(shí)間約為 50ns帘腹，而磁盤(pán)在 10ms 左右贰盗，相差了近 5 個(gè)數(shù)量級(jí)。這說(shuō)明程序大部分時(shí)間會(huì)阻塞在磁盤(pán) IO 上阳欲。
那么我們?nèi)绾翁岣叱绦蛐阅芏嬗繙p少磁盤(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è)位置被訪(fǎng)問(wèn)陆淀，那么將它附近的位置也會(huì)被訪(fǎng)問(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ū)間訪(fǎng)問(wèn)性，一般會(huì)對(duì) B+樹(shù)做一些優(yōu)化晶姊。如下圖帶順序訪(fǎng)問(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ū)間訪(fǎng)問(wèn)性欣鳖，可使用在范圍查詢(xún)等察皇，而 B-樹(shù)每個(gè)節(jié)點(diǎn)關(guān)鍵字和 data 在一起，則無(wú)法區(qū)間查找泽台。
根據(jù)空間局部性原理：如果一個(gè)存儲(chǔ)器的某個(gè)位置被訪(fǎng)問(wèn)什荣，那么將它附近的位置也會(huì)被訪(fǎng)問(wèn)。
B+樹(shù)可以很好的利用局部性原理怀酷，若我們?cè)L問(wèn)節(jié)點(diǎn)關(guān)鍵字為 50稻爬，則關(guān)鍵字為 55、60胰坟、62 的節(jié)點(diǎn)將來(lái)也可能被訪(fǎng)問(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ū)間訪(fǎng)問(wèn)是常見(jiàn)的一種情況界阁，而 B-樹(shù)并不支持區(qū)間訪(fǎng)問(wèn)，B+樹(shù)由于數(shù)據(jù)全部存儲(chǔ)在葉子節(jié)點(diǎn)胖喳，并且通過(guò)指針串在一起泡躯，這樣就很容易的進(jìn)行區(qū)間遍歷甚至全部遍歷，且每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確丽焊。
