再有人問你MySQL索引原理，就把這篇文章甩給他

索引圖什麼意思

索引，可能讓好很多人望而生畏，畢竟每次面試時候 MySQL 的索引一定是必問內容，哪怕先撇開面試，就在平常的開發中，對於 SQL 的最佳化也而是重中之重。

可以毫不誇張的說，系統中 SQL 的好壞，是能直接決定你係統的快慢的。但是在最佳化之前大家是否想過一個問題？那就是：我們最佳化的原則是什麼？最佳化SQL的理論基礎是什麼？

雖然說實踐出真知，但是我更相信理論是支撐實踐的基礎，因為我們不可能毫無目的的去盲目的實踐，因為這樣往往事倍功半。

所以說了這麼多隻想告訴大家，在真正的開始索引最佳化之前，我們需要徹底搞明白索引的原理。這樣再談最佳化你將覺得更絲滑~

1、索引的本質

索引的本質是一種排好序的資料結構。這個我相信其實大家並不陌生，因為談到索引很多人自然而然的就會聯想到字典中的目錄。

沒錯，這樣的類比是很形象的，但是如果再往深處說，恐怕很多小夥伴就有點張口結舌了，那既然你已經知道了索引的本質，那麼您就已經有了看這篇文章的基礎，相信讀文字文的你，一定會對索引的原理有一個全新的瞭解。

2、索引的分類

在資料庫中，索引是分很多種類的（千萬不要狹隘的認為索引只有 B+ 樹，那是因為我們平時使用的基本都是 MySQL）。而不同的種類很顯然是為了應付不同的場合，那索引到底有那些種類呢？下面就讓我們來大致的瞭解下。

2。1、Hash 索引

Hash 索引是比較常見的一種索引，他的單條記錄查詢的效率很高，時間複雜度為1。但是，Hash索引並不是最常用的資料庫索引型別，尤其是我們常用的Mysql Innodb引擎就是不支援hash索引的。主要有以下原因：

Hash索引適合精確查詢，但是範圍查詢不適合

* 因為儲存引擎都會為每一行計算一個hash碼，hash碼都是比較小的，並且不同鍵值行的hash碼通常是不一樣的，hash索引中儲存的就是Hash碼，hash 碼彼此之間是沒有規律的，且 Hash 操作並不能保證順序性，所以值相近的兩個資料，Hash值相差很遠，被分到不同的桶中。這就是為什麼hash索引只能進行全職匹配的查詢，因為只有這樣，hash碼才能夠匹配到資料。

對於 hash 索引，小夥伴們只需要瞭解到這裡就可以了。

2。2、二叉樹

另外，常見的索引使用的資料結構是樹結構，首先我們來介紹下最經典的二叉樹。

先來介紹下二叉樹的特點：

1。 二叉樹的時間複雜度為 O（n）

1。 一個節點只能有兩個子節點。即度不超過2

1。 左子節點 小於 本節點，右子節點 大於 本節點

首先來看一下二叉樹的樣子

但是在極端情況下會出現鏈化的情況，即節點一直在某一邊增加。如下圖

二叉樹中，有一種特殊的結構——平衡二叉樹，平衡二叉樹的特點：

1。 根節點會隨著資料的改變而變更

1。 資料量越多，遍歷次數越多，IO次數就越多，就越慢（磁碟的IO由樹高決定）

2。4、B樹（二三樹）

瞭解了二叉樹之後，可以進一步談一下什麼是B樹了。B 樹大概是這樣子的：

從B樹的結構圖中可以看到每個節點中不僅包含資料的 key 值，還有 data 值。

而每頁的儲存空間是有限的，如果 data 比較大，會導致每個節點的 key 儲存的較少，當資料量較大的時候，同樣會導致B樹很深，從而增加了磁碟 IO 的次數，進而影響查詢效率。

好了，說到這裡，常見的索引的種類也說完了，上面的內容僅僅是作為一個鋪墊，下面我們正式開始 MySQL 的 B+ 樹。

2。5、B+樹

MySQL 中最常用的索引的資料結構是 B+ 樹，他有以下特點：

在 B+ 樹中，所有資料記錄節點都是按照鍵值的大小存放在同一層的葉子節點上，而非葉子結點只儲存key的資訊，這樣可以大大減少每個節點的儲存的key的數量，降低B+ 樹的高度

B+ 樹葉子節點的關鍵字從小到大有序排列，左邊結尾資料都會儲存右邊節點開始資料的指標。

B+ 樹的層級更少：相較於 B 樹 B+ 每個非葉子節點儲存的關鍵字數更多，樹的層級更少所以查詢資料更快

B+ 樹查詢速度更穩定：B+ 所有關鍵字資料地址都存在葉子節點上，所以每次查詢的次數都相同所以查詢速度要比B樹更穩定；

