【51CTO.com原創(chuàng)稿件】

 騰訊云數(shù)據(jù)庫負(fù)責(zé)人林曉斌說過：“我們面試 MySQL 同事時(shí)只考察兩點(diǎn)，索引和鎖”。

[[339341]]
圖片來自 Pexels

 

言簡(jiǎn)意賅，MySQL 索引的重要性不言而喻。MySQL 索引歷經(jīng)了多個(gè)版本的迭代，從語法到底層數(shù)據(jù)結(jié)構(gòu)都有很多改變。

MySQL 索引，我們真的了解么?好了，今天我們一起來看看 MySQL 索引的前世今生，一起聊聊索引的那些事兒。

[[339342]]

 

什么是索引?

在關(guān)系數(shù)據(jù)庫中，索引是一種單獨(dú)的、物理的對(duì)數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序的一種存儲(chǔ)結(jié)構(gòu)，它是某個(gè)表中一列或若干列值的集合和相應(yīng)的指向表中物理標(biāo)識(shí)這些值的數(shù)據(jù)頁的邏輯指針清單。

索引的作用相當(dāng)于圖書的目錄，可以根據(jù)目錄中的頁碼快速找到所需的內(nèi)容。

當(dāng)表中有大量記錄時(shí)，若要對(duì)表進(jìn)行查詢：

• 第一種搜索信息方式是全表搜索，是將所有記錄一一取出，和查詢條件進(jìn)行一一對(duì)比，然后返回滿足條件的記錄，這樣做會(huì)消耗大量數(shù)據(jù)庫系統(tǒng)時(shí)間，并造成大量磁盤 I/O 操作。
• 第二種就是在表中建立索引，然后在索引中找到符合查詢條件的索引值，最后通過保存在索引中的 ROWID(相當(dāng)于頁碼)快速找到表中對(duì)應(yīng)的記錄。

MySQL 5.5 以后 InnoDB 儲(chǔ)引擎使用的索引數(shù)據(jù)結(jié)構(gòu)主要用：B+Tree;本篇文章帶大家以 B+Tree 前世今生為主線來聊一聊。

Mark：B+Tree 可以對(duì) <，<=，=，>，>=，BETWEEN，IN，以及不以通配符開始的 LIKE 使用索引。(MySQL 5.5 后)

這些事實(shí)或許會(huì)顛覆你的一些認(rèn)知，比如在你讀過的其他文章或書中。以上這些都屬于“范圍查詢”，都是不走索引的!

沒錯(cuò)，早在 5.5 以前，優(yōu)化器是不會(huì)選擇通過索引搜索的，優(yōu)化器認(rèn)為這樣取出的行多與全表掃描的行，因?yàn)檫€要回表查一次嘛，可能會(huì)涉及 I/O 的行數(shù)更多，被優(yōu)化器放棄。

經(jīng)過算法(B+Tree)優(yōu)化后，支持對(duì)部分范圍類型的掃描(得利與 B+Tree 數(shù)據(jù)結(jié)構(gòu)的有序性)。

該做法同時(shí)也違反了最左前綴原則，導(dǎo)致范圍查詢后的條件無法用到聯(lián)合索引，我們?cè)诤竺嬖敿?xì)說明。

索引的優(yōu)缺點(diǎn)

索引的優(yōu)點(diǎn)如下：

• 索引大大減小了服務(wù)器需要掃描的數(shù)據(jù)量。
• 索引可以幫助服務(wù)器避免排序和臨時(shí)表。
• 索引可以將隨機(jī) I/O 變成順序 I/O。

索引的缺點(diǎn)如下：

• 雖然索引大大提高了查詢速度，同時(shí)卻會(huì)降低更新表的速度，如對(duì)表進(jìn)行 INSERT、UPDATE 和 DELETE。因?yàn)楦卤頃r(shí)，MySQL 不僅要保存數(shù)據(jù)，還要保存索引文件。
• 建立索引會(huì)占用磁盤空間的索引文件。一般情況這個(gè)問題不算嚴(yán)重，但如果你在一個(gè)大表上創(chuàng)建了多種組合索引，且伴隨大量數(shù)據(jù)量插入，索引文件大小也會(huì)快速膨脹。
• 如果某個(gè)數(shù)據(jù)列包含許多重復(fù)的內(nèi)容，為它建立索引就沒有太大的實(shí)際效果。
• 對(duì)于非常小的表，大部分情況下簡(jiǎn)單的全表掃描更高效。

