樹形結構定義介紹

B-樹就是B樹，中間是橫線不是減号。B樹是一種多路平衡查找樹。

B-樹（Balance Tree），一個m階的B樹具有如下幾個特征： 

1.根結點至少有兩個子女。

2.每個中間節點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m

3.每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m

4.所有的葉子結點都位于同一層。

5.每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。 

一個m階的B+樹具有如下幾個特征：

1.有k個子樹的中間節點包含有k個元素（B樹中是k-1個元素），每個元素不儲存資料，隻用來索引，所有資料都儲存在葉子節點。(中間節點可以存更多元素)

2.所有的葉子結點中包含了全部元素的資訊，及指向含這些元素記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結。

3.所有的中間節點元素都同時存在于子節點，在子節點元素中是最大（或最小）元素。

在資料庫的聚集索引（Clustered Index）中，葉子節點直接包含衛星資料。在非聚集索引（NonClustered Index）中，葉子節點帶有指向衛星資料的指針。

B+樹相比B樹的優勢有三個：

IO次數更少,中間節點不存資料可容納更多元素 

查詢性能穩定，都需要定位到葉子節點

範圍查詢簡便，葉子節點之間是有序連結清單

左子樹上所有結點的值均小于或等于它的根結點的值。

右子樹上所有結點的值均大于或等于它的根結點的值。

左、右子樹也分别為二叉排序樹。

紅黑樹是一種近似平衡的二叉查找樹，它能夠確定任何一個節點的左右子樹的高度差不會超過二者中較低那個的一倍。

具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）：

每個節點要麼是紅色，要麼是黑色。

根節點必須是黑色

紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）。

對于每個節點，從該點至null（樹尾端）的任何路徑，都含有相同個數的黑色節點。

在樹的結構發生改變時（插入或者删除操作），往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的條件。

調整可以分為兩類：一類是顔色調整，即改變某個節點的顔色；另一類是結構調整，集改變檢索樹的結構關系。結構調整過程包含兩個基本操作：左旋（Rotate Left），右旋（RotateRight）。