B+ 樹天然具備排序功能：B+ 樹所有的葉子節點資料構成了一個有序連結串列，在查詢大小區間的資料時候更方便，資料緊密性很高，快取的命中率也會比B樹高。

B+ 樹全節點遍歷更快：B+ 樹遍歷整棵樹只需要遍歷所有的葉子節點即可，，而不需要像 B 樹一樣需要對每一層進行遍歷，這有利於資料庫做全表掃描。

好了說了這麼多的 B+ 樹的特點，我們來張圖看看 B+ 樹到底長什麼樣子（如果看不懂，也沒有關係，下文會一步一步解釋說明的）

上面的資料頁就是實際存放資料頁的地方，且資料頁之間是透過雙向連結串列進行連線的，好了到這裡我們就將各個索引的型別快速瞭解了下，下面我們就開始正式B+樹的分析。

3、主鍵目錄

我們將上圖中的資料頁拿出來再細化下，就成了下面的這張圖

我們都知道 MySQL 在儲存資料的時候是以

資料頁

為最小單位的，且資料在資料頁中的儲存是

連續

的，資料頁中的資料是按照主鍵排序的（沒有主鍵是由 MySQL自己維護的 ROW_ID 來排序的），資料頁和資料頁之間是透過

雙向連結串列

來關聯的，資料與資料時間是透過

單向連結串列

來關聯的。

也就是說有一個在每個資料頁中，他必然就有一個最小的主鍵，然後每個資料頁的頁號和最小的主鍵會組成一個

主鍵目錄

（就像上圖中的左邊部分），假設現在要查詢主鍵為 2 的資料，透過二分查詢法最後確定下主鍵為 2 的記錄在資料頁 1 中，此時就會定位到資料頁 1 接著再去定位主鍵為 2 的記錄，我們先知道大致的流程，細節先不要深究，先從宏觀看結構原理，再到微觀看實現原理。

剛剛上面是說的其實可以理解為是主鍵索引，主鍵索引也是最簡單的最基礎的索引。這個時候大家應該知道為什麼你建立了主鍵查詢就能變快了吧？

4、索引頁

但是現在假設有很多很多的是資料頁，那是不是對應的主鍵目錄會很大很大呢？

那假設有1000萬條記錄、5000萬條記錄呢？是不是就算是二分法查詢，其效率也依舊是很低的，所以為了解決這種問題 MySQL 又設計出了一種新的儲存結構—

索引頁

。例如有下面這樣情況，

假設上面的主鍵目錄中的記錄是非常非常多的，此時上面的結構是演變成這樣子的，MySQL 會將裡面的記錄拆分到不同的索引頁中，也就是下面這樣子的

索引頁中記錄的是每頁資料頁的頁號和該資料頁中最小的主鍵的記錄，也就是說最小主鍵和資料頁號不是單純的維護在主鍵目錄中了，而是演變成了索引頁，索引頁和資料頁類似，一張不夠存就分裂到下一張。

假如現在要查詢 id=20 的這條記錄，咦？那我應該到哪個索引頁中查詢該條記錄呢？所以這個時候肯定是需要去維護索引頁的。

沒錯，MySQL 也是這麼設計的，也就是說 MySQL 同時也設計出了用於維護索引頁的資料結構，其實也還叫

索引頁

，只不過他們是在不同的層級，類似下面這樣子的：

也就是說

維護索引頁的索引頁

是在真正

儲存記錄和資料頁的索引頁

的上一層，現在如果你想查詢 id=20 的這條記錄，那就是從最上層的索引頁開始查詢，透過二分法查詢，很快就能夠定位到 id=20 s這條記錄是在索引頁 2 上，然後到就索引頁 2 上面查詢，接著就是和之前一樣了（注意，索引頁中的記錄也是透過單向連結串列連線的），根據各個最小的主鍵能夠定位到 id=20 是在資料頁5上，假設資料頁5是這樣子的

那這個時候你是不是能夠想明白資料是怎麼定位的了呢？

5、索引頁的分層

好，既然你已經知道到索引頁太多會往上一層擴散，那現在假設上一層的索引頁記錄也太多了，那該怎麼辦？很簡單，繼續分裂，再往上一層繼續，不廢話，我來畫圖幫助大家理解

我看明白了，你看明白了嗎？我們來模擬一個查詢的過程，假設你要查詢 37 這條記錄，說實話我根本不知道這條記錄在哪裡。好，現在我們就來模擬 MySQL 的查詢過程，首先從

最頂層的索引頁

開始查詢，因為 id=37，因此定位到了索引頁16，然後到索引頁 16 中繼續查詢，此時同樣能夠定位到 id=37 在索引頁 3 中，然後繼續查詢，最終能夠定位到資料實在資料頁 8 中，假設資料頁 8 是這樣子的

