二叉查找樹

二叉樹具有以下性質：左子樹的鍵值小于根的鍵值，右子樹的鍵值大于根的鍵值。

對該二叉樹的節點進行查找發現深度為1的節點的查找次數為1，深度為2的查找次數為2，深度為n的節點的查找次數為n，因此其平均查找次數為 (1+2+2+3+3+3) / 6 = 2.3次。

平衡二叉樹AVLT

為了提高二叉樹的查找效率，顯然二叉樹層級越少越好，于是就有了平衡二叉樹。它在符合二叉查找樹的條件下，還滿足任何節點的兩個子樹的高度最大差為1，如下圖所示：

AVL二叉樹的高度為：
$$lo{g}_{2}n$$
如果在AVL樹中進行插入或刪除節點，可能導致AVL樹失去平衡，這種失去平衡的二叉樹可以概括為四種姿態：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它們的示意圖如下：

AVL樹失去平衡之后，可以通過旋轉使其恢復平衡。下面分別介紹四種失去平衡的情況下對應的旋轉方法。

LL的旋轉：

1. 將根節點的左孩子作為新根節點。
2. 將新根節點的右孩子作為原根節點的左孩子。
3. 將原根節點作為新根節點的右孩子。

RR的旋轉：

1. 將根節點的右孩子作為新根節點。
2. 將新根節點的左孩子作為原根節點的右孩子。
3. 將原根節點作為新根節點的左孩子。

LR的旋轉：

1. 圍繞根節點的左孩子進行RR旋轉。
2. 圍繞根節點進行LL旋轉。

RL的旋轉：

1. 圍繞根節點的右孩子進行LL旋轉。
2. 圍繞根節點進行RR旋轉。

紅黑樹 RBT

因為二叉搜索樹有可能會出現極端的情況，就是只有一側有數據，那這樣的話就會降級為鏈表。后來出現了平衡二叉樹，但是由于強制平衡所導致付出的代價比較高昂，所以紅黑樹出現了。

紅黑樹（Red Black Tree） 的實現是基于二叉查找樹的，對于含有n個節點的二叉查找樹的最壞的情況是這n個節點形成一條單鏈，此時二叉查找樹的高度為n，時間復雜度為O(n)。為了維持AVL的高度，就需要采取一些措施在不影響二叉查找樹的性質下改變二叉查找樹的結構，使之平衡。紅黑樹就是這樣一種二叉查找樹，即自平衡二叉查找樹，也就是紅黑樹。

紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。

1. 根節點是黑色。
2. 所有葉子都是黑色，葉子是NUIL節點。
3. 紅色節點的兩個子節點都是黑色。
4. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點，這一點就要求，如果一個分支比另一個分支多了一層，那么就必須多一個紅色節點。

當對紅黑樹進行插入或刪除時，就有可能破壞紅黑樹的性質，這時需要通過變色、左旋與右旋操作平衡紅黑樹。變色操作很簡單，紅變黑，黑變紅；左旋可以看成是在某個區域內沿著某個節點X逆時針旋轉，右旋是順時針。然后X就成了此區域內的最高節點。

紅黑樹并沒有像AVL那樣對樹的平衡有那么嚴格的要求，它追求的是大致平衡，因此左旋右旋操作沒那么頻繁。它的高度最多是
$$2?lo{g}_2(n+1)$$
因此時間復雜度也是這個，其查找效率雖然不如AVL，但是還是處于同一量級的。

AVL適合查多改少的場景；紅黑樹相較于AVL，更適合頻繁插入或刪除的場景。

在插入節點時，先將其設置為紅色（滿足特性4），然后特性1和2好說，所以需要重點考慮的是特性3，然后再做一些旋轉和改色。

在整個插入旋轉的過程中，我們一定要確保高度最低原則，即把紅色刪除后剩下的高度越低越好，那么在調整的時候能給紅色就給紅色。

現在新節點為紅色，來考慮特性3，如果父節點是黑色，那么無需處理，如果父節點為紅色，則需要分情況來處理。此處我們拋開 NULL 節點。并且假設父節點是祖父節點的左節點，實際上父節點是祖父節點的右節點的情況是類似的。

1、新節點為左節點，叔叔節點為紅色

2、新節點為左節點，此時必然不存在叔叔節點

3、新節點為右節點，叔叔節點為紅色

4、新節點為右節點，此時必然不存在叔叔節點

情況3左旋變成了情況1，情況4通過左旋變成了情況2，因此只需要討論1，2。

情況1：將祖父節點變為紅色，父節點和叔叔節點變為黑色，新增節點是紅色，如果祖父節點是根節點那么根節點應該是黑色，如果祖父節點還有父節點，則需要將祖父節點看成輸入節點遞歸向上調整。

情況2：父節點變黑，祖父節點變紅，沿父節點右旋。

平衡多路查找數B-Tree

B-Tree是為磁盤等外存儲設備設計的一種平衡查找樹。因此在講B-Tree之前先了解下磁盤的相關知識。

操作系統從磁盤讀取數據到內存時是以磁盤塊（block）為基本單位的（在許多操作系統中，塊的大小通常為4k），位于同一個磁盤塊中的數據會被一次性讀取出來，而不是需要什么取什么。

InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB，可通過參數innodb_page_size將頁的大小設置為4K、8K、16K，在MySQL中可通過如下命令查看頁的大小：

mysql> show variables like 'innodb_page_size';

而操作系統一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次為一個節點申請磁盤空間時都會是若干地址連續磁盤塊來達到頁的大小16KB。而且InnoDB在把磁盤數據讀入到內存時也是以頁為基本單位，在查詢數據時如果一個頁中的每條數據都能有助于定位數據記錄的位置，這將會減少磁盤I/O次數，提高查詢效率。

B-Tree結構的數據可以讓系統高效的找到數據所在的磁盤塊。為了描述B-Tree，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值，對應表中的主鍵值，data為一行記錄中除主鍵外的數據。對于不同的記錄，key值互不相同。

一棵 m 階的B-Tree有如下特性

1. 每個節點最多有 m 個孩子。
2. 除了根節點和葉子節點外，其它每個節點最少有Ceil(m/2)個孩子。
3. 若根節點不是葉子節點，則至少有2個孩子 。
4. 所有葉子節點都在同一層，且不包含其它關鍵字信息 。
5. 每個非終端節點包含 n 個關鍵字信息（P0, P1, …Pn, k1,…kn） 。
6. 關鍵字的個數 n 滿足：ceil(m/2)-1 <= n <= m-1 。
7. ki(i=1,…n)為關鍵字，且關鍵字升序排序。
8. Pi(i=1,…n)為指向子樹根節點的指針。P(i-1)指向的子樹的所有節點關鍵字均小于ki，但都大于k(i-1)。

B-Tree中的每個節點根據實際情況可以包含大量的關鍵字信息和分支，如下圖所示為一個 3 階的B-Tree：

每個節點為一個頁，一個節點上有兩個升序排序的關鍵字和三個指向子節點的指針，指針存儲的是子節點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為例，關鍵字為17和35，P1指針指向的子樹的數據范圍為小于17，P2指針指向的子樹的數據范圍為17~35，P3指針指向的子樹的數據范圍為大于35。

模擬查找關鍵字29的過程：

1. 根據根節點找到磁盤塊1，讀入內存。【磁盤I/O操作第1次】
2. 比較關鍵字29在區間（17,35），找到磁盤塊1的指針P2。
3. 根據P2指針找到磁盤塊3，讀入內存。【磁盤I/O操作第2次】
4. 比較關鍵字29在區間（26,30），找到磁盤塊3的指針P2。
5. 根據P2指針找到磁盤塊8，讀入內存。【磁盤I/O操作第3次】
6. 在磁盤塊8中的關鍵字列表中找到關鍵字29。

分析上面過程，發現需要3次磁盤I/O操作，和3次內存查找操作。由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節點層數，使每次磁盤I/O取到內存的數據都發揮了作用，從而提高了查詢效率。

B+Tree

B+Tree是在B-Tree基礎上的一種優化，使其更適合實現外存儲索引結構，InnoDB存儲引擎就是用B+Tree實現其索引結構。

從上一節中的B-Tree結構圖中可以看到每個節點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節點（即一個頁）能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲key值信息，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度。

B+Tree相對于B-Tree有幾點不同：

1. 非葉子節點只存儲鍵值信息。
2. 所有葉子節點之間都有一個鏈指針。
3. 數據記錄都存放在葉子節點中。

將上一節中的B-Tree優化，由于B+Tree的非葉子節點只存儲鍵值信息，假設每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結構如下圖所示：

通常在B+Tree上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點（即數據節點）之間是一種鏈式環結構。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始，進行隨機查找。

可能上面例子中只有22條數據記錄，看不出B+Tree的優點，下面做一個推算：

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個字節）或BIGINT（占用8個字節），指針類型也一般為4或8個字節，也就是說一個頁（B+Tree中的一個節點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為方便計算，這里的K取值為10^3）。也就是說一個深度為 3 的B+Tree索引可以維護10^3 * 10^3 * 10^3 = 10億 條記錄。

實際情況中每個節點可能不能填充滿，因此在數據庫中，B+Tree的高度一般都在2_{4層。mysql的InnoDB存儲引擎在設計時是將根節點常駐內存的，也就是說查找某一鍵值的行記錄時最多只需要1}3次磁盤I/O操作。

數據庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在數據庫中的實現即為聚集索引，聚集索引的B+Tree中的葉子節點存放的是整張表的行記錄數據。輔助索引與聚集索引的區別在于輔助索引的葉子節點并不包含行記錄的全部數據，而是存儲相應行數據的聚集索引鍵，即主鍵值。當通過輔助索引來查詢數據時，InnoDB存儲引擎會遍歷輔助索引找到主鍵，然后再通過主鍵在聚集索引中找到完整的行記錄數據。mysql數據表都有一個 Primary Key，聚集索引就是基于 Primary Key 創建的，另外你還可以創建其他的索引，就是輔助索引。

InnoDB表中如果不存在 Primary Key ，則MySQL自動生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形。

MyISAM 引擎使用的也是B+Tree，但是它的葉子節點上存儲的data是具體記錄的地址，因此被稱為非聚集索引。