因此應(yīng)該只為最經(jīng)常查詢和最經(jīng)常排序的數(shù)據(jù)列建立索引。(MySQL 里同一個(gè)數(shù)據(jù)表里的索引總數(shù)限制為 16 個(gè))

數(shù)據(jù)庫存在的意義之一就是是解決數(shù)據(jù)存儲(chǔ)和快速查找的。那么數(shù)據(jù)庫的數(shù)據(jù)存在哪?沒錯(cuò)，是磁盤，磁盤的優(yōu)點(diǎn)是啥?便宜!缺點(diǎn)呢?相比內(nèi)存訪問速度慢。

那么你知道 MySQL 索引主要使用的數(shù)據(jù)結(jié)構(gòu)么?B+樹!你脫口而出。

那 B+樹是什么樣的數(shù)據(jù)結(jié)構(gòu)?MySQL 索引又是為什么選擇了 B+樹呢?

其實(shí)最終選用 B+樹是經(jīng)歷了漫長(zhǎng)的演化：

二叉排序樹 → 二叉平衡樹 → B-Tree（B樹） → B+Tree（B+樹） 

有小伙伴問我“B 樹跟 B-樹有什么區(qū)別”?這里普及一下，MySQL 數(shù)據(jù)結(jié)構(gòu)只有B-Tree(B 樹)和 B+Tree(B+樹)，多只是讀法不同罷了，“B-Tree” 一般統(tǒng)稱為 B 樹，你叫他 B-樹也行!

還有小伙伴提到的紅黑樹，是編程語言中的存儲(chǔ)結(jié)構(gòu)，不是 MySQL 的;如 Java 的 HashMap 就是用的鏈表加紅黑樹。

好了，今天就帶著大家一起看一下演化成 B+樹的過程吧。

B+Tree 索引的前世今生

①二叉排序樹

理解 B+樹之前，簡(jiǎn)單說一下二叉排序樹，對(duì)于一個(gè)節(jié)點(diǎn)，它的左子樹的孩子節(jié)點(diǎn)值都要小于它本身，它的右子樹的孩子節(jié)點(diǎn)值都要大于它本身。

如果所有節(jié)點(diǎn)都滿足這個(gè)條件，那么它就是二叉排序樹。(此處可以串一下二分查找的知識(shí)點(diǎn))

 

上圖是一顆二叉排序樹，你可以嘗試?yán)盟奶攸c(diǎn)，體驗(yàn)查找 9 的過程：

• 9 比 10 小，去它的左子樹(節(jié)點(diǎn) 3)查找。
• 9 比 3 大，去節(jié)點(diǎn) 3 的右子樹(節(jié)點(diǎn) 4)查找。
• 9 比 4 大，去節(jié)點(diǎn) 4 的右子樹(節(jié)點(diǎn) 9)查找。
• 節(jié)點(diǎn) 9 與 9 相等，查找成功。

一共比較了 4 次，那你有沒有想過上述結(jié)構(gòu)的優(yōu)化方式?

②AVL 樹(自平衡二叉查找樹)

 

上圖是 AVL 樹，節(jié)點(diǎn)個(gè)數(shù)和值均和二叉排序樹一摸一樣。

再來看一下查找 9 的過程：

• 9 比 4 大，去它的右子樹查找。
• 9 比 10 小，去它的左子樹查找。
• 節(jié)點(diǎn) 9 與 9 相等，查找成功。

一共比較了 3 次，同樣的數(shù)據(jù)量比二叉排序樹少了一次，為什么呢?因?yàn)?AVL 樹高度要比二叉排序樹小，高度越高意味著比較的次數(shù)越多;不要小看優(yōu)化的這一次，假如是 200w 條數(shù)據(jù)，比較次數(shù)會(huì)明顯地不同。

你可以想象一下一棵 100 萬節(jié)點(diǎn)的平衡二叉樹，樹高 20。一次查詢可能需要訪問 20 個(gè)數(shù)據(jù)塊。在機(jī)械硬盤時(shí)代，從磁盤隨機(jī)讀一個(gè)數(shù)據(jù)塊需要 10 ms 左右的尋址時(shí)間。

也就是說，對(duì)于一個(gè) 100 萬行的表，如果使用二叉樹來存儲(chǔ)，單獨(dú)訪問一個(gè)行可能需要 20 個(gè) 10 ms 的時(shí)間，這個(gè)查詢可真夠慢的!

