深入理解 MySQL 索引底層原理-有解無憂

一步一步推匯出 Mysql 索引的底層資料結構，

Mysql 作為互聯網中非常熱門的資料庫，其底層的存盤引擎和資料檢索引擎的設計非常重要，尤其是 Mysql 資料的存盤形式以及索引的設計，決定了 Mysql 整體的資料檢索性能，

我們知道，索引的作用是做資料的快速檢索，而快速檢索的實作的本質是資料結構，通過不同資料結構的選擇，實作各種資料快速檢索，在資料庫中，高效的查找演算法是非常重要的，因為資料庫中存盤了大量資料，一個高效的索引能節省巨大的時間，比如下面這個資料表，如果 Mysql 沒有實作索引演算法，那么查找 id=7 這個資料，那么只能采取暴力順序遍歷查找，找到 id=7 這個資料需要比較 7 次，如果這個表存盤的是 1000W 個資料，查找 id=1000W 這個資料那就要比較 1000W 次，這種速度是不能接受的，

Mysql 索引底層資料結構選型

哈希表（Hash）

哈希表是做資料快速檢索的有效利器，

哈希演算法：也叫散列演算法，就是把任意值(key)通過哈希函式變換為固定長度的 key 地址，通過這個地址進行具體資料的資料結構，

考慮這個資料庫表 user，表中一共有 7 個資料，我們需要檢索 id=7 的資料，SQL 語法是：

select  *  from user where id = 7;

哈希演算法首先計算存盤 id=7 的資料的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存盤的額資料的物理地址，通過該獨立地址可以找到對應 user_name='g'這個資料，這就是哈希演算法快速檢索資料的計算程序，

但是哈希演算法有個資料碰撞的問題，也就是哈希函式可能對不同的 key 會計算出同一個結果，比如 hash(7)可能跟 hash(199)計算出來的結果一樣，也就是不同的 key 映射到同一個結果了，這就是碰撞問題，解決碰撞問題的一個常見處理方式就是鏈地址法，即用鏈表把碰撞的資料接連起來，計算哈希值之后，還需要檢查該哈希值是否存在碰撞資料鏈表，有則一直遍歷到鏈表尾，直達找到真正的 key 對應的資料為止，

從演算法時間復雜度分析來看，哈希演算法時間復雜度為 O（1），檢索速度非常快，比如查找 id=7 的資料，哈希索引只需要計算一次就可以獲取到對應的資料，檢索速度非常快，但是 Mysql 并沒有采取哈希作為其底層演算法，這是為什么呢？

因為考慮到資料檢索有一個常用手段就是范圍查找，比如以下這個 SQL 陳述句：

select \* fromuserwhereid \>3;

針對以上這個陳述句，我們希望做的是找出 id>3 的資料，這是很典型的范圍查找，如果使用哈希演算法實作的索引，范圍查找怎么做呢？一個簡單的思路就是一次把所有資料找出來加載到記憶體，然后再在記憶體里篩選篩選目標范圍內的資料，但是這個范圍查找的方法也太笨重了，沒有一點效率而言，

所以，使用哈希演算法實作的索引雖然可以做到快速檢索資料，但是沒辦法做資料高效范圍查找，因此哈希索引是不適合作為 Mysql 的底層索引的資料結構，

二叉查找樹(BST)

二叉查找樹是一種支持資料快速查找的資料結構，如圖下所示:

二叉查找樹的時間復雜度是 O(lgn)，比如針對上面這個二叉樹結構，我們需要計算比較 3 次就可以檢索到 id=7 的資料，相對于直接遍歷查詢省了一半的時間，從檢索效率上看來是能做到高速檢索的，此外二叉樹的結構能不能解決哈希索引不能提供的范圍查找功能呢？

答案是可以的，觀察上面的圖，二叉樹的葉子節點都是按序排列的，從左到右依次升序排列，如果我們需要找 id>5 的資料，那我們取出節點為 6 的節點以及其右子樹就可以了，范圍查找也算是比較容易實作，

但是普通的二叉查找樹有個致命缺點：極端情況下會退化為線性鏈表，二分查找也會退化為遍歷查找，時間復雜退化為 O（N），檢索性能急劇下降，比如以下這個情況，二叉樹已經極度不平衡了，已經退化為鏈表了，檢索速度大大降低，此時檢索 id=7 的資料的所需要計算的次數已經變為 7 了，

