Mysql B+數索引分析

         InnoDB存儲引擎支援以下幾種常見的索引：

•  B+樹索引
• 全文索引
• 哈希索引

        B+數索引的構造類似于二叉樹，根據 鍵值快熟查找資料，并且B+樹中的B不代表二叉（Binary），而實代表平衡（balance），因為B+樹是從最早的平衡二叉樹演變而來的，但是B+樹不是一個二叉樹。B+樹索引并不能找到一個鍵值的具體行，B+樹索引找到的隻是被查找資料行所在的頁。然後資料庫通過英把頁讀入記憶體，再在頁中進行查找，最後找到要查找的資料。

       B+樹索引是資料庫中使用最頻繁的一種索引。B+樹是有平衡二叉樹演化而來，是以在介紹B+樹之前，先了解一下什麼是二叉查找樹和二叉平衡樹。

       一.二叉查找樹

       在二叉查找樹中，左子樹的鍵值總是小于根節點的鍵值，右子樹的鍵值總是大于根節點的鍵值。

     該圖就是二叉查找樹，并且可以通過中序周遊得到鍵值的排序，為：235678.

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

    二叉查找樹可以任意地構造，同樣是2,3,5,6,7,8這六個數字，也可以按照下圖的方式來構造：

     但是這棵二叉樹的查詢效率就低了。是以若想二叉樹的查詢效率盡可能高，需要這棵二叉樹是平衡的，進而引出新的定義——平衡二叉樹，或稱AVL樹。

   二.平衡二叉樹

  平衡二叉樹首先要滿足二叉查找樹的定義既：左子樹的鍵值要小于根節點的鍵值，右子樹的鍵值要大于根節點的鍵值，其次必須滿足任意節點的兩個子樹的高度最大差為1。

  平衡二叉樹的查詢速度比較快，但是維護一顆平衡二叉樹的代價非常大，對二叉樹插入資料時需要左旋或者右旋來更新後樹的平衡。

平衡二叉樹（AVL樹）在符合二叉查找樹的條件下，還滿足任何節點的兩個子樹的高度最大差為1。下面的兩張圖檔，左邊是AVL樹，它的任何節點的兩個子樹的高度差<=1；右邊的不是AVL樹，其根節點的左子樹高度為3，而右子樹高度為1； 

如果在AVL樹中進行插入或删除節點，可能導緻AVL樹失去平衡，這種失去平衡的二叉樹可以概括為四種姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它們的示意圖如下： 

這四種失去平衡的姿态都有各自的定義： 

LL：LeftLeft，也稱“左左”。插入或删除一個節點後，根節點的左孩子（Left Child）的左孩子（Left Child）還有非空節點，導緻根節點的左子樹高度比右子樹高度高2，AVL樹失去平衡。

RR：RightRight，也稱“右右”。插入或删除一個節點後，根節點的右孩子（Right Child）的右孩子（Right Child）還有非空節點，導緻根節點的右子樹高度比左子樹高度高2，AVL樹失去平衡。

LR：LeftRight，也稱“左右”。插入或删除一個節點後，根節點的左孩子（Left Child）的右孩子（Right Child）還有非空節點，導緻根節點的左子樹高度比右子樹高度高2，AVL樹失去平衡。

RL：RightLeft，也稱“右左”。插入或删除一個節點後，根節點的右孩子（Right Child）的左孩子（Left Child）還有非空節點，導緻根節點的右子樹高度比左子樹高度高2，AVL樹失去平衡。

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

LL的旋轉。LL失去平衡的情況下，可以通過一次旋轉讓AVL樹恢複平衡。步驟如下：

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

LL旋轉示意圖如下： 

RR的旋轉：RR失去平衡的情況下，旋轉方法與LL旋轉對稱，步驟如下：

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

RR旋轉示意圖如下： 

LR的旋轉：LR失去平衡的情況下，需要進行兩次旋轉，步驟如下：

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

LR的旋轉示意圖如下： 

RL的旋轉：RL失去平衡的情況下也需要進行兩次旋轉，旋轉方法與LR旋轉對稱，步驟如下：

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

RL的旋轉示意圖如下： 

   三.B+樹

   B+樹和平衡二叉樹，平衡二叉樹一樣。B+樹是為了磁盤或其他直接存取輔助裝置設計的一種平衡查找樹。在B+樹中，所有記錄節點都是按鍵值對的大小順序存放在同一層的葉子節點上，由各各葉子節點指針進行連結。

  1.B+樹的插入操作

   B+樹的插入必須保證插入後葉子節點中的記錄依然排序，同時考慮插入到B+樹的三種情況。

    在B+樹中頁會由旋轉的功能，當葉子頁已經滿的時候，但是其的左右兄弟節點沒有滿的情況下。這時B+樹不會急于去做拆分頁的操作，而是将記錄移到所在頁的兄弟節點上，通常左兄弟會被首先檢查用來做旋轉操作。

   2.B+樹的删除

B+樹使用填充因子來控制樹的删除變化，50%是填充因子可設的最小值。B+樹的删除操作同樣必須滿足删除後葉子節點中的記錄依然排序，B+樹的删除操作同樣考慮以下三種情況。

   3.B+樹索引

   B+樹在資料中的高度一般都是2~4層。并且B+樹索引可以分為聚集索引和輔助索引。聚類索引與輔助索引不同的是，葉子節點是否是一整行的資訊。

   3.1.聚類索引

    聚集索引就是按照每一張表的主鍵構造一顆B+樹，同時葉子節點中存放的即為整張表的行記錄資料，也将聚集索引的葉子節點稱為資料頁。聚集索引的這個特征決定了索引組織表中的資料是索引的一部分。同B+樹的資料結構一樣，每個資料頁都是通過一個雙向連結清單來進行連結的。

      由于實際的資料頁隻能按照一棵B+樹的進行排序，是以每張表隻能擁有一個聚集索引。

    3.2.輔助索引

    輔助索引葉子節點并不包含行記錄的全部資料。葉子節點除了包含鍵值以外，每個葉子節點中的索引行中還包含一個書簽，該書簽用于告訴InnoDB存儲引擎哪裡可以找到與索引相對應的行資料。由于InnoDB存儲引擎表是索引組織表，是以InnoDB存儲引擎的輔助索引的書簽就是相應行資料的聚集索引建。每張表可以有多個輔助索引。

文中的圖檔來源https://blog.csdn.net/ifollowrivers/article/details/73614549