Mysql索引簡明教程

來自專欄 Beautiful Java63 人贊了文章

在絕大多數情況下，Mysql索引都是基於B+樹的，而索引可以提高數據查詢的效率。

但是Mysql是如何利用B+樹進行查詢的呢？索引的作用只是提高查詢效率嗎？

Mysql中的B+Tree索引

假設有一張教師表，裡面有教師編號、名字、學科、薪資四個欄位。

當你執行下面這條創建索引的sql語句時：

create index id_name on teacher(name);

Mysql就會在磁碟中構建這樣一顆B+樹：

這樣一棵樹有什麼用呢？首先當然是加速查詢。

舉個簡單的例子，假設現在要查找名字為「Mozart」的教師的數據：

select * from teacher where name = "Mozart";

既然我們已經建立了B+樹，那麼就要好好利用它來加速查詢，而不是傻傻的去遍歷整張表。

從根節點開始，我們發現，根節點就是」Mozart」，不過很可惜，根節點上面只有name欄位的信息，沒有其他欄位的數據。

這是B+樹的一個特點——只有葉子節點（leaf nodes）會指向行數據。

我們比較了要查找的值和搜索碼值，發現相等，於是跳到搜索碼右邊的指針指向的節點，也就是「Srinivasan」所在的節點（注意，這裡的節點是指下圖紅色框畫出的區域）。

接著，我們遍歷當前節點的搜索碼值，和要查找的值做比較。

我們發現「Srinivasan」已經大於我們要查找的」Mozart」了，於是就此止步，跟隨著「Srinivasan」左邊的指針，跳到下一級的節點。

接著，還是一樣，我們繼續遍歷當前節點的搜索碼值，和要查找的值做比較。

這時我們又碰到了一個搜索碼值為」Mozart」的塊，和上次不同的是，這次是在葉子節點找到的，而不是根節點。葉子節點的指針指向行數據。

於是，我們循著」Mozart」左邊指針的指引，找到了」Mozart」的行數據。

當然，這只是最最簡潔的描述，如果name沒有加唯一索引，那麼mysql還需要遍歷下一個塊，看看搜索碼值是不是也是」Mozart」。另外，葉子節點也不會直接存儲行數據的位置，而是存儲聚簇索引（clustered index）的值，通過聚簇索引去找到數據的位置，這個在後面會解釋。

通過上面的描述，大家大概對B+樹的查找原則有了一定的了解：

• 從節點最左邊的搜索碼值開始，向右遍歷
• 如果搜索碼值大於被查找值，則跳到搜索碼值左邊指針指向的節點
• 如果等於，則跳到右邊指針指向的節點
• 如果小於，則遍歷下一個搜索碼值
• 如果遍歷完了整個節點，還是沒發現有大於等於被查找值的搜索碼，則跳到該節點最後一個非空指針指向的節點
• 不斷循環，直到找到被查找值，或者發現被查找值不存在

作為測驗，大家可以模擬上面查找」Mozart」的過程，試著查找」Brandt」和「El Said」。

複合索引

上面講的只是單索引，那麼如果是複合索引呢？

create index id_name_subject on teacher(name, subject);

一樣的，只是這次的搜索碼值，不再只是存放name一個欄位，而是存放了name和subject兩個欄位。

熟悉Java的同學，可以理解為，之前只是一個字元串，現在變成了一個Object了。

之前只是單純的字元串比較，現在是對象間的比較。

對象怎麼比較呢？一項項來，如果前一項分不出勝負，那麼再比下一項。

比較的順序，就是你索引創建語句里寫的順序。

比如按照上面那條sql創建出來的索引，mysql會先比較name，如果name一樣，再比較subject。

其他查找原則，和單索引一致。

最左前綴匹配

弄懂了單索引和複合索引的原理，再來理解Mysql中經常被提及的——最左前綴匹配（leftmost prefix），就輕鬆的多了。

什麼是最左前綴匹配？簡單說，就是你給一個表的a，b，c三個欄位建了索引：

create index id_a_b_c on foo(a, b, c);

那麼當你where條件是a或者a、b或者a、b、c時，都可以命中索引，除此之外，都不能命中索引，比如a、c，或者b、c等。

為什麼？看看上面的單索引和複合索引就知道了。

有一個例外，當你select的欄位里有複合索引里的欄位，那麼where語句不需要滿足最左前綴匹配，Mysql也會走索引。

比如：

select a from foo where b = "xxx";

