Mysql索引簡(jiǎn)明教程

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

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

Mysql中的B+Tree索引

假設(shè)有一張教師表，里面有教師編號(hào)、名字、學(xué)科、薪資四個(gè)字段。

當(dāng)你執(zhí)行下面這條創(chuàng)建索引的sql語句時(shí)：

create index id_name on teacher(name);

Mysql就會(huì)在磁盤中構(gòu)建這樣一顆B+樹：

這樣一棵樹有什么用呢？首先當(dāng)然是加速查詢。

舉個(gè)簡(jiǎn)單的例子，假設(shè)現(xiàn)在要查找名字為“Mozart”的教師的數(shù)據(jù)：

select * from teacher where name = "Mozart";

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

從根節(jié)點(diǎn)開始，我們發(fā)現(xiàn)，根節(jié)點(diǎn)就是"Mozart"，不過很可惜，根節(jié)點(diǎn)上面只有name字段的信息，沒有其他字段的數(shù)據(jù)。

這是B+樹的一個(gè)特點(diǎn)——只有葉子節(jié)點(diǎn)（leaf nodes）會(huì)指向行數(shù)據(jù)。

我們比較了要查找的值和搜索碼值，發(fā)現(xiàn)相等，于是跳到搜索碼右邊的指針指向的節(jié)點(diǎn)，也就是“Srinivasan”所在的節(jié)點(diǎn)（注意，這里的節(jié)點(diǎn)是指下圖紅色框畫出的區(qū)域）。

接著，我們遍歷當(dāng)前節(jié)點(diǎn)的搜索碼值，和要查找的值做比較。

我們發(fā)現(xiàn)“Srinivasan”已經(jīng)大于我們要查找的"Mozart"了，于是就此止步，跟隨著“Srinivasan”左邊的指針，跳到下一級(jí)的節(jié)點(diǎn)。

接著，還是一樣，我們繼續(xù)遍歷當(dāng)前節(jié)點(diǎn)的搜索碼值，和要查找的值做比較。

這時(shí)我們又碰到了一個(gè)搜索碼值為"Mozart"的塊，和上次不同的是，這次是在葉子節(jié)點(diǎn)找到的，而不是根節(jié)點(diǎn)。葉子節(jié)點(diǎn)的指針指向行數(shù)據(jù)。

于是，我們循著"Mozart"左邊指針的指引，找到了"Mozart"的行數(shù)據(jù)。

當(dāng)然，這只是最最簡(jiǎn)潔的描述，如果name沒有加唯一索引，那么mysql還需要遍歷下一個(gè)塊，看看搜索碼值是不是也是"Mozart"。另外，葉子節(jié)點(diǎn)也不會(huì)直接存儲(chǔ)行數(shù)據(jù)的位置，而是存儲(chǔ)聚簇索引（clustered index）的值，通過聚簇索引去找到數(shù)據(jù)的位置，這個(gè)在后面會(huì)解釋。

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

  • 從節(jié)點(diǎn)最左邊的搜索碼值開始，向右遍歷
  • 如果搜索碼值大于被查找值，則跳到搜索碼值左邊指針指向的節(jié)點(diǎn)
  • 如果等于，則跳到右邊指針指向的節(jié)點(diǎn)
  • 如果小于，則遍歷下一個(gè)搜索碼值
  • 如果遍歷完了整個(gè)節(jié)點(diǎn)，還是沒發(fā)現(xiàn)有大于等于被查找值的搜索碼，則跳到該節(jié)點(diǎn)最后一個(gè)非空指針指向的節(jié)點(diǎn)
  • 不斷循環(huán)，直到找到被查找值，或者發(fā)現(xiàn)被查找值不存在

作為測(cè)驗(yàn)，大家可以模擬上面查找"Mozart"的過程，試著查找"Brandt"和“El Said”。

復(fù)合索引

上面講的只是單索引，那么如果是復(fù)合索引呢？

create index id_name_subject on teacher(name, subject);

一樣的，只是這次的搜索碼值，不再只是存放name一個(gè)字段，而是存放了name和subject兩個(gè)字段。

熟悉Java的同學(xué)，可以理解為，之前只是一個(gè)字符串，現(xiàn)在變成了一個(gè)Object了。

之前只是單純的字符串比較，現(xiàn)在是對(duì)象間的比較。

對(duì)象怎么比較呢？一項(xiàng)項(xiàng)來，如果前一項(xiàng)分不出勝負(fù)，那么再比下一項(xiàng)。

比較的順序，就是你索引創(chuàng)建語句里寫的順序。

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

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

最左前綴匹配

弄懂了單索引和復(fù)合索引的原理，再來理解Mysql中經(jīng)常被提及的——最左前綴匹配（leftmost prefix），就輕松的多了。