是不是很完美？如果非要我把上面的圖畫完整，那…。小弟義不容辭（圖太大了，索引頁中資料的連結串列結構就不畫出來了）

這個時候機智的你是不是已經發現了什麼小秘密？他是不是很像一顆二叉樹？實際上這就是一顆 B+ 樹的結構，這也是資料在磁碟中真正儲存的物理結構。B+樹的特性是什麼呢？B+樹，也是二叉搜尋樹的一種，但是他的資料僅僅儲存在葉子節點（在這裡就是資料頁），像這種

索引頁+資料頁

組成的組成的B+樹就是

聚簇索引

（這句話很重要）。

聚簇索引是 MySQL 基於主鍵索引結構建立的

6、非主鍵索引

但是現在問題又來了，既然這裡強調的是

主鍵索引

，那我們平時開發中除了主鍵索引其他的索引也用的不少，這時候該怎麼辦？假設你現在 對

name

、

age

建立索引。現在回顧下主鍵索引，是不是在插入資料的時候基於主鍵的順序去維護一個 B+ 樹的？

而實際上非主鍵索引其原理是一樣的，MySQL 都是去維護一顆 B+ 樹，說白了，你建立多少個索引，MySQL 就會幫你維護多少的B+樹（這下是不是也突然想明白了為什麼索引不能建立太多了？以前就知道不能建立太多索引，因為索引也會佔用空間，實際上這就是根本原因）

假如現在真的對 name+age 建立索引，那此時是存放的呢？此時 MySQL 根據會 name+age 維護一個單獨的 B+ 樹結構，資料依舊是存放在資料頁中的，只不過是原來資料中的每條記錄寫的是 id=xx，現在寫的是name=xx，age=xx，id=xx，不管怎麼樣，主鍵肯定會存放的，先來張圖壓壓驚

在插入資料的時候，MySQL 首先會根據 name 進行排序，如果 name 一樣，就根據聯合索引中的 age 去排序，如果還一樣，那麼就會根據 主鍵 欄位去排序。插入的原理就是這樣子的。

此時每個資料頁中的記錄存放的實際是

索引欄位

和主鍵欄位，而其他欄位是不存的（為什麼不存放？一樣的資料到處存放很浪費空間的，也沒必要，所以才會有下面的索引最佳化），至於查詢，原理和過程跟聚簇索引一樣，這裡就不再贅述，但是，下面說的內容卻是至關重要的：假設現在執行這樣的SQL：

SELECT name FROM student WHERE name=‘wx’

那麼此時的查詢是完美的，使用到了索引且不需要

回表

7.回表

是這樣子的，現在要根據 name 查詢到該條記錄，且查詢的欄位（即 select 後面的查詢欄位）也僅僅有 name（只要是在 name，age，id 這三個欄位中都可以）這個時候是能夠直接獲取到最終的記錄的

換句話說，因為聯合索引中的記錄也僅僅有 name，age，id，所以在查詢的如果也僅僅查詢這三個欄位，那麼在該B+樹中就能夠查詢到想要的結果了。

那現在假設查詢的 SQL 是這樣子的（我們假設 student 中還有除了name，age，id 其他的欄位 ）

SELECT * FROM student WHERE name=‘wx’

那這下子就完蛋了，因為你現在雖然根據 name 很快的定位到了該條記錄，但是因為 name+age 不是聚簇索引，此時的 B+ 樹的資料頁中存放的僅僅是自己關聯的索引和主鍵索引欄位，並不會存其他的欄位，所以這個時候其他的屬性值是獲取不到的，這時候該怎麼辦？

這種情況下，MySQL 就需要進行

回表

查詢了。此時 MySQL 就會根據定位到的某條記錄中的 id 再次進行聚簇索引查詢，也就是說會根據 id 去維護 id 的那麼 B+ 樹中查詢。因為聚簇索引中資料頁記錄的是一條記錄的完整的記錄，這個過程就叫

回表

。

再強調下回表的含義：

根據非主鍵索引查詢到的結果並沒有查詢的欄位值，此時就需要再次根據主鍵從聚簇索引的根節點開始查詢，這樣再次查詢到的記錄才是完成的。

最後，讓我一起看下 MySQL 對於非主鍵索引的維護過程：

對於非主鍵索引（一般都是聯合索引），在維護 B+ 樹的時候，會根據聯合索引的欄位依次去判斷，假設聯合索引為：name + address + age，那麼 MySQL 在維護該索引的 B+ 樹的時候，首先會根據 name 進行排序，name 相同的話會根據第二個 address 排序，如果 address 也一樣，那麼就會根據 age 去排序，如果 age 也一樣，那麼就會根據主鍵欄位值去排序，且對於非主鍵索引，MySQL 在維護 B+ 樹的時候，僅僅是維護索引欄位和主鍵欄位。