③B 樹(Balanced Tree)多路平衡查找樹，多叉的

B 樹是一種多路自平衡搜索樹，它類似普通的二叉樹，但是 B 樹允許每個(gè)節(jié)點(diǎn)有更多的子節(jié)點(diǎn)。

B 樹示意圖如下：

B 樹的特點(diǎn)如下：

 

• 所有鍵值分布在整個(gè)樹中。
• 任何關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)節(jié)點(diǎn)中。
• 搜索有可能在非葉子節(jié)點(diǎn)結(jié)束。
• 在關(guān)鍵字全集內(nèi)做一次查找，性能逼近二分查找算法。

為了提升效率，要盡量減少磁盤 I/O 的次數(shù)。實(shí)際過程中，磁盤并不是每次嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀。

磁盤讀取完需要的數(shù)據(jù)后，會(huì)按順序再多讀一部分?jǐn)?shù)據(jù)到內(nèi)存中，這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中注明的局部性原理：

• 由于磁盤順序讀取的效率很高(不需要尋址時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間)，因此對(duì)于具有局部性的程序來說，預(yù)讀可以提高 I/O 效率。預(yù)讀的長(zhǎng)度一般為頁(page)的整倍數(shù)。
• MySQL(默認(rèn)使用 InnoDB 引擎)，將記錄按照頁的方式進(jìn)行管理，每頁大小默認(rèn)為 16K(可以修改)。

B-Tree 借助計(jì)算機(jī)磁盤預(yù)讀機(jī)制：每次新建節(jié)點(diǎn)的時(shí)候，都是申請(qǐng)一個(gè)頁的空間，所以每查找一個(gè)節(jié)點(diǎn)只需要一次 I/O;因?yàn)閷?shí)際應(yīng)用當(dāng)中，節(jié)點(diǎn)深度會(huì)很少，所以查找效率很高。

那么最終版的 B+樹是如何做的呢?

④B+Tree (B+樹是 B 樹的變體，也是一種多路搜索樹)

從圖中也可以看到，B+樹與 B 樹的不同在于：

 

• 所有關(guān)鍵字存儲(chǔ)在葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)不存儲(chǔ)真正的 data，從而可以快速定位到葉子結(jié)點(diǎn)。
• 為所有葉子節(jié)點(diǎn)增加了一個(gè)鏈指針，意味著所有的值都是按順序存儲(chǔ)的，并且每一個(gè)葉子頁到根的距離相同，很適合查找范圍數(shù)據(jù)。

因此，B+Tree 可以對(duì) <，<=，=，>，>=，BETWEEN，IN，以及不以通配符開始的 LIKE 使用索引。

B+ 樹的優(yōu)點(diǎn)，比較的次數(shù)均衡，減少了 I/O 次數(shù)，提高了查找速度，查找也更穩(wěn)定：

• B+樹的磁盤讀寫代價(jià)更低。
• B+樹的查詢效率更加穩(wěn)定。

要知道的是，你每次創(chuàng)建表，系統(tǒng)會(huì)為你自動(dòng)創(chuàng)建一個(gè)基于 ID 的聚集索引(上述 B+樹)，存儲(chǔ)全部數(shù)據(jù)。

你每次增加索引，數(shù)據(jù)庫就會(huì)為你創(chuàng)建一個(gè)附加索引(上述 B+樹)，索引選取的字段個(gè)數(shù)就是每個(gè)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)索引的個(gè)數(shù)，注意該索引并不存儲(chǔ)全部數(shù)據(jù)。

為什么 MySQL 索引選擇了 B+樹而不是 B 樹?

原因有如下兩點(diǎn)：

• B+樹更適合外部存儲(chǔ)(一般指磁盤存儲(chǔ))，由于內(nèi)節(jié)點(diǎn)(非葉子節(jié)點(diǎn))不存儲(chǔ) data，所以一個(gè)節(jié)點(diǎn)可以存儲(chǔ)更多的內(nèi)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確。也就是說使用 B+樹單次磁盤 I/O 的信息量相比較 B 樹更大，I/O 效率更高。
• MySQL 是關(guān)系型數(shù)據(jù)庫，經(jīng)常會(huì)按照區(qū)間來訪問某個(gè)索引列，B+樹的葉子節(jié)點(diǎn)間按順序建立了鏈指針，加強(qiáng)了區(qū)間訪問性，所以 B+樹對(duì)索引列上的區(qū)間范圍查詢很友好。而 B 樹每個(gè)節(jié)點(diǎn)的 key 和 data 在一起，無法進(jìn)行區(qū)間查找。

