深入了解MySQL索引結構

本篇文章為大家帶來了關於mysql的相關知識，其中主要介紹了關於索引結構的相關問題，那麼，索引的結構是什麼樣的呢？為什麼索引可以這麼快？下面一起來看看吧，希望對大家有幫助。

推薦學習：mysql教學

#資料庫儲存單位

首先我們要知道，由於為了實現持久化，只能將索引儲存在硬碟上，透過索引來進行查詢的時候就會產生硬碟的I/O 操作，因此，設計索引時需要盡可能減少的查找次數，從而減少I/O 耗時。

此外還需要知道一個很重要的原理：資料庫管理儲存空間的基本單位是頁(Page)，一個頁中儲存多條行記錄(Row)。

電腦系統對磁碟I/O 會做預讀優化，當一次I/O時，除了目前磁碟位址的資料以外，還會將相鄰的資料也讀取到記憶體緩衝池中，每一次I/O 讀取的資料成為一頁，InnoDB 預設的頁大小是16KB。
連續的64 個頁組成一個區(Extent)，一個或多個區組成一個段(Segment)，一個或多個段組成表空間(Tablespace)。 InnoDB 有兩種表空間類型，共享表空間表示多張表共享一個表空間，獨立表空間表示每張表的資料和索引全部存在獨立的表空間中。

資料頁結構如下（圖來源：極客時間《MySQL 必知必會》）：

資料頁的7 個結構內容可以大致分為以下三類：

• 檔案通用部分，用於校驗頁傳輸完整
  • 檔案頭（File Header）: 表述頁訊息，檔案頭中使用FIL_PAGE_PREV 和FIL_PAGE_NEXT 構成雙向鍊錶，分別指向前後的數據頁。
  • 頁頭（File Header）：記錄頁的狀態資訊
  • 檔案尾（File Trailer）: 校驗頁是否完整
• 記錄部分，用於儲存資料記錄
  • 最大最小記錄（Infimum/Supremum）：虛擬的行記錄，表示資料頁的最大記錄和最小記錄。
  • 使用者記錄（User Record）和空閒空間（Free Space）: 用於儲存資料行記錄內容
• 索引部分，用於提高記錄的檢索效率
  • 頁目錄（Page Directory）：儲存使用者記錄的相對位置

#詳情可參考淘寶的資料庫核心月報

索引數據結構

很自然的，我們會想到尋找演算法中涉及到的一些常用資料結構，例如二元查找樹，二叉平衡樹等等，實際上，Innodb 的索引是用B樹 來實現的，下面我們來看看為何會選擇這個索引結構。

二元樹的限制

先簡單回顧一下二元搜尋樹（Binary Search Tree）的定義，在二叉搜尋樹中，如果要尋找的key 大於根節點，則在右子樹中搜索，如果key 小於根節點，則在左子樹中搜索，直到找到key 為止，時間複雜度為O(logn)。例如數列[4,2,6,1,3,5,7]，會產生如下二元搜尋樹：

但是在某些特殊情況下，二元樹的深度會非常大，例如[1,2,3,4,5,6,7]，則會產生如下的樹：

在下面這種情況中，最壞的情況下需要查7 次才能夠查到想要的結果，查詢時間變成了O(n)。

為了優化這個情況，就有了平衡二元搜尋樹（AVL 樹），AVL 樹是指左右子樹的高度相差不超過1 的樹，搜尋時間複雜度為O(logn) ，這已經是比較理想的搜尋樹了，但是在動輒幾千萬行記錄的資料庫中，樹的深度還是會很高，依然不是最理想的結構。

B 樹

那麼，如果從二元樹擴展到N 叉樹呢，很容易想像到，N 叉樹可以大大的減少樹的深度，實際上，4 層樹結構就已經可以支撐幾十T 的數據了。

B 樹（Balance Tree）就是這樣的一種N 叉樹， B 樹也稱為B- 樹，滿足如下定義：
設k 為B 樹的度(degree, 表示每個節點最多能有多少個子節點)，

1. 每個磁碟區塊中最多包含k - 1 個關鍵字和k 個子節點的指標
2. 葉子節點中，只有關鍵字，沒有子節點指標
3. 每個結點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小於它，而右子樹中的所有關鍵字都大於它。
4. 所有葉子節點位於同一層。

上面已經提到，每一次I/O 會預讀一個磁碟區塊的數據，大小為一頁，用一個磁碟區塊的內容表示一次I/O，B 樹的結構如下圖(圖源：極客時間SQL 必知必會)：

