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

超過十多年行業(yè)經(jīng)驗，技術(shù)領(lǐng)先，服務(wù)至上的經(jīng)營模式，全靠網(wǎng)絡(luò)和口碑獲得客戶，為自己降低成本，也就是為客戶降低成本。到目前業(yè)務(wù)范圍包括了：網(wǎng)站建設(shè)、成都做網(wǎng)站，成都網(wǎng)站推廣，成都網(wǎng)站優(yōu)化，整體網(wǎng)絡(luò)托管，微信平臺小程序開發(fā)，微信開發(fā)，手機(jī)APP定制開發(fā)，同時也可以讓客戶的網(wǎng)站和網(wǎng)絡(luò)營銷和我們一樣獲得訂單和生意！

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

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

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

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

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

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

• 文件通用部分，用于校驗頁傳輸完整

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

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

• 文件尾（File Trailer）: 校驗頁是否完整

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

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

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

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

• 頁目錄（Page Directory）：存儲用戶記錄的相對位置

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

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

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

二叉樹的局限性

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

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

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

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

B 樹

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

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

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

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

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

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

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

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

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

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

2. 與磁盤塊 2 (8,12) 比較，位于兩者之間，繼續(xù)在指針 P2 查找，對應(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ū)別有以下幾點：

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

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

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

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

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

1. 與根節(jié)點磁盤 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)點：

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

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

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

HASH 索引

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

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

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

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

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

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

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

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

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

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

分享題目：MySQL索引結(jié)構(gòu)是怎么樣的
當(dāng)前網(wǎng)址：http://www.chinadenli.net/article12/jsgdgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、品牌網(wǎng)站制作、品牌網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、建站公司、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)