MySQL索引結(jié)構(gòu)是怎么樣的

這篇文章主要為大家展示了“MySQL索引結(jié)構(gòu)是怎么樣的”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“MySQL索引結(jié)構(gòu)是怎么樣的”這篇文章吧。

數(shù)據(jù)庫(kù)存儲(chǔ)單位

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

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

計(jì)算機(jī)系統(tǒng)對(duì)磁盤 I/O 會(huì)做預(yù)讀優(yōu)化，當(dāng)一次I/O時(shí)，除了當(dāng)前磁盤地址的數(shù)據(jù)以外，還會(huì)把相鄰的數(shù)據(jù)也讀取到內(nèi)存緩沖池中，每一次 I/O 讀取的數(shù)據(jù)成為一頁(yè)，InnoDB 默認(rèn)的頁(yè)大小是 16KB。
連續(xù)的 64 個(gè)頁(yè)組成一個(gè)區(qū)(Extent)，一個(gè)或多個(gè)區(qū)組成一個(gè)段(Segment)，一個(gè)或多個(gè)段組成表空間(Tablespace)。InnoDB 有兩種表空間類型，共享表空間表示多張表共享一個(gè)表空間，獨(dú)立表空間表示每張表的數(shù)據(jù)和索引全部存在獨(dú)立的表空間中。

數(shù)據(jù)頁(yè)結(jié)構(gòu)如下（圖源：極客時(shí)間《MySQL 必知必會(huì)》）：

數(shù)據(jù)頁(yè)的 7 個(gè)結(jié)構(gòu)內(nèi)容可以大致分為以下三類：

• 文件通用部分，用于校驗(yàn)頁(yè)傳輸完整

• 文件頭（File Header）: 表述頁(yè)信息，文件頭中使用 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 構(gòu)成一個(gè)雙向鏈表，分別指向前后的數(shù)據(jù)頁(yè)。

• 頁(yè)頭（File Header）：記錄頁(yè)的狀態(tài)信息

• 文件尾（File Trailer）: 校驗(yàn)頁(yè)是否完整

• 記錄部分，用于存儲(chǔ)數(shù)據(jù)記錄

• 最大最小記錄（Infimum/Supremum）：虛擬的行記錄，表示數(shù)據(jù)頁(yè)的最大記錄和最小記錄。

• 用戶記錄（User Record）和空閑空間（Free Space）: 用于存儲(chǔ)數(shù)據(jù)行記錄內(nèi)容

• 索引部分，用于提高記錄的檢索效率

• 頁(yè)目錄（Page Directory）：存儲(chǔ)用戶記錄的相對(duì)位置

詳情可參考淘寶的數(shù)據(jù)庫(kù)內(nèi)核月報(bào)

索引數(shù)據(jù)結(jié)構(gòu)

很自然的，我們會(huì)想到查找算法中涉及到的一些常用數(shù)據(jù)結(jié)構(gòu)，比如二叉查找樹，二叉平衡樹等等，實(shí)際上，Innodb 的索引是用 B+ 樹 來實(shí)現(xiàn)的，下面我們來看看為何會(huì)選擇這種索引結(jié)構(gòu)。

二叉樹的局限性

先來簡(jiǎn)單回顧一下二叉搜索樹（Binary Search Tree）的定義，二叉搜索樹中，如果要查找的 key 大于根節(jié)點(diǎn)，則在右子樹中搜索，如果 key 小于根節(jié)點(diǎn)，則在左子樹中搜索，直到找到 key 為止，時(shí)間復(fù)雜度為 O(logn)。比如數(shù)列 [4,2,6,1,3,5,7]，會(huì)生成如下二叉搜索樹：

但是在某些特殊情況下，二叉樹的深度會(huì)非常大，比如 [1,2,3,4,5,6,7]，則會(huì)生成如下的樹：

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

為了優(yōu)化這種情況，就有了平衡二叉搜索樹（AVL 樹），AVL 樹是指左右子樹的高度相差不超過 1 的樹，搜索時(shí)間復(fù)雜度為 O(logn)，這已經(jīng)是比較理想的搜索樹了，但是在動(dòng)輒幾千萬行記錄的數(shù)據(jù)庫(kù)中，樹的深度還是會(huì)很高，依然不是最理想的結(jié)構(gòu)。

B 樹

那么，如果從二叉樹擴(kuò)展到 N 叉樹呢，很容易想象到，N 叉樹可以大大的減少樹的深度，實(shí)際上，4 層樹結(jié)構(gòu)就已經(jīng)可以支撐幾十 T 的數(shù)據(jù)了。

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

1. 每個(gè)磁盤塊中最多包含 k - 1 個(gè)關(guān)鍵字 和 k 個(gè)子節(jié)點(diǎn)的指針

2. 葉子節(jié)點(diǎn)中，只有關(guān)鍵字，沒有子節(jié)點(diǎn)指針

3. 每個(gè)結(jié)點(diǎn)中的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它。

4. 所有葉子節(jié)點(diǎn)位于同一層。

上面已經(jīng)提到，每一次 I/O 會(huì)預(yù)讀一個(gè)磁盤塊的數(shù)據(jù)，大小為一頁(yè)，用一個(gè)磁盤塊的內(nèi)容表示一次 I/O，B 樹的結(jié)構(gòu)如下圖 (圖源：極客時(shí)間 SQL 必知必會(huì))：

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