在資料庫中，資料的自增是一個很常見的形式，比如一個表的主鍵是 id，而主鍵一般默認都是自增的，如果采取二叉樹這種資料結構作為索引，那上面介紹到的不平衡狀態導致的線性查找的問題必然出現，因此，簡單的二叉查找樹存在不平衡導致的檢索性能降低的問題，是不能直接用于實作 Mysql 底層索引的，

AVL 樹和紅黑樹

二叉查找樹存在不平衡問題，因此學者提出通過樹節點的自動旋轉和調整，讓二叉樹始終保持基本平衡的狀態，就能保持二叉查找樹的最佳查找性能了，基于這種思路的自調整平衡狀態的二叉樹有 AVL 樹和紅黑樹，

首先簡單介紹紅黑樹，這是一顆會自動調整樹形態的樹結構，比如當二叉樹處于一個不平衡狀態時，紅黑樹就會自動左旋右旋節點以及節點變色，調整樹的形態，使其保持基本的平衡狀態（時間復雜度為 O（logn）），也就保證了查找效率不會明顯減低，比如從 1 到 7 升序插入資料節點，如果是普通的二叉查找樹則會退化成鏈表，但是紅黑樹則會不斷調整樹的形態，使其保持基本平衡狀態，如下圖所示，下面這個紅黑樹下查找 id=7 的所要比較的節點數為 4，依然保持二叉樹不錯的查找效率，

紅黑樹擁有不錯的平均查找效率，也不存在極端的 O(n)情況，那紅黑樹作為 Mysql 底層索引實作是否可以呢？其實紅黑樹也存在一些問題，觀察下面這個例子，

紅黑樹順序插入 1~7 個節點，查找 id=7 時需要計算的節點數為 4，

紅黑樹順序插入 1~16 個節點，查找 id=16 需要比較的節點數為 6 次，觀察一下這個樹的形態，是不是當資料是順序插入時，樹的形態一直處于“右傾”的趨勢呢？從根本上上看，紅黑樹并沒有完全解決二叉查找樹雖然這個“右傾”趨勢遠沒有二叉查找樹退化為線性鏈表那么夸張，但是資料庫中的基本主鍵自增操作，主鍵一般都是數百萬數千萬的，如果紅黑樹存在這種問題，對于查找性能而言也是巨大的消耗，我們資料庫不可能忍受這種無意義的等待的，

現在考慮另一種更為嚴格的自平衡二叉樹 AVL 樹，因為 AVL 樹是個絕對平衡的二叉樹，因此他在調整二叉樹的形態上消耗的性能會更多，

AVL 樹順序插入 1~7 個節點，查找 id=7 所要比較節點的次數為 3，

AVL 樹順序插入 1~16 個節點，查找 id=16 需要比較的節點數為 4，從查找效率而言，AVL 樹查找的速度要高于紅黑樹的查找效率（AVL 樹是 4 次比較，紅黑樹是 6 次比較），從樹的形態看來，AVL 樹不存在紅黑樹的“右傾”問題，也就是說，大量的順序插入不會導致查詢性能的降低，這從根本上解決了紅黑樹的問題，

總結一下 AVL 樹的優點：

不錯的查找性能（O（logn）），不存在極端的低效查找的情況，
可以實作范圍查找、資料排序，

看起來 AVL 樹作為資料查找的資料結構確實很不錯，但是 AVL 樹并不適合做 Mysql 資料庫的索引資料結構，因為考慮一下這個問題：

資料庫查詢資料的瓶頸在于磁盤 IO，如果使用的是 AVL 樹，我們每一個樹節點只存盤了一個資料，我們一次磁盤 IO 只能取出來一個節點上的資料加載到記憶體里，那比如查詢 id=7 這個資料我們就要進行磁盤 IO 三次，這是多么消耗時間的，所以我們設計資料庫索引時需要首先考慮怎么盡可能減少磁盤 IO 的次數，

磁盤 IO 有個有個特點，就是從磁盤讀取 1B 資料和 1KB 資料所消耗的時間是基本一樣的，我們就可以根據這個思路，我們可以在一個樹節點上盡可能多地存盤資料，一次磁盤 IO 就多加載點資料到記憶體，這就是 B 樹，B+樹的的設計原理了，