程序員，你應(yīng)該知道的索引知識(shí)點(diǎn)

①回表查詢

比如你創(chuàng)建了 name， age 索引 name_age_index，查詢數(shù)據(jù)時(shí)使用了：

select * from table where name ='陳哈哈' and age = 26; 

由于附加索引中只有 name 和 age，因此命中索引后，數(shù)據(jù)庫還必須回去聚集索引中查找其他數(shù)據(jù)，這就是回表，這也是你背的那條：少用 select * 的原因。

②索引覆蓋

結(jié)合回表會(huì)更好理解，比如上述 name_age_index 索引，有查詢：

select name， age from table where name ='陳哈哈' and age = 26; 

此時(shí) select 的字段 name，age 在索引 name_age_index 中都能獲取到，所以不需要回表，滿足索引覆蓋，直接返回索引中的數(shù)據(jù)，效率高。是 DBA 同學(xué)優(yōu)化時(shí)的首選優(yōu)化方式。

③最左前綴原則

B+樹的節(jié)點(diǎn)存儲(chǔ)索引順序是從左向右存儲(chǔ)，在匹配的時(shí)候自然也要滿足從左向右匹配。

通常我們?cè)诮⒙?lián)合索引的時(shí)候，也就是對(duì)多個(gè)字段建立索引，相信建立過索引的同學(xué)們會(huì)發(fā)現(xiàn)，無論是 Oracle 還是 MySQL 都會(huì)讓我們選擇索引的順序。

比如我們想在 a，b，c 三個(gè)字段上建立一個(gè)聯(lián)合索引，我們可以選擇自己想要的優(yōu)先級(jí)，a、b、c，或者是 b、a、c 或者是 c、a、b 等順序。

為什么數(shù)據(jù)庫會(huì)讓我們選擇字段的順序呢?不都是三個(gè)字段的聯(lián)合索引么?這里就引出了數(shù)據(jù)庫索引的最左前綴原理。

在我們開發(fā)中經(jīng)常會(huì)遇到明明這個(gè)字段建了聯(lián)合索引，但是 SQL 查詢?cè)撟侄螘r(shí)卻不會(huì)使用索引的問題。

比如索引 abc_index：(a，b，c)是 a，b，c 三個(gè)字段的聯(lián)合索引，下列 sql 執(zhí)行時(shí)都無法命中索引 abc_index 的。

select * from table where c = '1'; 
select * from table where b ='1' and c ='2'; 

以下三種情況卻會(huì)走索引：

select * from table where a = '1'; 
select * from table where a = '1' and b = '2'; 
select * from table where a = '1' and b = '2'  and c='3'; 

從上面兩個(gè)例子大家是否闊以看出點(diǎn)眉目?

是的，索引 abc_index：(a，b，c)，只會(huì)在(a)、(a，b)、(a，b，c)三種類型的查詢中使用。

其實(shí)這里說的有一點(diǎn)歧義，其實(shí)(a，c)也會(huì)走，但是只走 a 字段索引，不會(huì)走 c 字段。

另外還有一個(gè)特殊情況說明下，下面這種類型的也只會(huì)有 a 與 b 走索引，c 不會(huì)走。

select * from table where a = '1' and b > '2'  and c='3'; 

像上面這種類型的 sql 語句，在 a、b 走完索引后，c 已經(jīng)是無序了，所以 c 就沒法走索引，優(yōu)化器會(huì)認(rèn)為還不如全表掃描 c 字段來的快。

最左前綴：顧名思義，就是最左優(yōu)先，上例中我們創(chuàng)建了 a_b_c 多列索引，相當(dāng)于創(chuàng)建了(a)單列索引，(a，b)組合索引以及(a，b，c)組合索引。

因此，在創(chuàng)建多列索引時(shí)，要根據(jù)業(yè)務(wù)需求，where 子句中使用最頻繁的一列放在最左邊。

④索引下推優(yōu)化

還是索引 name_age_index，有如下 sql：

select * from table where name like '陳%' and age > 26； 

該語句有兩種執(zhí)行可能：

