B 樹
通常我們所說的 B樹 或 B-樹，其實指的是一種樹兵怯，這里我將其稱為 B樹彩匕。
一顆 M 階的 B樹具有以下特點：
1）樹的根或者是一片葉子，或者其兒子數(shù)在 2 和 M 之間媒区；
2）除根外驼仪，所有非樹葉節(jié)點的兒子數(shù)在 ?M/2? 和 M 之間；
3）所有的樹葉都在相同的深度上袜漩。
B樹的深度最多是:?log?M/2? N?绪爸。這個公式表明 B樹 的高度可以較小。
B樹是為了磁盤或其它存儲設(shè)備而設(shè)計的一種多叉平衡查找樹宙攻，在降低磁盤I/0操作方面性能較好奠货，許多數(shù)據(jù)庫系統(tǒng)一般使用B樹或者B樹的各種變形結(jié)構(gòu)。
B樹 有多種實現(xiàn)方式座掘，這里給出網(wǎng)上常見的一種：
特點如下：1）所有鍵值分布在整顆樹中递惋；2）任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；3）搜索有可能在非葉子結(jié)點結(jié)束溢陪；4）在關(guān)鍵字全集內(nèi)做一次查找,性能逼近二分查找丹墨。
要注意的是《數(shù)據(jù)結(jié)構(gòu)與算法》一書中的 B樹 與這棵樹有所區(qū)別，它更像下面的 B+ 樹嬉愧，但其樹葉之間沒有鏈指針贩挣。
B+ 樹
1）B+樹 和 B樹 的區(qū)別主要在于 B+樹 的非葉節(jié)點并無指向關(guān)鍵字具體信息的指針，所以 B+樹 的節(jié)點大小相對于 B樹 就會小一些，如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中王财，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多卵迂，一次性讀入內(nèi)存中的關(guān)鍵字也就越多，相對來說IO讀寫次數(shù)也就降低了绒净。正因為這個原因见咒，B+樹 的搜索必須到葉節(jié)點，那里才有指向關(guān)鍵字信息的指針挂疆，而 B樹 的搜索則可能在非葉節(jié)點結(jié)束改览，因為其非葉節(jié)點有指向關(guān)鍵字信息的指針。
2）此外缤言，由于非葉點并不是最終指向文件內(nèi)容的結(jié)點宝当，而只是葉子結(jié)點中關(guān)鍵字的索引，所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路胆萧。所有關(guān)鍵字查詢的路徑長度相同庆揩，導(dǎo)致每一個數(shù)據(jù)的查詢效率相當(dāng)。
3）B+樹只要遍歷葉子節(jié)點就可以實現(xiàn)整棵樹的遍歷跌穗，支持基于范圍的查詢订晌，而B樹不支持這樣的操作（或者說效率太低）。
通過以上介紹蚌吸，大致將B樹锈拨，B+樹總結(jié)如下：1）B樹：有序數(shù)組+平衡多叉樹；2）B+樹：有序數(shù)組鏈表+平衡多叉樹.無論是B樹羹唠，還是B+樹推励，由于根或者樹的上面幾層被反復(fù)查詢，所以這幾塊可以存在內(nèi)存中肉迫，換言之验辞，B樹、B+樹的根結(jié)點和部分頂層數(shù)據(jù)在內(nèi)存中喊衫，大部分下層數(shù)據(jù)在磁盤上跌造。
紅黑樹等數(shù)據(jù)結(jié)構(gòu)也可以用來實現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)普遍采用B/B+Tree作為索引結(jié)構(gòu)族购，一般來說壳贪，索引本身也很大，不可能全部存儲在內(nèi)存中寝杖，因此索引往往以索引文件的形式存儲的磁盤上违施。這樣的話，索引查找過程中就要產(chǎn)生磁盤I/O消耗瑟幕，相對于內(nèi)存存取磕蒲，I/O存取的消耗要高幾個數(shù)量級留潦，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說辣往，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)兔院。一般來說，B/B+樹的出度很大站削，所以樹的深度就會比較小坊萝。而紅黑樹就會深很多。
RB 樹
RB樹與AVL樹類似许起，也是一種平衡二叉查找樹十偶，廣泛應(yīng)用與 STL（set，map）园细，Linux的進(jìn)程調(diào)度（管理進(jìn)程控制塊）惦积，epoll在內(nèi)核中的實現(xiàn)（管理事件塊），nginx中（管理timer）珊肃，對 RB樹 的操作在最壞情形下花費 O(logN)荣刑。
紅黑樹的特性:
（1）每個節(jié)點或者是黑色馅笙，或者是紅色伦乔；（2）根節(jié)點是黑色；（3）如果一個節(jié)點是紅色的董习，則它的子節(jié)點必須是黑色的烈和；（4）從一個節(jié)點到NULL節(jié)點的任意路徑上包含相同數(shù)目的黑節(jié)點（確保沒有一條路徑會比其他路徑長出倆倍。因而皿淋，紅黑樹是相對是接近平衡的二叉樹）招刹；
（5）NULL 節(jié)點是黑色的。
紅黑樹示意圖：
著色法則的一個推論是窝趣，紅黑樹的高度最多是 2log(N + 1)疯暑。經(jīng)驗指出，平均紅黑樹大約和平均AVL樹一樣深哑舒，從而查找時間一般接近最優(yōu)妇拯，紅黑樹的優(yōu)點是執(zhí)行插入所需要的開銷相對于AVL較低，再有就是實踐中發(fā)生的旋轉(zhuǎn)相對較小洗鸵。但是越锈，紅黑樹的具體實現(xiàn)是復(fù)雜的，不僅因為有大量可能的旋轉(zhuǎn)膘滨，而且還因為一些子樹可能是空的甘凭，以及處理根的特殊情況（尤其是根沒有父節(jié)點）。
紅黑樹的 Insert 操作有兩種做法：
1）自底向上（插入的樹葉涂紅色）
2）自頂向下（兩個兒子都是紅色的翻轉(zhuǎn)顏色）
兩種方法都會涉及單旋轉(zhuǎn)與雙旋轉(zhuǎn)的操作火邓，類似AVL樹丹弱，但注意還要變換顏色德撬。
Delete操作可用自底向上，也可自頂向下蹈矮。
AVL 樹和紅黑樹的比較：1）如果插入一個node引起了樹的不平衡砰逻，AVL和RB-Tree都是最多只需要2次旋轉(zhuǎn)操作，即兩者都是O(1)泛鸟；但是在刪除node引起樹的不平衡時蝠咆，最壞情況下，AVL需要維護從被刪node到root這條路徑上所有node的平衡性北滥，因此需要旋轉(zhuǎn)的量級O(logN)刚操，而RB-Tree最多只需3次旋轉(zhuǎn)，只需要O(1)的復(fù)雜度再芋。2）其次菊霜，AVL的結(jié)構(gòu)相較RB-Tree來說更為平衡，在插入和刪除node更容易引起Tree的unbalance济赎，因此在大量數(shù)據(jù)需要插入或者刪除時鉴逞，AVL需要rebalance的頻率會更高。因此司训，RB-Tree在需要大量插入和刪除node的場景下构捡，效率更高。自然壳猜，由于AVL高度平衡勾徽，因此AVL的search效率更高。3）map的實現(xiàn)只是折衷了兩者在search统扳、insert以及delete下的效率喘帚。總體來說咒钟，RB-tree的統(tǒng)計性能是高于AVL的吹由。
**B＋tree **是一個n叉樹，每個節(jié)點有多個葉子節(jié)點朱嘴，一顆B+樹包含根節(jié)點倾鲫，內(nèi)部節(jié)點，葉子節(jié)點腕够。根節(jié)點可能是一個葉子節(jié)點级乍，也可能是一個包含兩個或兩個以上葉子節(jié)點的節(jié)點。
B＋tree的性質(zhì)：
1.n棵子tree的節(jié)點包含n個關(guān)鍵字帚湘，不用來保存數(shù)據(jù)而是保存數(shù)據(jù)的索引玫荣。
2.所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針大诸，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接捅厂。
3.所有的非終端結(jié)點可以看成是索引部分贯卦，結(jié)點中僅含其子樹中的最大（或最小）關(guān)鍵字焙贷。