B 樹

下面這個 B 樹，每個節點限制最多存盤兩個 key，一個節點如果超過兩個 key 就會自動分裂，比如下面這個存盤了 7 個資料 B 樹，只需要查詢兩個節點就可以知道 id=7 這資料的具體位置，也就是兩次磁盤 IO 就可以查詢到指定資料，優于 AVL 樹，

下面是一個存盤了 16 個資料的 B 樹，同樣每個節點最多存盤 2 個 key，查詢 id=16 這個資料需要查詢比較 4 個節點，也就是經過 4 次磁盤 IO，看起來查詢性能與 AVL 樹一樣，

但是考慮到磁盤 IO 讀一個資料和讀 100 個資料消耗的時間基本一致，那我們的優化思路就可以改為：盡可能在一次磁盤 IO 中多讀一點資料到記憶體，這個直接反映到樹的結構就是，每個節點能存盤的 key 可以適當增加，

當我們把單個節點限制的 key 個數設定為 6 之后，一個存盤了 7 個資料的 B 樹，查詢 id=7 這個資料所要進行的磁盤 IO 為 2 次，

一個存盤了 16 個資料的 B 樹，查詢 id=7 這個資料所要進行的磁盤 IO 為 2 次，相對于 AVL 樹而言磁盤 IO 次數降低為一半，

所以資料庫索引資料結構的選型而言，B 樹是一個很不錯的選擇，總結來說，B 樹用作資料庫索引有以下優點：

優秀檢索速度，時間復雜度：B 樹的查找性能等于 O（h*logn），其中 h 為樹高，n 為每個節點關鍵詞的個數；
盡可能少的磁盤 IO，加快了檢索速度；
可以支持范圍查找，

5.B+樹

B 樹和 B+樹有什么不同呢？

第一，B 樹一個節點里存的是資料，而 B+樹存盤的是索引（地址），所以 B 樹里一個節點存不了很多個資料，但是 B+樹一個節點能存很多索引，B+樹葉子節點存所有的資料，

第二，B+樹的葉子節點是資料階段用了一個鏈表串聯起來，便于范圍查找，

通過 B 樹和 B+樹的對比我們看出，B+樹節點存盤的是索引，在單個節點存盤容量有限的情況下，單節點也能存盤大量索引，使得整個 B+樹高度降低，減少了磁盤 IO，其次，B+樹的葉子節點是真正資料存盤的地方，葉子節點用了鏈表連接起來，這個鏈表本身就是有序的，在資料范圍查找時，更具備效率，因此 Mysql 的索參考的就是 B+樹，B+樹在查找效率、范圍查找中都有著非常不錯的性能，

Innodb 引擎和 Myisam 引擎的實作

Mysql 底層資料引擎以插件形式設計，最常見的是 Innodb 引擎和 Myisam 引擎，用戶可以根據個人需求選擇不同的引擎作為 Mysql 資料表的底層引擎，我們剛分析了，B+樹作為 Mysql 的索引的資料結構非常合適，但是資料和索引到底怎么組織起來也是需要一番設計，設計理念的不同也導致了 Innodb 和 Myisam 的出現，各自呈現獨特的性能，

MyISAM 雖然資料查找性能極佳，但是不支持事務處理，Innodb 最大的特色就是支持了 ACID 兼容的事務功能，而且他支持行級鎖，Mysql 建立表的時候就可以指定引擎，比如下面的例子，就是分別指定了 Myisam 和 Innodb 作為 user 表和 user2 表的資料引擎，

執行這兩個指令后，系統出現了以下的檔案，說明這兩個引擎資料和索引的組織方式是不一樣的，

Innodb 創建表后生成的檔案有：

frm:創建表的陳述句
idb:表里面的資料+索引檔案

Myisam 創建表后生成的檔案有

frm:創建表的陳述句
MYD:表里面的資料檔案（myisam data）
MYI:表里面的索引檔案（myisam index）

