樹形結構總結

1.BST

二叉排序樹又叫二叉查找樹，英文名稱是：Binary Sort Tree. BST的定義一句話概括：左 < 中 < 右。根據這個原理，我們可以推斷：BST的中序周遊必定是嚴格遞增的。

2.AVL

平衡二叉搜尋樹（Self-balancing binary search tree）又被稱為AVL樹，且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

某結點的左子樹與右子樹的高度(深度)差即為該結點的平衡因子（BF,Balance Factor）。平衡二叉樹上所有結點的平衡因子隻可能是 -1，0 或 1。如果某一結點的平衡因子絕對值大于1則說明此樹不是平衡二叉樹。

往平衡二叉樹中添加節點很可能會導緻二叉樹失去平衡，是以我們需要在每次插入節點後進行平衡的維護操作。插入節點破壞平衡性有如下四種情況：

1)LL右旋(因左子樹的左子樹插入資料導緻樹不平衡)

2)RR左旋(因右子樹的右子樹插入資料導緻樹不平衡)

3)LR先左再右(因左子樹的右子樹插入資料導緻樹不平衡)

4)RL先右再左(因右子樹的左子樹插入資料導緻樹不平衡)

3.RBT

紅黑樹的英文是“Red-Black Tree”，簡稱 R-B Tree。它是一種不嚴格的平衡二叉查找樹，顧名思義，紅黑樹中的節點，一類被标記為黑色，一類被标記為紅色。除此之外，一棵紅黑樹還需要滿足這樣四個要求：

1.根節點是黑色的；

2.每個葉子節點都是黑色的空節點，也就是說，葉子節點不存儲資料；

3.任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；

4.每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；

實際上，紅黑樹的平衡過程和AVL樹一樣，在進行節點的插入和删除時，就會破壞紅黑樹的一些規則．在紅黑樹中主要破壞的是以下兩點：

1．任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；

2． 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；

紅黑樹的高度近似 2log2n，隻比高度平衡的 AVL 樹的高度（log2n）僅僅大了一倍。

4.B樹及其變形

1.B樹

首先，B樹和B-樹是一種結構，B樹屬于多叉樹又名平衡多路查找樹（查找路徑不隻兩個），資料庫索引技術裡大量使用者B樹和B+樹的資料結構，其特點包括：

(1)排序方式：所有節點關鍵字是按遞增次序排列，并遵循左小右大原則；

(2)子節點數：非葉節點的子節點數>1，且<=M ，且M>=2，空樹除外（注：M階代表一個樹節點最多有多少個查找路徑，M=M路,當M=2則是2叉樹,M=3則是3叉）；

(3)關鍵字數：枝節點的關鍵字數量大于等于ceil(m/2)-1個且小于等于M-1個（注：ceil()是個朝正無窮方向取整的函數 如ceil(1.1)結果為2);

(4)所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針隻不過其指針位址都為null對應下圖最後一層節點的空格子;

2.B+樹

B+樹是B樹的一個更新版，相對于B樹來說B+樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近于二分法查找，B樹有如下特點：

(1)B+樹的層級更少：相較于B樹B+每個非葉子節點存儲的關鍵字數更多，樹的層級更少是以查詢資料更快；

(2)B+樹查詢速度更穩定：B+所有關鍵字資料位址都存在葉子節點上，是以每次查找的次數都相同是以查詢速度要比B樹更穩定;

(3)B+樹天然具備排序功能：B+樹所有的葉子節點資料構成了一個有序連結清單，在查詢大小區間的資料時候更友善，資料緊密性很高，緩存的命中率也會比B樹高。

(4)B+樹全節點周遊更快：B+樹周遊整棵樹隻需要周遊所有的葉子節點即可，，而不需要像B樹一樣需要對每一層進行周遊，這有利于資料庫做全表掃描。

B樹相對于B+樹的優點是，如果經常通路的資料離根節點很近，而B樹的非葉子節點本身存有關鍵字其資料的位址，是以這種資料檢索的時候會要比B+樹快。

B+樹與B樹差別包括：

(1)B+跟B樹不同B+樹的非葉子節點不儲存關鍵字記錄的指針，隻進行資料索引，這樣使得B+樹每個非葉子節點所能儲存的關鍵字大大增加；

(2)B+樹葉子節點儲存了父節點的所有關鍵字記錄的指針，所有資料位址必須要到葉子節點才能擷取到。是以每次資料查詢的次數都一樣；

(3)B+樹葉子節點的關鍵字從小到大有序排列，左邊結尾資料都會儲存右邊節點開始資料的指針。

(4)非葉子節點的子節點數=關鍵字數（來源百度百科）（根據各種資料 這裡有兩種算法的實作方式，另一種為非葉節點的關鍵字數=子節點數-1（來源維基百科)，雖然他們資料排列結構不一樣，但其原理還是一樣的Mysql 的B+樹是用第一種方式實作）;

3.B*樹

B*樹是B+樹的變種，相對于B+樹他們的不同之處如下：