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 層就可滿足 百萬級別的數(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ū)間訪問性撩笆，提高了范圍查詢，而B樹的范圍查詢相對較差
????B+樹更適合外部存儲(chǔ)缸浦。因?yàn)樗姆侨~子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)夕冲，只保存索引。
b+樹相比于b樹的查詢優(yōu)勢：
????b+樹的中間節(jié)點(diǎn)不保存數(shù)據(jù)裂逐，所以磁盤頁能容納更多節(jié)點(diǎn)元素歹鱼，更“矮胖”；
????b+樹查詢必須查找到葉子節(jié)點(diǎn)卜高，b樹只要匹配到即可不用管元素位置弥姻，因此b+樹查找更穩(wěn)定（并不慢）；
????對于范圍查找來說掺涛，b+樹只需遍歷葉子節(jié)點(diǎn)鏈表即可庭敦，b樹卻需要重復(fù)地中序遍歷
為什么會(huì)出現(xiàn)B-樹這類數(shù)據(jù)結(jié)構(gòu)
????傳統(tǒng)用來搜索的平衡二叉樹有很多，如 AVL 樹鸽照，紅黑樹等螺捐。這些樹在一般情況下查詢性能非常好，但當(dāng)數(shù)據(jù)非常大的時(shí)候它們就無能為力了。原因當(dāng)數(shù)據(jù)量非常大時(shí)定血，內(nèi)存不夠用赔癌，大部分?jǐn)?shù)據(jù)只能存放在磁盤上，只有需要的數(shù)據(jù)才加載到內(nèi)存中澜沟。一般而言內(nèi)存訪問的時(shí)間約為 50 ns灾票，而磁盤在 10 ms 左右收夸。速度相差了近 5 個(gè)數(shù)量級湾碎，磁盤讀取時(shí)間遠(yuǎn)遠(yuǎn)超過了數(shù)據(jù)在內(nèi)存中比較的時(shí)間面哼。這說明程序大部分時(shí)間會(huì)阻塞在磁盤 IO 上腊徙。那么我們?nèi)绾翁岣叱绦蛐阅埽繙p少磁盤 IO 次數(shù)庶香，像 AVL 樹丑慎，紅黑樹這類平衡二叉樹從設(shè)計(jì)上無法“迎合”磁盤裹唆。
