Binary Search Tree（二叉查找樹、二叉排序樹、二叉搜索樹）

指一棵空樹或者具有下列性質的 二叉樹 ：

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

Balanced Binary Search Tree（平衡二叉查找樹、AVL樹）

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

紅黑樹

1. 紅黑樹是每個節點都帶有 顏色 屬性的 二叉查找樹 ，顏色為 紅色 或 黑色 。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

   性質1. 節點是紅色或黑色。

   性質2. 根是黑色。

   性質3. 所有葉子都是黑色（葉子是NIL節點）。

   性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

   性質5. 從任一節點到其每個葉子的所有 簡單路徑 都包含相同數目的黑色節點。

   二叉查找樹但若是一棵具有n個結點的線性鏈，則此些操作最壞情況運行時間為O（n），但是 紅黑樹，能保證在最壞情況下，基本的動態幾何操作的時間均為O（lgn）。

   從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。

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

   平衡二叉樹和紅黑樹比較：

   AVL是嚴格平衡樹，因此在增加或者刪除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多；

   紅黑是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低；

   所以簡單說，如果你的應用中，搜索的次數遠遠大于插入和刪除，那么選擇AVL，如果搜索，插入刪除次數幾乎差不多，或者插入更多，應該選擇RB

B樹

???? 是一個節點可以擁有多于2個子節點的 二叉查找樹 。

1. 

   就是大規模數據存儲中，實現索引查詢這樣一個實際背景下，樹節點存儲的元素數量是有限的（如果元素數量非常多的話，查找就退化成節點內部的線性查找了），這樣導致二叉查找樹結構由于 樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導致查詢效率低下 （為什么會出現這種情況，待會在外部存儲器-磁盤中有所解釋），那么如何減少樹的深度（當然是不能減少查詢的數據量），一個基本的想法就是：采用 多叉樹 結構（由于樹節點元素數量是有限的，自然該節點的子樹數量也就是有限的）。

   在大規模數據存儲方面，大量數據存儲在外存磁盤中，而在外存磁盤中讀取/寫入塊(block)中某數據時，首先需要定位到磁盤中的某塊，如何有效地查找磁盤中的數據，需要一種合理高效的外存數據結構，就是B-tree結構。

   B樹與紅黑樹最大的不同在于，B樹的結點可以有許多子女，從幾個到幾千個。那為什么又說B樹與紅黑樹很相似呢?因為與紅黑樹一樣，一棵含n個結點的B樹的高度也為O（lgn），但可能比一棵紅黑樹的高度小許多，應為它的分支因子比較大。所以，B樹可以在O（logn）時間內，實現各種如插入（insert），刪除（delete）等動態集合操作。

B＋樹

????? B ⁺ -tree ：是應文件系統所需而產生的一種 B-tree的變形樹。

???? 一棵m階的B+樹和m階的B樹的異同點在于：

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

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

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

   a) 為什么說 B ⁺ -tree 比B 樹更適合實際應用中操作系統的文件索引和數據庫索引？

   1) B ⁺ -tree的磁盤讀寫代價更低

   B ⁺ -tree 的內部結點并沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。

   舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階 B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而 B ^+? 樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候，B 樹就比 B ^+? 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。

   

   2) B ⁺ -tree的查詢效率更加穩定

   由于非終結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

   數據庫索引采用B+樹的主要原因是 B樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹只要遍歷葉子節點就可以實現整棵樹的遍歷。而且在數據庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作（或者說效率太低）。

B ^* -tree

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

   B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針。

   B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針。

   所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高；

   現在一般主流的數據庫索引一般都是用的B/B+樹系列，包括MySQL及NoSQL中的MongoDB。

LSM－tree（Log Structured merge －tree）

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

?