MySQL索引結構是什么樣的

2024-07-24 12:33:14

字體：大中小

來源：轉載

供稿：網友

　　這篇文章主要為大家展示了“MySQL索引結構是怎么樣的”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“MySQL索引結構是怎么樣的”這篇文章吧。

　　數據庫存儲單位

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

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

　　計算機系統對磁盤 I/O 會做預讀優化，當一次I/O時，除了當前磁盤地址的數據以外，還會把相鄰的數據也讀取到內存緩沖池中，每一次 I/O 讀取的數據成為一頁，InnoDB 默認的頁大小是 16KB。MySQL索引結構是怎么樣的

　　連續的 64 個頁組成一個區(Extent)，一個或多個區組成一個段(Segment)，一個或多個段組成表空間(Tablespace)。InnoDB 有兩種表空間類型，共享表空間表示多張表共享一個表空間，獨立表空間表示每張表的數據和索引全部存在獨立的表空間中。

　　數據頁的 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, 表示每個節點最多能有多少個子節點)，

　　每個磁盤塊中最多包含 k - 1 個關鍵字和 k 個子節點的指針

　　葉子節點中，只有關鍵字，沒有子節點指針

　　每個結點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小于它，而右子樹中的所有關鍵字都大于它。

　　所有葉子節點位于同一層。

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

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

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

　　與根節點磁盤塊 1 (17,35) 比較，小于 17，繼續在指針 P1 中查找，對應磁盤塊 2

　　與磁盤塊 2 (8,12) 比較，位于兩者之間，繼續在指針 P2 查找，對應磁盤塊 6

　　與磁盤塊 6 (9, 10) 比較，找到 9

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

　　B+ 樹索引

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

　　B+ 樹的構建方式是，對于父節點中的關鍵字，左子樹的所有關鍵字小于它，右子樹的所有關鍵字都大于等于它

　　非葉子節點僅用于索引，不會存儲數據記錄

　　父節點的關鍵字也會出現在子節點中，并且都是子節點中的最大值（或者最小值）

　　所有關鍵字都會出現在葉子節點中，葉子節點構成一個有序鏈表，按從小到大排序。

　　示例如下，本例中，父節點的關鍵字都是子節點中的最小值 (圖源：極客時間 SQL 必知必會)：MySQL索引結構是怎么樣的

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

　　與根節點磁盤 1 (1,18,35) 比較，16 在 1 和 18 之間，得到指針 P1，指向磁盤 2

　　找到磁盤 2 (1,8,14)，16 大于 14，得到指針P3，指向磁盤 7

　　找到磁盤 7 (14,16,17)，找到16

　　B+ 樹優點：

　　內部節點不存儲數據，因此每個內部節點可以存儲的記錄數量遠大于 B樹，樹的高度更低，I/O 更少，每次 I/O 讀取的數據頁里內容更多

　　可以支持范圍查詢，直接在葉子節點組成的有序鏈表遍歷即可

　　所有數據都存儲在葉子節點，因此查詢效率更穩定

　　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 排序。

　　由于 Hash 是精確匹配，因此也不能進行模糊查詢。

　　Hash 索引不支持聯合索引的最左匹配原則，聯合索引只有在完全匹配時生效。因為 Hash 索引計算 Hash 值的時候是將索引合并后再一起計算 Hash 值，而不會計算每個索引的單獨 Hash 值。

　　如果被索引字段的重復值很多，那就會造成大量的 Hash 沖突，這時候查詢就會變得非常耗時。

　　基于上述原因考慮，Mysql InnoDB 引擎不支持 Hash 索引，但是在內存結構中有一個自適應 Hash 索引的功能，當某個索引值使用非常頻繁的時候，會在 B+ 樹索引的基礎上自動創建一個 Hash 索引，來提高查詢性能。

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

　　以上是“MySQL索引結構是怎么樣的”這篇文章的所有內容，感謝各位的閱讀！

（編輯：武林網）

上一篇：MySQL中update語句的執行過程是咋樣的

下一篇：MySQL索引的優劣勢是什么