專注於Java領域優質技術，歡迎關注

作者： 以李服人 知否專欄

前言

講到索引，第一反應肯定是能提高查詢效率。例如書的目錄，想要查找某一章節，會先從目錄中定位。如果沒有目錄，那麼就需要將所有內容都看一遍才能找到。

索引的設計對程序的性能至關重要，若索引太少，對查詢性能受影響；而如果索引太多，則會影響增/改/刪等的性能。

知識點

MySQL中一般支持以下幾種常見的索引：

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

我們今天重點來講下B+樹索引，以及為什麼要用B+樹來作為索引的數據結構。

B+樹索引並不能直接找到具體的行，只是找到被查找行所在的頁，然後DB通過把整頁讀入內存，再在內存中查找。

重溫數據結構

1.1 哈希結構

如有 3、1、2、10、9、0、4、6這8個數據，建立如 圖1-1所示哈希索引。

• 直接查詢：現在要從8個數中查找6這條記錄，只需要計算6的哈希值，便可快速定位記錄，時間複雜度為O(1)。
• 範圍查詢：如果要進行範圍查詢（大於4的數據），那這個索引就完全沒用了。

圖1-1 哈希索引



1.2 二叉樹查找樹

二叉樹是一種經典的數據結構，要求左子樹小於根節點，右子樹大於根節點。

如有 3、1、2、10、9、0、4、6這8個數據，建立如 圖1-2所示二分查找樹。

• 直接查詢：假設查找鍵值為6的記錄，先找到根4，4<6，因此查找4的右子樹，找到9；9大於6，因此查找9的左子樹；一共查找3次。但如果順序查找，則需要查找8次（位於最後）。
• 範圍查詢：如果需要查找大於4的數據，則遍歷4的右子樹就行了

圖1-2 二叉查找樹

1.3 平衡二叉樹（AVL樹）

按照二叉查找樹的定義，它是可以任意的構造，同樣是這些數字，可以按照 圖1-3-1的方式來建立二叉查找樹。同樣查找數據6，需要查找5次。

圖1-3-1 性能較差的二叉查找樹

因此為了最大性能地構造一個二叉查找樹，需要它是平衡的，即平衡二叉樹。

平衡二叉樹定義：首先符合二叉查找樹的定義，另外任何節點的兩個子樹高度最大差為1。

平衡二叉樹的查詢速度是很快的，但是有缺點：

1. 維護樹的代價是非常大，在進行插入或更新時，經常會需要多次左旋或右旋來維持平衡。如 圖1-3-2所示
2. 數據量多的時候，樹會很高，需要多次I/O操作。
3. 在進行範圍查找時，假設查找>=3，先找到3，然後需要查找到3的父節點，然後遍歷父節點的右子樹。



圖1-3-2 平衡二叉樹AVL

1.4 B+ 樹

在B+樹中，所有記錄節點存放在葉子節點上，且是順序存放，由各葉子節點指針進行連接。如果從最左邊的葉子節點開始順序遍歷，能得到所有鍵值的順序排序。

如有 3、1、2、10、9、0、4、6這8個數據，可建立如圖1-4-1所示高度為2的B+樹。

 圖1-4-1 高度為2的B+樹

在進行更新時，B+樹同樣需要類似二叉樹的旋轉操作。舉例，假設新增一個7，那可以直接填充到4、6的後面。如果再添加8，那麼就需要進行旋轉了，感受下面的B+樹旋轉過程。

圖1-4-2 高度為3的B+樹

採用B+樹的索引結構優點：

1. B+樹的高度一般為2-4層，所以查找記錄時最多隻需要2-4次IO，相對二叉平衡樹已經大大降低了。
2. 範圍查找時，能通過葉子節點的指針獲取數據。例如查找大於等於3的數據，當在葉子節點中查到3時，通過3的尾指針便能獲取所有數據，而不需要再像二叉樹一樣再獲取到3的父節點。

看到這應該明白mysql索引為什麼使用B+樹了吧