B 樹也是有順序的，由於子節點指標一定比關鍵字多1，所以剛好可以用關鍵字劃分子節點的區段，如圖中的例子，每個節點有2 個關鍵字，3 個子節點，如磁碟區塊2 ，第一個字節點的關鍵字3，5 小於自身的第一個子節點8 ，第二個子節點的9，10 在8 和12 之間，第三個子節點的值13，15 大於自身的第二個子節點12。

假設我們現在要查找9，步驟如下：

1. 與根節點磁碟區塊1 (17,35) 比較，小於17，繼續在指標P1 中查找，對應磁碟區塊2
2. 與磁碟區塊2 (8,12) 比較，位於兩者之間，繼續在指標P2 中查找，對應磁碟區塊6
3. 與磁碟區塊6 (9, 10)比較，找到9

可以看到，雖然做了很多次比較的操作，但是由於進行了預讀，所以在磁碟區塊內部的比較是在記憶體中進行的，不耗費磁碟I/O，上述操作只需要進行3 次I/O 即可完成，已經是比較理想的結構了。

B 樹索引

B 樹在B 樹的基礎上進行了進一步的改進，B 樹和B 樹的差異有以下幾點：

## B 樹的建構方式是，對於父節點中的關鍵字，左子樹的所有關鍵字小於它，右子樹的所有關鍵字都大於等於它
1. 非葉子節點僅用於索引，不會儲存資料記錄
2. 父節點的關鍵字也會出現在子節點中，而且都是子節點中的最大值（或最小值）
3. 所有關鍵字都會出現在在葉子節點中，葉子節點構成一個有序鍊錶，按從小到大排序。

範例如下，本例中，父節點的關鍵字都是子節點中的最小值(圖源：極客時間SQL 必知必會)：

假設若要找出關鍵字16，找出步驟如下：

與根節點磁碟1 (1,18,35) 比較，16 在1 和18 之間，得到指標P1，指向磁碟2
1. 找到磁碟2 (1,8,14)，16 大於14，得到指標P3，指向磁碟7
2. 找到磁碟7 (14,16,17)，找出16

#B 樹優點：

內部節點不儲存數據，因此每個內部節點可以儲存的記錄數量遠大於B樹，樹的高度更低，I/O 更少，每次I/O 讀取的資料頁裡內容更多
1. 可以支援範圍查詢，直接在葉子節點組成的有序鍊錶遍歷即可
2. 所有資料都儲存在葉子節點，因此查詢效率更穩定

HASH 索引

MySQL 的memory 儲存引擎預設的索引結構是Hash 索引，Hash 是一種函數， 稱為雜湊函數，透過特定演算法（如MD5, SHA1，SHA2 等）將任意長度的輸入轉換為固定長度的輸出，輸入和輸出一一對應，本文不會對hash 函數做深入的介紹，詳情請參考百度百科。

Hash 查找的效率為O(1)，效率非常高，python 的dict，golang 中的map，java 中的hash map 都是基於hash 實現的，在Redis 這樣的Key-Value 資料庫也是由Hash 實現。

對於精確查找而言，Hash 索引的效率會比 B 樹索引更高，但是 Hash 索引有一些局限性，因此不是最主流的索引結構。

因為 Hash 索引所指向的資料是無序的，所以Hash 索引不能範圍查詢，也不支援 ORDER BY 排序。
1. 由於 Hash 是精確匹配，因此也不能進行模糊查詢。
2. Hash 索引不支援聯合索引的最左匹配原則，聯合索引只有在完全匹配時生效。因為 Hash 索引計算 Hash 值的時候是將索引合併後再一起計算 Hash 值，而不會計算每個索引的單獨 Hash 值。
3. 如果被索引欄位的重複值很多，那就會造成大量的 Hash 衝突，這時候查詢就會變得非常耗時。

基於上述原因考慮，Mysql InnoDB 引擎不支援Hash 索引，但是在記憶體結構中有一個自適應Hash 索引的功能，當某個索引值使用非常頻繁的時候，會在B樹索引的基礎上

自動建立一個Hash 索引，來提高查詢效能。

自適應 Hash 索引可以理解為一種 “索引的索引”，採用 Hash 索引儲存 B 樹索引中的頁面位址，迅速定位到對應的葉子節點。可以透過 innodb_adaptive_hash_index 變數來查看。

推薦學習：mysql教學

以上是深入了解MySQL索引結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！