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

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

Mysql中的B+Tree索引

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

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

create index id_name on teacher(name);

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

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

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

select * from teacher where name = "Mozart";

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

從根節(jié)點開始妥曲，我們發(fā)現贾费，根節(jié)點就是”Mozart”，不過很可惜檐盟，根節(jié)點上面只有name字段的信息褂萧，沒有其他字段的數據。

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

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

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

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

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

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

于是，我們循著”Mozart”左邊指針的指引脚作，找到了”Mozart”的行數據葫哗。

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

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

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

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

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

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

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

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

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

復合索引

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

create index id_name_subject on teacher(name, subject);

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

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

之前只是單純的字符串比較像寒，現在是對象間的比較烘豹。

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

比較的順序筷笨，就是你索引創(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";

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

覆蓋索引

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

同理斥废，當你要select的字段椒楣，已經在索引樹里面存儲，那就不需要再去檢索數據庫牡肉，直接拿來用就行了捧灰。

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

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

explain一下拧抖，你就會發(fā)現extra字段是“Using index”煤搜，或者使用explain FORMAT=JSON … ，輸出一個json結果的結果唧席，看“using_index”屬性擦盾，你會發(fā)現是“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時有提到過，葉子節(jié)點不會直接存儲數據的位置奈惑，而是存儲了聚簇索引（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.

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

總結

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

單索引（Column Indexes）：當你為一個字段建了索引時循衰，mysql默默種了一棵樹铲敛。通過這顆樹，可以實現高效的逐級查找会钝。

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

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

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

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

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

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

索引如何加速排序

Mysql的ICP（Index Condition Pushdown Optimization）

索引的存儲和緩存

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

…