B樹

????B 是 Balance（平衡）的縮寫。它是一種多路的平衡搜索樹。
????它跟普通的平衡二叉樹的不同是，B樹的每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)數(shù)據(jù)，而且每個(gè)節(jié)點(diǎn)不止有兩個(gè)子節(jié)點(diǎn)，最多可以有上千個(gè)子節(jié)點(diǎn)。
????B樹中每個(gè)節(jié)點(diǎn)都存放著索引和數(shù)據(jù)，數(shù)據(jù)遍布整個(gè)樹結(jié)構(gòu)，搜索可能在非葉子節(jié)點(diǎn)結(jié)束，最好的情況是O(1)。
? ? 一般一棵 B 樹的高度在 3 層左右，3 層就可滿足 百萬(wàn)級(jí)別的數(shù)據(jù)量

B+樹

????葉子節(jié)點(diǎn)保存了完整的索引和數(shù)據(jù)，而非葉子節(jié)點(diǎn)只保存索引值，因此它的查詢時(shí)間固定為 log(n).
????葉子節(jié)點(diǎn)中有指向下一個(gè)葉子節(jié)點(diǎn)的指針，葉子節(jié)點(diǎn)類似于一個(gè)單鏈表
????正因?yàn)槿~子節(jié)點(diǎn)保存了完整的數(shù)據(jù)以及有指針作為連接，B+樹可以增加了區(qū)間訪問(wèn)性，提高了范圍查詢，而B樹的范圍查詢相對(duì)較差
????B+樹更適合外部存儲(chǔ)。因?yàn)樗姆侨~子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只保存索引。

b+樹相比于b樹的查詢優(yōu)勢(shì)：

????b+樹的中間節(jié)點(diǎn)不保存數(shù)據(jù)，所以磁盤頁(yè)能容納更多節(jié)點(diǎn)元素，更“矮胖”；
????b+樹查詢必須查找到葉子節(jié)點(diǎn)，b樹只要匹配到即可不用管元素位置，因此b+樹查找更穩(wěn)定（并不慢）；
????對(duì)于范圍查找來(lái)說(shuō)，b+樹只需遍歷葉子節(jié)點(diǎn)鏈表即可，b樹卻需要重復(fù)地中序遍歷

為什么會(huì)出現(xiàn)B-樹這類數(shù)據(jù)結(jié)構(gòu)

????傳統(tǒng)用來(lái)搜索的平衡二叉樹有很多，如 AVL 樹，紅黑樹等。這些樹在一般情況下查詢性能非常好，但當(dāng)數(shù)據(jù)非常大的時(shí)候它們就無(wú)能為力了。原因當(dāng)數(shù)據(jù)量非常大時(shí)，內(nèi)存不夠用，大部分?jǐn)?shù)據(jù)只能存放在磁盤上，只有需要的數(shù)據(jù)才加載到內(nèi)存中。一般而言內(nèi)存訪問(wèn)的時(shí)間約為 50 ns，而磁盤在 10 ms 左右。速度相差了近 5 個(gè)數(shù)量級(jí)，磁盤讀取時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)了數(shù)據(jù)在內(nèi)存中比較的時(shí)間。這說(shuō)明程序大部分時(shí)間會(huì)阻塞在磁盤 IO 上。那么我們?nèi)绾翁岣叱绦蛐阅?？減少磁盤 IO 次數(shù)，像 AVL 樹，紅黑樹這類平衡二叉樹從設(shè)計(jì)上無(wú)法“迎合”磁盤。