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

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

Mysql中的B+Tree索引

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

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

create index id_name on teacher(name);

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

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

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

select * from teacher where name = "Mozart";

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

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

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

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

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

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

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

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

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

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

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

從節(jié)點最左邊的搜索碼值開始，向右遍歷

如果搜索碼值大于被查找值，則跳到搜索碼值左邊指針指向的節(jié)點

如果等于，則跳到右邊指針指向的節(jié)點

如果小于，則遍歷下一個搜索碼值

如果遍歷完了整個節(jié)點，還是沒發(fā)現(xiàn)有大于等于被查找值的搜索碼，則跳到該節(jié)點最后一個非空指針指向的節(jié)點

不斷循環(huán)，直到找到被查找值，或者發(fā)現(xiàn)被查找值不存在

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

復合索引

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

create index id_name_subject on teacher(name, subject);

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

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

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

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

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

比如按照上面那條sql創(chuàng)建出來的索引，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";

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

覆蓋索引

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

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

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

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

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

聚簇索引和二級索引

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

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

和上一條sql對比，這一次我們在select里頭，加了一個字段，主鍵id。

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

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

那什么是聚簇索引呢？

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

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

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

那當然是要具有唯一性的字段，比如：

主鍵

唯一索引（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.

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

總結

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

單索引（Column Indexes）：當你為一個字段建了索引時，mysql默默種了一棵樹。通過這顆樹，可以實現(xiàn)高效的逐級查找。

復合索引（Multiple-Column Indexes/Compound Indexes）：跟單索引原理一致，比較的方式變了一下，從字符串比較變?yōu)閷ο蟊容^。

最左前綴匹配：一個理所當然的概念，只要你理解了上面兩位。

覆蓋索引：有些信息已經在樹里面了，就不必再麻煩磁盤老人家了。

聚簇索引和二級索引：葉子節(jié)點不直接存儲數(shù)據(jù)位置的信息，存儲數(shù)據(jù)位置信息的，只有聚簇索引。

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

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

索引如何加速排序

Mysql的ICP（Index Condition Pushdown Optimization）

索引的存儲和緩存

索引區(qū)分度和索引長度

…