Binary Search Tree（二叉查找樹(shù)、二叉排序樹(shù)、二叉搜索樹(shù)）

指一棵空樹(shù)或者具有下列性質(zhì)的 二叉樹(shù) ：

1. 1）若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2. 2）任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
3. 3）任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)。
4. 4）沒(méi)有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）。

Balanced Binary Search Tree（平衡二叉查找樹(shù)、AVL樹(shù)）

1. 在AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè) 子樹(shù) 的高度最大差別為一，所以它也被稱(chēng)為 高度平衡樹(shù) 。查找、插入和刪除在平均和最壞情況下都是 O （log? n ）。增加和刪除可能需要通過(guò)一次或多次 樹(shù)旋轉(zhuǎn) 來(lái)重新平衡這個(gè)樹(shù)。
2. 平衡二叉樹(shù)是一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，它有很均衡的插入、刪除以及查詢性能（時(shí)間復(fù)雜度都是O(logn)）。Linux2.4以前的內(nèi)核中，虛擬內(nèi)存管理中用的容器就是AVL Tree。AVL Tree對(duì)平衡的要求是比較嚴(yán)格的，它要求左右子數(shù)之間的長(zhǎng)度差不能大于1。

紅黑樹(shù)

1. 紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有 顏色 屬性的 二叉查找樹(shù) ，顏色為 紅色 或 黑色 。在二叉查找樹(shù)強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求:

   性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。

   性質(zhì)2. 根是黑色。

   性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。

   性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))

   性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有 簡(jiǎn)單路徑 都包含相同數(shù)目的黑色節(jié)點(diǎn)。

   二叉查找樹(shù)但若是一棵具有n個(gè)結(jié)點(diǎn)的線性鏈，則此些操作最壞情況運(yùn)行時(shí)間為O（n），但是 紅黑樹(shù)，能保證在最壞情況下，基本的動(dòng)態(tài)幾何操作的時(shí)間均為O（lgn）。

   從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。

   詳細(xì)介紹可以參考： http://blog.csdn.net/v_JULY_v/article/details/6105630 等的詳細(xì)介紹。

   平衡二叉樹(shù)和紅黑樹(shù)比較：

   AVL是嚴(yán)格平衡樹(shù)，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹(shù)要多；

   紅黑是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低；

   所以簡(jiǎn)單說(shuō)，如果你的應(yīng)用中，搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL，如果搜索，插入刪除次數(shù)幾乎差不多，或者插入更多，應(yīng)該選擇RB

B樹(shù)

???? 是一個(gè)節(jié)點(diǎn)可以擁有多于2個(gè)子節(jié)點(diǎn)的 二叉查找樹(shù) 。

1. 

   就是大規(guī)模數(shù)據(jù)存儲(chǔ)中，實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下，樹(shù)節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的（如果元素?cái)?shù)量非常多的話，查找就退化成節(jié)點(diǎn)內(nèi)部的線性查找了），這樣導(dǎo)致二叉查找樹(shù)結(jié)構(gòu)由于 樹(shù)的深度過(guò)大而造成磁盤(pán)I/O讀寫(xiě)過(guò)于頻繁，進(jìn)而導(dǎo)致查詢效率低下 （為什么會(huì)出現(xiàn)這種情況，待會(huì)在外部存儲(chǔ)器-磁盤(pán)中有所解釋?zhuān)敲慈绾螠p少樹(shù)的深度（當(dāng)然是不能減少查詢的數(shù)據(jù)量），一個(gè)基本的想法就是：采用 多叉樹(shù) 結(jié)構(gòu)（由于樹(shù)節(jié)點(diǎn)元素?cái)?shù)量是有限的，自然該節(jié)點(diǎn)的子樹(shù)數(shù)量也就是有限的）。

   在大規(guī)模數(shù)據(jù)存儲(chǔ)方面，大量數(shù)據(jù)存儲(chǔ)在外存磁盤(pán)中，而在外存磁盤(pán)中讀取/寫(xiě)入塊(block)中某數(shù)據(jù)時(shí)，首先需要定位到磁盤(pán)中的某塊，如何有效地查找磁盤(pán)中的數(shù)據(jù)，需要一種合理高效的外存數(shù)據(jù)結(jié)構(gòu)，就是B-tree結(jié)構(gòu)。

   B樹(shù)與紅黑樹(shù)最大的不同在于，B樹(shù)的結(jié)點(diǎn)可以有許多子女，從幾個(gè)到幾千個(gè)。那為什么又說(shuō)B樹(shù)與紅黑樹(shù)很相似呢?因?yàn)榕c紅黑樹(shù)一樣，一棵含n個(gè)結(jié)點(diǎn)的B樹(shù)的高度也為O（lgn），但可能比一棵紅黑樹(shù)的高度小許多，應(yīng)為它的分支因子比較大。所以，B樹(shù)可以在O（logn）時(shí)間內(nèi)，實(shí)現(xiàn)各種如插入（insert），刪除（delete）等動(dòng)態(tài)集合操作。