假設(shè)我們現(xiàn)在要查找 9，步驟如下：

1. 與根節(jié)點(diǎn)磁盤塊 1 (17,35) 比較，小于 17，繼續(xù)在指針 P1 中查找，對(duì)應(yīng)磁盤塊 2

2. 與磁盤塊 2 (8,12) 比較，位于兩者之間，繼續(xù)在指針 P2 查找，對(duì)應(yīng)磁盤塊 6

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

可以看到，雖然做了很多次比較的操作，但是由于進(jìn)行了預(yù)讀，所以在磁盤塊內(nèi)部的比較是在內(nèi)存中進(jìn)行的，不耗費(fèi)磁盤 I/O，上述操作只需要進(jìn)行 3 次 I/O 即可完成，已經(jīng)是比較理想的結(jié)構(gòu)了。

B+ 樹索引

B+ 樹在 B 樹的基礎(chǔ)上進(jìn)行了進(jìn)一步的改進(jìn)，B+ 樹和 B 樹的區(qū)別有以下幾點(diǎn)：

1. B+ 樹的構(gòu)建方式是，對(duì)于父節(jié)點(diǎn)中的關(guān)鍵字，左子樹的所有關(guān)鍵字小于它，右子樹的所有關(guān)鍵字都大于等于它

2. 非葉子節(jié)點(diǎn)僅用于索引，不會(huì)存儲(chǔ)數(shù)據(jù)記錄

3. 父節(jié)點(diǎn)的關(guān)鍵字也會(huì)出現(xiàn)在子節(jié)點(diǎn)中，并且都是子節(jié)點(diǎn)中的最大值（或者最小值）

4. 所有關(guān)鍵字都會(huì)出現(xiàn)在葉子節(jié)點(diǎn)中，葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，按從小到大排序。

示例如下，本例中，父節(jié)點(diǎn)的關(guān)鍵字都是子節(jié)點(diǎn)中的最小值 (圖源：極客時(shí)間 SQL 必知必會(huì))：
假設(shè)要查找關(guān)鍵字 16，查找步驟如下：

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

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

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

B+ 樹優(yōu)點(diǎn)：

1. 內(nèi)部節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，因此每個(gè)內(nèi)部節(jié)點(diǎn)可以存儲(chǔ)的記錄數(shù)量遠(yuǎn)大于 B樹，樹的高度更低，I/O 更少，每次 I/O 讀取的數(shù)據(jù)頁(yè)里內(nèi)容更多

2. 可以支持范圍查詢，直接在葉子節(jié)點(diǎn)組成的有序鏈表遍歷即可

3. 所有數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)，因此查詢效率更穩(wěn)定

HASH 索引

MySQL 的 memory 存儲(chǔ)引擎默認(rèn)的索引結(jié)構(gòu)是 Hash 索引，Hash 是一種函數(shù)， 稱為散列函數(shù)，通過特定算法（如 MD5, SHA1，SHA2 等）將任意長(zhǎng)度的輸入轉(zhuǎn)換為固定長(zhǎng)度的輸出，輸入和輸出一一對(duì)應(yīng)，本文不會(huì)對(duì) hash 函數(shù)做深入的介紹，詳情請(qǐng)參考 百度百科。

Hash 查找的效率為 O(1)，效率非常高，python 的 dict，golang 中的 map，java 中的 hash map 都是基于 hash 實(shí)現(xiàn)的，在 Redis 這樣的 Key-Value 數(shù)據(jù)庫(kù)也是由 Hash 實(shí)現(xiàn)。

對(duì)于精確查找而言，Hash 索引的效率會(huì)比 B+ 樹索引更高，但是 Hash 索引有一些局限性，因此不是最主流的索引結(jié)構(gòu)。

1. 因?yàn)?Hash 索引指向的數(shù)據(jù)是無序的，所以Hash 索引不能范圍查詢，也不支持 ORDER BY 排序。

2. 由于 Hash 是精確匹配，因此也不能進(jìn)行模糊查詢。

3. Hash 索引不支持聯(lián)合索引的最左匹配原則，聯(lián)合索引只有在完全匹配時(shí)生效。因?yàn)?Hash 索引計(jì)算 Hash 值的時(shí)候是將索引合并后再一起計(jì)算 Hash 值，而不會(huì)計(jì)算每個(gè)索引的單獨(dú) Hash 值。

4. 如果被索引字段的重復(fù)值很多，那就會(huì)造成大量的 Hash 沖突，這時(shí)候查詢就會(huì)變得非常耗時(shí)。

基于上述原因考慮，Mysql InnoDB 引擎不支持 Hash 索引，但是在內(nèi)存結(jié)構(gòu)中有一個(gè)自適應(yīng) Hash 索引的功能，當(dāng)某個(gè)索引值使用非常頻繁的時(shí)候，會(huì)在 B+ 樹索引的基礎(chǔ)上自動(dòng)創(chuàng)建一個(gè) Hash 索引，來提高查詢性能。

自適應(yīng) Hash 索引可以理解為一種 “索引的索引”，采用 Hash 索引儲(chǔ)存 B+ 樹索引中的頁(yè)面地址，迅速定位到對(duì)應(yīng)的葉子節(jié)點(diǎn)?？梢酝ㄟ^ innodb_adaptive_hash_index 變量來查看。

以上是“MySQL索引結(jié)構(gòu)是怎么樣的”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！