• 命中 name_age_index 聯(lián)合索引，查詢所有滿足 name 以"陳"開頭的數(shù)據(jù)， 然后回表查詢所有滿足的行。
• 命中 name_age_index 聯(lián)合索引，查詢所有滿足 name 以"陳"開頭的數(shù)據(jù)，然后順便篩出 age>20 的索引，再回表查詢?nèi)袛?shù)據(jù)。

顯然第 2 種方式回表查詢的行數(shù)較少，I/O 次數(shù)也會(huì)減少，這就是索引下推。所以不是所有 like 都不會(huì)命中索引。

使用索引時(shí)的注意事項(xiàng)

①索引不會(huì)包含有 null 值的列

只要列中包含有 null 值都將不會(huì)被包含在索引中，復(fù)合索引中只要有一列含有 null 值，那么這一列對(duì)于此復(fù)合索引就是無效的。所以我們?cè)跀?shù)據(jù)庫設(shè)計(jì)時(shí)建議不要讓字段的默認(rèn)值為 null。

②使用短索引

對(duì)串列進(jìn)行索引，如果可能應(yīng)該指定一個(gè)前綴長(zhǎng)度。

例如，如果有一個(gè) char(255)的列，如果在前 10 個(gè)或 20 個(gè)字符內(nèi)，多數(shù)值是惟一的，那么就不要對(duì)整個(gè)列進(jìn)行索引。短索引不僅可以提高查詢速度而且可以節(jié)省磁盤空間和 I/O 操作。

③索引列排序

查詢只使用一個(gè)索引，因此如果 where 子句中已經(jīng)使用了索引的話，那么 order by 中的列是不會(huì)使用索引的。

因此數(shù)據(jù)庫默認(rèn)排序可以符合要求的情況下不要使用排序操作;盡量不要包含多個(gè)列的排序，如果需要最好給這些列創(chuàng)建復(fù)合索引。

④like 語句操作

一般情況下不推薦使用 like 操作，如果非使用不可，如何使用也是一個(gè)問題。like “%陳%” 不會(huì)使用索引而 like “陳%”可以使用索引。

⑤不要在列上進(jìn)行運(yùn)算

這將導(dǎo)致索引失效而進(jìn)行全表掃描，例如：

SELECT * FROM table_name WHERE YEAR(column_name)<2017; 

⑥不使用 not in 和 <> 操作

這不屬于支持的范圍查詢條件，不會(huì)使用索引。

我的體會(huì)

曾經(jīng)，我一度以為我很懂 MySQL。

剛?cè)肼毮悄?，我還是個(gè)孩子，記得第一個(gè)需求是做個(gè)統(tǒng)計(jì)接口，查詢近兩小時(shí)每隔 5 分鐘為一時(shí)間段的網(wǎng)站訪問量，JSONArray 中一共返回 24 個(gè)值，當(dāng)時(shí)菜啊，寫了個(gè)接口循環(huán)二十四遍，發(fā)送 24 條 SQL 去查(捂臉)。

由于那個(gè)接口，被技術(shù)經(jīng)理嘲諷表示他寫的 SQL 比我吃的米都多。雖然我們山東人基本不吃米飯，但我還是羞愧不已。

然后經(jīng)理通過調(diào)用一個(gè) dateTime 函數(shù)分組查詢處理一下，就 OK 了，效率是我的幾十倍吧。

從那時(shí)起，我就定下目標(biāo)，深入 MySQL 學(xué)習(xí)，萬一日后有機(jī)會(huì)嘲諷回去?

筒子們，MySQL 路漫漫，其修遠(yuǎn)兮。永遠(yuǎn)不要眼高手低，一起加油，希望本文能對(duì)你有所幫助。

作者：陳哈哈

簡(jiǎn)介：MySQL 社區(qū)的非著名貢獻(xiàn)者，善于白嫖知識(shí);陪伴 MySQL 五年，致力于高性能 SQL、事務(wù)鎖優(yōu)化方面的研究;長(zhǎng)路漫漫，希望通過自己的分享讓大家少踩一些坑。我是陳哈哈，一個(gè)愛笑的程序員。

編輯：陶家龍

征稿：有投稿、尋求報(bào)道意向技術(shù)人請(qǐng)聯(lián)絡(luò) editor@51cto.com

【51CTO原創(chuàng)稿件，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文作者和出處為51CTO.com】