B＋樹(shù)

????? B ⁺ -tree ：是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種 B-tree的變形樹(shù)。

???? 一棵m階的B+樹(shù)和m階的B樹(shù)的異同點(diǎn)在于：

1. ?有n棵子樹(shù)的結(jié)點(diǎn)中含有n-1 個(gè)關(guān)鍵字； (與B 樹(shù)n棵子樹(shù)有n-1個(gè)關(guān)鍵字 保持一致，參照： http://en.wikipedia.org/wiki/B%2B_tree#Overview ，而下面 B+樹(shù)的圖可能有問(wèn)題 ，請(qǐng)讀者注意)

   ????? 2.所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。 (而B(niǎo) 樹(shù)的葉子節(jié)點(diǎn)并沒(méi)有包括全部需要查找的信息)

   ????? 3. 所有的非終端結(jié)點(diǎn)可以看成是索引部分 ，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大（或最小）關(guān)鍵字。 (而B(niǎo) 樹(shù)的非終節(jié)點(diǎn)也包含需要查找的有效信息)

   a) 為什么說(shuō) B ⁺ -tree 比B 樹(shù)更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫(kù)索引？

   1) B ⁺ -tree的磁盤(pán)讀寫(xiě)代價(jià)更低

   B ⁺ -tree 的內(nèi)部結(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹(shù)更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來(lái)說(shuō)IO讀寫(xiě)次數(shù)也就降低了。

   舉個(gè)例子，假設(shè)磁盤(pán)中的一個(gè)盤(pán)塊容納16bytes，而一個(gè)關(guān)鍵字2bytes，一個(gè)關(guān)鍵字具體信息指針2bytes。一棵9階 B-tree(一個(gè)結(jié)點(diǎn)最多8個(gè)關(guān)鍵字)的內(nèi)部結(jié)點(diǎn)需要2個(gè)盤(pán)快。而 B ^+? 樹(shù)內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤(pán)快。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候，B 樹(shù)就比 B ^+? 樹(shù)多一次盤(pán)塊查找時(shí)間(在磁盤(pán)中就是盤(pán)片旋轉(zhuǎn)的時(shí)間)。

   

   2) B ⁺ -tree的查詢效率更加穩(wěn)定

   由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。

   數(shù)據(jù)庫(kù)索引采用B+樹(shù)的主要原因是 B樹(shù)在提高了磁盤(pán)IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題。正是為了解決這個(gè)問(wèn)題，B+樹(shù)應(yīng)運(yùn)而生。B+樹(shù)只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹(shù)的遍歷。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢是非常頻繁的，而B(niǎo)樹(shù)不支持這樣的操作（或者說(shuō)效率太低）。

B ^* -tree

1. B*-tree是 B ⁺ -tree 的變體，在 B ⁺ 樹(shù)的基礎(chǔ)上(所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針)，B*樹(shù)中非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹(shù)的1/2）。給出了一個(gè)簡(jiǎn)單實(shí)例，如下圖所示：

   B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針。

   B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針。

   所以，B*樹(shù)分配新結(jié)點(diǎn)的概率比B+樹(shù)要低，空間使用率更高；

   現(xiàn)在一般主流的數(shù)據(jù)庫(kù)索引一般都是用的B/B+樹(shù)系列，包括MySQL及NoSQL中的MongoDB。

LSM－tree（Log Structured merge －tree）

?????????? 詳細(xì)參考： http://duanple.blog.163.com/blog/static/7097176720120391321283/

?