從生成的檔案看來，這兩個引擎底層資料和索引的組織方式并不一樣，MyISAM 引擎把資料和索引分開了，一人一個檔案，這叫做非聚集索引方式；Innodb 引擎把資料和索引放在同一個檔案里了，這叫做聚集索引方式，下面將從底層實作角度分析這兩個引擎是怎么依靠 B+樹這個資料結構來組織引擎實作的，

MyISAM 引擎的底層實作（非聚集索引方式）

MyISAM 用的是非聚集索引方式，即資料和索引落在不同的兩個檔案上，MyISAM 在建表時以主鍵作為 KEY 來建立主索引 B+樹，樹的葉子節點存的是對應資料的物理地址，我們拿到這個物理地址后，就可以到 MyISAM 資料檔案中直接定位到具體的資料記錄了，

當我們為某個欄位添加索引時，我們同樣會生成對應欄位的索引樹，該欄位的索引樹的葉子節點同樣是記錄了對應資料的物理地址，然后也是拿著這個物理地址去資料檔案里定位到具體的資料記錄，

Innodb 引擎的底層實作（聚集索引方式）

InnoDB 是聚集索引方式，因此資料和索引都存盤在同一個檔案里，首先 InnoDB 會根據主鍵 ID 作為 KEY 建立索引 B+樹，如左下圖所示，而 B+樹的葉子節點存盤的是主鍵 ID 對應的資料，比如在執行 select * from user_info where id=15 這個陳述句時，InnoDB 就會查詢這顆主鍵 ID 索引 B+樹，找到對應的 user_name='Bob'，

這是建表的時候 InnoDB 就會自動建立好主鍵 ID 索引樹，這也是為什么 Mysql 在建表時要求必須指定主鍵的原因，當我們為表里某個欄位加索引時 InnoDB 會怎么建立索引樹呢？比如我們要給 user_name 這個欄位加索引，那么 InnoDB 就會建立 user_name 索引 B+樹，節點里存的是 user_name 這個 KEY，葉子節點存盤的資料的是主鍵 KEY，注意，葉子存盤的是主鍵 KEY！拿到主鍵 KEY 后，InnoDB 才會去主鍵索引樹里根據剛在 user_name 索引樹找到的主鍵 KEY 查找到對應的資料，

問題來了，為什么 InnoDB 只在主鍵索引樹的葉子節點存盤了具體資料，但是其他索引樹卻不存具體資料呢，而要多此一舉先找到主鍵，再在主鍵索引樹找到對應的資料呢?

其實很簡單，因為 InnoDB 需要節省存盤空間，一個表里可能有很多個索引，InnoDB 都會給每個加了索引的欄位生成索引樹，如果每個欄位的索引樹都存盤了具體資料，那么這個表的索引資料檔案就變得非常巨大（資料極度冗余了），從節約磁盤空間的角度來說，真的沒有必要每個欄位索引樹都存具體資料，通過這種看似“多此一舉”的步驟，在犧牲較少查詢的性能下節省了巨大的磁盤空間，這是非常有值得的，

在進行 InnoDB 和 MyISAM 特點對比時談到，MyISAM 查詢性能更好，從上面索引檔案資料檔案的設計來看也可以看出原因：MyISAM 直接找到物理地址后就可以直接定位到資料記錄，但是 InnoDB 查詢到葉子節點后，還需要再查詢一次主鍵索引樹，才可以定位到具體資料，等于 MyISAM 一步就查到了資料，但是 InnoDB 要兩步，那當然 MyISAM 查詢性能更高，

本文首先探討了哪種資料結構更適合作為 Mysql 底層索引的實作，然后再介紹了 Mysql 兩種經典資料引擎 MyISAM 和 InnoDB 的底層實作，最后再總結一下什么時候需要給你的表里的欄位加索引吧：

較頻繁的作為查詢條件的欄位應該創建索引；
唯一性太差的欄位不適合單獨創建索引，即使該欄位頻繁作為查詢條件；
更新非常頻繁的欄位不適合創建索引，

作者：junshili

本文來自博客園，作者：古道輕風，轉載請注明原文鏈接：https://www.cnblogs.com/88223100/p/Deeply-understand-the-underlying-principles-of-MySQL-indexing.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/540690.html

標籤：其他

上一篇：以小博大外小內大,Db資料庫SQL優化之小資料驅動大資料

下一篇：以小博大外小內大,Db資料庫SQL優化之小資料驅動大資料