不過這時走索引不是為了加速查詢（這時候索引對查詢效率提升效果幾乎沒有），而是為了利用下面要講的，覆蓋索引，來減少對數據的檢索。

覆蓋索引

覆蓋索引（covering index）的原理很簡單，就像你拿到了一本書的目錄，裡頭有標題和對應的頁碼，當你想知道第267頁的標題是什麼的時候，完全沒有必要翻到267頁去看，而是直接看目錄。

同理，當你要select的欄位，已經在索引樹裡面存儲，那就不需要再去檢索資料庫，直接拿來用就行了。

還是上面的例子，你給a、b、c三個欄位建了複合索引，那麼對於下面這條sql，就可以走覆蓋索引:

select b,c from foo where a = "xxx";

explain一下，你就會發現extra欄位是「Using index」，或者使用explain FORMAT=JSON … ，輸出一個json結果的結果，看「using_index」屬性，你會發現是「true」，這都意味著使用到了覆蓋索引。

Using index (JSON property: using_index)

The column information is retrieved from the table using only information in the index tree without having to do an additional seek to read the actual row.

聚簇索引和二級索引

現在問一個問題，下面這條sql，會走覆蓋索引嗎？還是需要去磁碟再一次檢索？

select id,b,c from foo where a = "xxx";

和上一條sql對比，這一次我們在select裡頭，加了一個欄位，主鍵id。

有同學說，id不在複合索引里，B+樹沒有id的信息，只能再查一次資料庫了。

非也，在上面介紹B+ tree時有提到過，葉子節點不會直接存儲數據的位置，而是存儲了聚簇索引（clustered index）的值，再通過聚簇索引，找到數據對應的位置。

那什麼是聚簇索引呢？

Every InnoDB table has a special index called the clustered index where the data for the rows is stored.

簡單說，聚簇索引就是用來存儲行數據的位置的。

什麼樣的欄位才可以作為聚簇索引？

那當然是要具有唯一性的欄位，比如：

• 主鍵
• 唯一索引（unique index）所在欄位

這兩個都沒有？沒關係，mysql會給你建一個rowid欄位，用它作為聚簇索引：

If the table has no PRIMARY KEY or suitable UNIQUE index, InnoDB internally generates a hidden clustered index named GEN_CLUST_INDEX on a synthetic column containing row ID values.

除了聚簇索引，mysql中的其他索引，都叫二級索引（secondary index），有時也翻譯為「輔助索引」。

All indexes other than the clustered index are known as secondary indexes.

回到本小節開頭的問題，雖然id不在複合索引裡頭，但是mysql里所有的二級索引的葉子節點，都會存儲聚簇索引的信息，而id是主鍵，所以所有的葉子節點，都會有id的信息，因此還是可以走覆蓋索引。

總結

這篇文章從一顆簡單的B+樹，引申出了Mysql中常見的幾個索引概念：

• 單索引（Column Indexes）：當你為一個欄位建了索引時，mysql默默種了一棵樹。通過這顆樹，可以實現高效的逐級查找。
• 複合索引（Multiple-Column Indexes/Compound Indexes）：跟單索引原理一致，比較的方式變了一下，從字元串比較變為對象比較。
• 最左前綴匹配：一個理所當然的概念，只要你理解了上面兩位。
• 覆蓋索引：有些信息已經在樹裡面了，就不必再麻煩磁碟老人家了。
• 聚簇索引和二級索引：葉子節點不直接存儲數據位置的信息，存儲數據位置信息的，只有聚簇索引。

之所以寫這篇文章，是因為上個星期組內分享時，大佬講了一些關於Mysql執行優化的東西，比較高深，一下子發現了自己還有那麼多知識盲點，於是惡補了一下Mysql。

這篇文章只是稍微對Mysql基於B+樹的索引，做了稍微的延伸，還有很多好玩的沒提及，比如：

• 索引如何加速排序
• Mysql的ICP（Index Condition Pushdown Optimization）
• 索引的存儲和緩存
• 索引區分度和索引長度
• …

後面再一塊討論。

參考

• 一本關於資料庫系統理論的經典書籍：《資料庫系統概念》
• Mysql Index概覽：How MySQL Uses Indexes
• Mysql詞條-覆蓋索引：covering index
• 聚簇索引和二級索引：Clustered and Secondary Indexes
• StackOverflow上一個有趣的問題：Mysql covering vs composite vs column index

對了，微信公眾號已經開通：Bridge4You，歡迎關注！

有些話只能在那裡跟你說 (〃▽〃)