這篇文章的出現(xiàn)，主要是因為在復(fù)習(xí)數(shù)據(jù)庫的時候，涉及到了b樹和b+樹，再加上之前復(fù)習(xí)多路復(fù)用的時候也會涉及到紅黑樹，所以就想把這幾種樹統(tǒng)統(tǒng)總結(jié)一下，做一個知識點(diǎn)的概括。
1. 二叉查找樹
要了解B樹，B+樹和紅黑樹首先要了解二叉查找樹，二叉查找樹（英語：Binary Search Tree），也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：
- 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
- 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
- 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
- 沒有鍵值相等的節(jié)點(diǎn)。
mOk8AA.png
中序遍歷二叉查找樹可得到一個節(jié)點(diǎn)值的有序序列。
二叉搜索樹在多次插入后可能會退化成一個線性鏈表。
2. B樹
一顆m階的B樹定義如下：：
- 每一個節(jié)點(diǎn)最多有 m 個子節(jié)點(diǎn)
- 每一個非葉子節(jié)點(diǎn)（除根節(jié)點(diǎn)）最少有 ?m/2? 個子節(jié)點(diǎn)
- 如果根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，那么它至少有兩個子節(jié)點(diǎn)
- 有 k 個子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)擁有 k ? 1 個鍵
- 所有的葉子節(jié)點(diǎn)都在同一層
2.1 模擬查找過程
假如說我們要查找10這個數(shù)字：
- 從根節(jié)點(diǎn)發(fā)現(xiàn)，10小于17，要走P1節(jié)點(diǎn)（磁盤塊2）
- 10大于8，小于12，走P2節(jié)點(diǎn)（磁盤塊6）
- 在磁盤塊6上面找到了10
如果用其存儲數(shù)據(jù)，每一個塊節(jié)點(diǎn)都是一個磁盤塊。
- 在磁盤塊6上面找到了10
3. B+樹
B+樹的定義各有不同，一種定義方式是關(guān)鍵字個數(shù)和孩子結(jié)點(diǎn)個數(shù)相同。這里我們采取維基百科上所定義的方式，即關(guān)鍵字個數(shù)比孩子結(jié)點(diǎn)個數(shù)小1，這種方式是和B樹基本等價的。
B+樹的性質(zhì)：
1）B+樹包含2種類型的結(jié)點(diǎn)：內(nèi)部結(jié)點(diǎn)（也稱索引結(jié)點(diǎn)）和葉子結(jié)點(diǎn)。根結(jié)點(diǎn)本身即可以是內(nèi)部結(jié)點(diǎn)，也可以是葉子結(jié)點(diǎn)。根結(jié)點(diǎn)的關(guān)鍵字個數(shù)最少可以只有1個。
2）B+樹與B樹最大的不同是內(nèi)部結(jié)點(diǎn)不保存數(shù)據(jù)，只用于索引，所有數(shù)據(jù)（或者說記錄）都保存在葉子結(jié)點(diǎn)中。
3） m階B+樹表示了內(nèi)部結(jié)點(diǎn)最多有m-1個關(guān)鍵字（或者說內(nèi)部結(jié)點(diǎn)最多有m個子樹），階數(shù)m同時限制了葉子結(jié)點(diǎn)最多存儲m-1個記錄。
4）內(nèi)部結(jié)點(diǎn)中的key都按照從小到大的順序排列，對于內(nèi)部結(jié)點(diǎn)中的一個key，左樹中的所有key都小于它，右子樹中的key都大于等于它。葉子結(jié)點(diǎn)中的記錄也按照key的大小排列。
5）每個葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
(2)，(5)是B+樹用來做INNODB索引數(shù)據(jù)結(jié)構(gòu)的重要原因。
查找原理和上面B樹的類似，但是要記住。只有葉子節(jié)點(diǎn)存儲了真實數(shù)據(jù)，內(nèi)部節(jié)點(diǎn)再真實也只是存儲了索引而已。
4. 紅黑樹：
1. 是一種自平衡二叉查找樹(紅黑樹嚴(yán)格來說并不遵守平衡二叉樹的定義，其左右子樹的高度差可以超過1)， 可以在O(logn)時間內(nèi)完成查找，插入和刪除，這里的n是樹中元素的數(shù)目。
- 紅黑樹的五個性質(zhì)：
- 節(jié)點(diǎn)是紅色或黑色。
- 根節(jié)點(diǎn)是黑色。
- 每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。
- 每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn))。
- 從任一節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
- 這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。 因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
2. 紅黑樹調(diào)整的方法有兩種：變色和旋轉(zhuǎn)，旋轉(zhuǎn)又分為左旋和右旋。
- 左旋：逆時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的右孩子取代，而自己成為自己的左孩子。
n9l3xP.png - 右旋：順時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的左孩子取代，而自己成為自己的右孩子。
n9lDx0.png
2. 紅黑樹比AVL樹的優(yōu)勢在哪？
- 查找顯然，avl樹要比紅黑樹更平衡，因此avl樹的查找效率更高。
- 插入不論是avl樹還是紅黑樹，旋轉(zhuǎn)的時間復(fù)雜度都是O(1)對于avl樹，旋轉(zhuǎn)的時候，需要找到第一個不平衡節(jié)點(diǎn)，這就需要我們維護(hù)一個平衡因子，每一次插入，旋轉(zhuǎn)，刪除等操作，都要更新從跟節(jié)點(diǎn)到被修改節(jié)點(diǎn)這個路徑上的平衡因子，最差情況下，需要O(logn)的時間復(fù)雜度，對于紅黑樹，除了旋轉(zhuǎn)外，最差情況下也需要O(logn)的時間復(fù)雜度來調(diào)整平衡，注意這只是極端情況下，比如父節(jié)點(diǎn)和伯父節(jié)點(diǎn)都是紅色，曾祖父節(jié)點(diǎn)也是紅色，這個時候，就要遞歸的去平衡父節(jié)點(diǎn)，然而，采用自頂向下的方法（就是如果一個節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是紅色，就把這個節(jié)點(diǎn)變成紅色，它的兩個子節(jié)點(diǎn)變成黑色），減少了多次旋轉(zhuǎn)操作，但也使得調(diào)整顏色的操作時間復(fù)雜度最差情況下是O(logn)。但這僅僅是很少的情況，所以紅黑樹的插入操作統(tǒng)計上比avl樹要好
- 刪除對于avl樹，刪除意味著某個子樹深度減少，這個時候，我們找到第一個不平衡的點(diǎn)，像插入操作那樣進(jìn)行旋轉(zhuǎn)，使得子樹平衡，然后，遞歸的使它的祖先節(jié)點(diǎn)也平衡。對于紅黑樹，也是只有個別情況才會遞歸平衡父節(jié)點(diǎn)，它發(fā)生在：兄弟節(jié)點(diǎn)是黑色，兩個侄兒也是黑色。當(dāng)兄弟節(jié)點(diǎn)是紅色的時候，轉(zhuǎn)化為兄弟節(jié)點(diǎn)是黑色的情況處理，當(dāng)兩個侄兒有紅色節(jié)點(diǎn)的時候，則在常數(shù)時間內(nèi)就可以達(dá)到平衡。所以，刪除操作紅黑樹的平均效率也比avl樹高。
B樹B+樹這么好，為什么還要用紅黑樹
一般都是在內(nèi)存操作或者數(shù)據(jù)量不大的時候采用紅黑樹，因為紅黑樹沒有索引節(jié)點(diǎn)，會節(jié)省內(nèi)存。如果數(shù)據(jù)量很大，就像是數(shù)據(jù)庫那樣，還是需要使用b+樹的。