什么是最左前綴匹配？簡(jiǎn)單說，就是你給一個(gè)表的a，b，c三個(gè)字段建了索引：

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

那么當(dāng)你where條件是a或者a、b或者a、b、c時(shí)，都可以命中索引，除此之外，都不能命中索引，比如a、c，或者b、c等。

為什么？看看上面的單索引和復(fù)合索引就知道了。

有一個(gè)例外，當(dāng)你select的字段里有復(fù)合索引里的字段，那么where語句不需要滿足最左前綴匹配，Mysql也會(huì)走索引。

比如：

select a from foo where b = "xxx";

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

覆蓋索引

覆蓋索引（covering index）的原理很簡(jiǎn)單，就像你拿到了一本書的目錄，里頭有標(biāo)題和對(duì)應(yīng)的頁碼，當(dāng)你想知道第267頁的標(biāo)題是什么的時(shí)候，完全沒有必要翻到267頁去看，而是直接看目錄。

同理，當(dāng)你要select的字段，已經(jīng)在索引樹里面存儲(chǔ)，那就不需要再去檢索數(shù)據(jù)庫，直接拿來用就行了。

還是上面的例子，你給a、b、c三個(gè)字段建了復(fù)合索引，那么對(duì)于下面這條sql，就可以走覆蓋索引:

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

explain一下，你就會(huì)發(fā)現(xiàn)extra字段是“Using index”，或者使用explain FORMAT=JSON ... ，輸出一個(gè)json結(jié)果的結(jié)果，看“using_index”屬性，你會(huì)發(fā)現(xiàn)是“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.

聚簇索引和二級(jí)索引

現(xiàn)在問一個(gè)問題，下面這條sql，會(huì)走覆蓋索引嗎？還是需要去磁盤再一次檢索？

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

和上一條sql對(duì)比，這一次我們?cè)趕elect里頭，加了一個(gè)字段，主鍵id。

有同學(xué)說，id不在復(fù)合索引里，B+樹沒有id的信息，只能再查一次數(shù)據(jù)庫了。

非也，在上面介紹B+ tree時(shí)有提到過，葉子節(jié)點(diǎn)不會(huì)直接存儲(chǔ)數(shù)據(jù)的位置，而是存儲(chǔ)了聚簇索引（clustered index）的值，再通過聚簇索引，找到數(shù)據(jù)對(duì)應(yīng)的位置。

那什么是聚簇索引呢？

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

簡(jiǎn)單說，聚簇索引就是用來存儲(chǔ)行數(shù)據(jù)的位置的。

什么樣的字段才可以作為聚簇索引？

那當(dāng)然是要具有唯一性的字段，比如：

  • 主鍵
  • 唯一索引（unique index）所在字段

這兩個(gè)都沒有？沒關(guān)系，mysql會(huì)給你建一個(gè)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中的其他索引，都叫二級(jí)索引（secondary index），有時(shí)也翻譯為“輔助索引”。

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

回到本小節(jié)開頭的問題，雖然id不在復(fù)合索引里頭，但是mysql里所有的二級(jí)索引的葉子節(jié)點(diǎn)，都會(huì)存儲(chǔ)聚簇索引的信息，而id是主鍵，所以所有的葉子節(jié)點(diǎn)，都會(huì)有id的信息，因此還是可以走覆蓋索引。

總結(jié)

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

  • 單索引（Column Indexes）：當(dāng)你為一個(gè)字段建了索引時(shí)，mysql默默種了一棵樹。通過這顆樹，可以實(shí)現(xiàn)高效的逐級(jí)查找。
  • 復(fù)合索引（Multiple-Column Indexes/Compound Indexes）：跟單索引原理一致，比較的方式變了一下，從字符串比較變?yōu)閷?duì)象比較。
  • 最左前綴匹配：一個(gè)理所當(dāng)然的概念，只要你理解了上面兩位。
  • 覆蓋索引：有些信息已經(jīng)在樹里面了，就不必再麻煩磁盤老人家了。
  • 聚簇索引和二級(jí)索引：葉子節(jié)點(diǎn)不直接存儲(chǔ)數(shù)據(jù)位置的信息，存儲(chǔ)數(shù)據(jù)位置信息的，只有聚簇索引。

之所以寫這篇文章，是因?yàn)樯蟼€(gè)星期組內(nèi)分享時(shí)，大佬講了一些關(guān)于Mysql執(zhí)行優(yōu)化的東西，比較高深，一下子發(fā)現(xiàn)了自己還有那么多知識(shí)盲點(diǎn)，于是惡補(bǔ)了一下Mysql。

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

  • 索引如何加速排序
  • Mysql的ICP（Index Condition Pushdown Optimization）
  • 索引的存儲(chǔ)和緩存
  • 索引區(qū)分度和索引長(zhǎng)度
  • ...

后面再一塊討論。

參考

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容