• 案例背景

• 案例分析

• 案例解答

  • MySQL InnoDB 的索引原理

  • 索引類型

  • 通過主鍵查詢（主鍵索引）商品數(shù)據(jù)的過程

  • 通過非主鍵（輔助索引）查詢商品數(shù)據(jù)的過程

• B+Tree 索引的優(yōu)勢

• B+Tree 相對于 B 樹 索引結(jié)構(gòu)的優(yōu)勢

• B+Tree 相對于二叉樹索引結(jié)構(gòu)的優(yōu)勢

• B+Tree 相對于 Hash 表存儲結(jié)構(gòu)的優(yōu)勢

• 執(zhí)行計劃

• 索引失效的常見情況

• 常見優(yōu)化索引的方法

  • 前綴索引優(yōu)化

  • 覆蓋索引優(yōu)化

  • 聯(lián)合索引

• 總結(jié)

案例背景

假設(shè)面試官問你：在電商平臺的訂單中心系統(tǒng)中，通常要根據(jù)商品類型、訂單狀態(tài)篩選出需要的訂單，并按照訂單創(chuàng)建的時間進行排序，那針對下面這條 SQL，你怎么通過索引來提高查詢效率呢？

select * from order where status = 1 order by create_time asc

有的同學會認為，單獨給 status 建立一個索引就可以了。

但是更優(yōu)的方式是建立一個 status 和 create_time 組合索引，這是為了避免 MySQL 數(shù)據(jù)庫發(fā)生文件排序。

因為在查詢時，你只能用到 status 的索引，但如果要對 create_time 排序，就要用文件排序 filesort，也就是在 SQL 執(zhí)行計劃中，Extra 列會出現(xiàn) Using filesort 。

所以你要利用索引的有序性，在 status 和 create_time 列建立聯(lián)合索引，這樣根據(jù) status 篩選后的數(shù)據(jù)就是按照 create_time 排好序的，避免在文件排序。

案例分析

通過這個案例，你可以發(fā)現(xiàn)“索引知識”的重要性，

數(shù)據(jù)庫索引底層使用的是什么數(shù)據(jù)結(jié)構(gòu)和算法呢？

• 為什么 MySQL InnoDB 選擇 B+Tree 當默認的索引數(shù)據(jù)結(jié)構(gòu)？

• 如何通過執(zhí)行計劃查看索引使用詳情？

• 有哪些情況會導致索引失效？

• 平時有哪些常見的優(yōu)化索引的方法？

……

總結(jié)起來就是如下幾點：

• 理解 MySQL InnoDB 的索引原理；

• 掌握 B+Tree 相比于其他索引數(shù)據(jù)結(jié)構(gòu)（如 B-Tree、二叉樹，以及 Hash 表）的優(yōu)勢；

• 掌握 MySQL 執(zhí)行計劃的方法；

• 掌握導致索引失效的常見情況；

• 掌握實際工作中常用的建立高效索引的技巧（如前綴索引、建立覆蓋索引等）。

如果你曾經(jīng)被問到其中某一個問題，那你就有必要認真夯實 MySQL 索引及優(yōu)化的內(nèi)容了。

案例解答

MySQL InnoDB 的索引原理

從數(shù)據(jù)結(jié)構(gòu)的角度來看， MySQL 常見索引有 B+Tree 索引、HASH 索引、Full-Text 索引 。MySQL 常見的存儲引擎 InnoDB、MyISAM 和 Memory 分別支持的索引類型。（后兩個存儲引擎在實際工作和面試中很少提及，因此只講 InnoDB） 。

索引類型

在實際應(yīng)用中，InnoDB 是 MySQL 建表時默認的存儲引擎，B+Tree 索引類型也是 MySQL 存儲引擎采用最多的索引類型。

在創(chuàng)建表時，InnoDB 存儲引擎默認使用表的主鍵作為主鍵索引，該主鍵索引就是聚簇索引（Clustered Index），如果表沒有定義主鍵，InnoDB 就自己產(chǎn)生一個隱藏的 6 個字節(jié)的主鍵 ID 值作為主鍵索引， 而創(chuàng)建的主鍵索引默認使用的是 B+Tree 索引 。

接下來我們通過一個簡單的例子，說明一下 B+Tree 索引在存儲數(shù)據(jù)中的具體實現(xiàn)，為的是讓你理解通過 B+Tree 做索引的原理。

首先，我們創(chuàng)建一張商品表：

CREATE TABLE `product`  ( 
  `id` int(11) NOT NULL, 
  `product_no` varchar(20)  DEFAULT NULL, 
  `name` varchar(255) DEFAULT NULL, 
  `price` decimal(10, 2) DEFAULT NULL, 
  PRIMARY KEY (`id`) USING BTREE 
) CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic; 

然后新增幾行數(shù)據(jù)：

通過主鍵查詢（主鍵索引）商品數(shù)據(jù)的過程

此時當我們使用主鍵索引查詢商品 15 的時候，那么按照 B+Tree 索引原理，是如何找到對應(yīng)數(shù)據(jù)的呢？

select * from product where id = 15 

我們可以通過數(shù)據(jù)手動構(gòu)建一個 B+Tree，它的每個節(jié)點包含 3 個子節(jié)點（B+Tree 每個節(jié)點允許有 M 個子節(jié)點，且 M>2），根節(jié)點中的數(shù)據(jù)值 1、18、36 分別是子節(jié)點（1，6，12），（18，24，30）和（36，41，52）中的最小值。

每一層父節(jié)點的數(shù)據(jù)值都會出現(xiàn)在下層子節(jié)點的數(shù)據(jù)值中，因此在葉子節(jié)點中，包括了所有的數(shù)據(jù)值信息，并且每一個葉子節(jié)點都指向下一個葉子節(jié)點，形成一個鏈表。如圖所示：

我們舉例講解一下 B+Tree 的查詢流程，比如想要查找數(shù)據(jù)值 15，B+Tree 會自頂向下逐層進行查找：

1. 將 15 與根節(jié)點的數(shù)據(jù) (1，18，36) 比較，15 在 1 和 18 之間，所以根據(jù) B+Tree的搜索邏輯，找到第二層的數(shù)據(jù)塊 (1，6，12)；

2. 在第二層的數(shù)據(jù)塊 (1，6，12) 中進行查找，因為 15 大于 12，所以找到第三層的數(shù)據(jù)塊 (12，15，17)；

3. 在葉子節(jié)點的數(shù)據(jù)塊 (12，15，17) 中進行查找，然后我們找到了數(shù)據(jù)值 15；

最終根據(jù)數(shù)據(jù)值 15 找到葉子節(jié)點中存儲的數(shù)據(jù)。

整個過程一共進行了 3 次 I/O 操作，所以 B+Tree 相比于 B 樹和二叉樹來說，最大的優(yōu)勢在于查詢效率。

那么問題來了，如果你當前查詢數(shù)據(jù)時候，不是通過主鍵 ID，而是用商品編碼查詢商品，那么查詢過程又是怎樣的呢？

通過非主鍵（輔助索引）查詢商品數(shù)據(jù)的過程

如果你用商品編碼查詢商品（即使用輔助索引進行查詢），會先檢索輔助索引中的 B+Tree 的 商品編碼，找到對應(yīng)的葉子節(jié)點，獲取主鍵值，然后再通過主鍵索引中的 B+Tree 樹查詢到對應(yīng)的葉子節(jié)點，然后獲取整行數(shù)據(jù)。 這個過程叫回表 。

以上就是索引的實現(xiàn)原理。

在面試時，面試官一般不會讓你直接描述查詢索引的過程，但是會通過考察你對索引優(yōu)化方法的理解，來評估你對索引原理的掌握程度，比如為什么 MySQL InnoDB 選擇 B+Tree 作為默認的索引數(shù)據(jù)結(jié)構(gòu)？MySQL 常見的優(yōu)化索引的方法有哪些？

所以接下來，我們就詳細了解一下在面試中如何回答索引優(yōu)化的問題。

B+Tree 索引的優(yōu)勢

如果你被問到“為什么 MySQL 會選擇 B+Tree 當索引數(shù)據(jù)結(jié)構(gòu)？”其實在考察你兩個方面：B+Tree 的索引原理；B+Tree 索引相比于其他索引類型的優(yōu)勢。

我們剛剛已經(jīng)講了 B+Tree 的索引原理，現(xiàn)在就來回答一下 B+Tree 相比于其他常見索引結(jié)構(gòu)，如 B 樹、二叉樹或 Hash 索引結(jié)構(gòu)的優(yōu)勢在哪兒？

B+Tree 相對于 B 樹 索引結(jié)構(gòu)的優(yōu)勢

B+Tree 只在葉子節(jié)點存儲數(shù)據(jù)，而 B 樹 的非葉子節(jié)點也要存儲數(shù)據(jù)，所以 B+Tree 的單個節(jié)點的數(shù)據(jù)量更小，在相同的磁盤 I/O 次數(shù)下，就能查詢更多的節(jié)點。

另外，B+Tree 葉子節(jié)點采用的是雙鏈表連接，適合 MySQL 中常見的基于范圍的順序查找，而 B 樹無法做到這一點。

B+Tree 相對于二叉樹索引結(jié)構(gòu)的優(yōu)勢

對于有 N 個葉子節(jié)點的 B+Tree，其搜索復雜度為O(logdN)，其中 d 表示節(jié)點允許的最大子節(jié)點個數(shù)為 d 個。

在實際的應(yīng)用當中， d 值是大于100的，這樣就保證了，即使數(shù)據(jù)達到千萬級別時，B+Tree 的高度依然維持在 3~4 層左右，也就是說一次數(shù)據(jù)查詢操作只需要做 3~4 次的磁盤 I/O 操作就能查詢到目標數(shù)據(jù)（這里的查詢參考上面 B+Tree 的聚簇索引的查詢過程）。

而二叉樹的每個父節(jié)點的兒子節(jié)點個數(shù)只能是 2 個，意味著其搜索復雜度為 O(logN)，這已經(jīng)比 B+Tree 高出不少，因此二叉樹檢索到目標數(shù)據(jù)所經(jīng)歷的磁盤 I/O 次數(shù)要更多。

B+Tree 相對于 Hash 表存儲結(jié)構(gòu)的優(yōu)勢

我們知道范圍查詢是 MySQL 中常見的場景，但是 Hash 表不適合做范圍查詢，它更適合做等值的查詢，這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場景的原因。

至此，你就知道“為什么 MySQL 會選擇 B+Tree 來做索引”了。在回答時，你要著眼于 B+Tree 的優(yōu)勢，然后再引入索引原理的查詢過程（掌握這些知識點，這個問題其實比較容易回答）。

接下來，我們進入下一個問題：在實際工作中如何查看索引的執(zhí)行計劃。

通過執(zhí)行計劃查看索引使用詳情 我這里有一張存儲商品信息的演示表 product：

CREATE TABLE `product`  ( 
  `id` int(11) NOT NULL, 
  `product_no` varchar(20)  DEFAULT NULL, 
  `name` varchar(255) DEFAULT NULL, 
  `price` decimal(10, 2) DEFAULT NULL, 
  PRIMARY KEY (`id`) USING BTREE, 
  KEY 'index_name' ('name'). 
  KEY 'index_id_name' ('id', 'name') 
) CHARACTER SET = utf8 COLLATE = utf8_general_ci 

表中包含了主鍵索引、name 字段上的普通索引，以及 id 和 name 兩個字段的聯(lián)合索引?，F(xiàn)在我們來看一條簡單查詢語句的執(zhí)行計劃：

執(zhí)行計劃

對于執(zhí)行計劃，參數(shù)有 possible_keys 字段表示可能用到的索引，key 字段表示實際用的索引，key_len 表示索引的長度，rows 表示掃描的數(shù)據(jù)行數(shù)。

這其中需要你重點關(guān)注 type 字段， 表示數(shù)據(jù)掃描類型，也就是描述了找到所需數(shù)據(jù)時使用的掃描方式是什么，常見掃描類型的執(zhí)行效率從低到高的順序為（考慮到查詢效率問題，全表掃描和全索引掃描要盡量避免）：

ALL（全表掃描）；

index（全索引掃描）；

range（索引范圍掃描）；

ref（非唯一索引掃描）；

eq_ref（唯一索引掃描）；

const（結(jié)果只有一條的主鍵或唯一索引掃描）。

總的來說，執(zhí)行計劃是研發(fā)工程師分析索引詳情必會的技能（很多大廠公司招聘 JD 上寫著“SQL 語句調(diào)優(yōu)” ），所以你在面試時也要知道執(zhí)行計劃核心參數(shù)的含義，如 type。在回答時，也要以重點參數(shù)為切入點，再擴展到其他參數(shù)，然后再說自己是怎么做 SQL 優(yōu)化工作的。

索引失效的常見情況

在工作中，我們經(jīng)常會碰到 SQL 語句不適用已有索引的情況，來看一個索引失效的例子：

這條帶有 like 查詢的 SQL 語句，沒有用到 product 表中的 index_name 索引。

我們結(jié)合普通索引的 B+Tree 結(jié)構(gòu)看一下索引失效的原因：當 MySQL 優(yōu)化器根據(jù) name like ‘%路由器’ 這個條件，到索引 index_name 的 B+Tree 結(jié)構(gòu)上進行查詢評估時，發(fā)現(xiàn)當前節(jié)點的左右子節(jié)點上的值都有可能符合 '%路由器' 這個條件，于是優(yōu)化器判定當前索引需要掃描整個索引，并且還要回表查詢，不如直接全表掃描。

當然，還有其他類似的索引失效的情況：

索引列上做了計算、函數(shù)、類型轉(zhuǎn)換操作，這些情況下索引失效是因為查詢過程需要掃描整個索引并回表，代價高于直接全表掃描；

like 匹配使用了前綴匹配符 '%abc'；

字符串不加引號導致類型轉(zhuǎn)換；

我給你的建議是， 如果 MySQL 查詢優(yōu)化器預(yù)估走索引的代價比全表掃描的代價還要大，則不走對應(yīng)的索引，直接全表掃描，如果走索引比全表掃描代價小，則使用索引。

常見優(yōu)化索引的方法

前綴索引優(yōu)化

前綴索引就是用某個字段中，字符串的前幾個字符建立索引，比如我們可以在訂單表上對商品名稱字段的前 5 個字符建立索引。使用前綴索引是為了減小索引字段大小，可以增加一個索引頁中存儲的索引值，有效提高索引的查詢速度。在一些大字符串的字段作為索引時，使用前綴索引可以幫助我們減小索引項的大小。

但是，前綴索引有一定的局限性，例如 order by 就無法使用前綴索引，無法把前綴索引用作覆蓋索引。

覆蓋索引優(yōu)化

覆蓋索引是指 SQL 中 query 的所有字段，在索引 B+tree 的葉子節(jié)點上都能找得到的那些索引，從輔助索引中查詢得到記錄，而不需要通過聚簇索引查詢獲得。

假設(shè)我們只需要查詢商品的名稱、價格，有什么方式可以避免回表呢？

我們可以建立一個組合索引，即商品ID、名稱、價格作為一個組合索引。如果索引中存在這些數(shù)據(jù)，查詢將不會再次檢索主鍵索引，從而避免回表。所以，使用覆蓋索引的好處很明顯，即不需要查詢出包含整行記錄的所有信息，也就減少了大量的 I/O 操作。

聯(lián)合索引

聯(lián)合索引時，存在最左匹配原則，也就是按照最左優(yōu)先的方式進行索引的匹配。

比如聯(lián)合索引 (userpin, username)，如果查詢條件是 WHERE userpin=1 AND username=2，就可以匹配上聯(lián)合索引；或者查詢條件是 WHERE userpin=1，也能匹配上聯(lián)合索引，但是如果查詢條件是 WHERE username=2，就無法匹配上聯(lián)合索引。

另外，建立聯(lián)合索引時的字段順序，對索引效率也有很大影響。越靠前的字段被用于索引過濾的概率越高，實際開發(fā)工作中建立聯(lián)合索引時，要把區(qū)分度大的字段排在前面，這樣區(qū)分度大的字段越有可能被更多的 SQL 使用到。

區(qū)分度就是某個字段 column 不同值的個數(shù)除以表的總行數(shù)，比如性別的區(qū)分度就很小，不適合建立索引或不適合排在聯(lián)合索引列的靠前的位置，而 uuid 這類字段就比較適合做索引或排在聯(lián)合索引列的靠前的位置。

總結(jié)

主要講了 MySQL 的索引原理，介紹了 InnoDB 為什么會采用 B+Tree 結(jié)構(gòu)。因為 B+Tree 能夠減少單次查詢的磁盤訪問次數(shù)，做到查詢效率最大化。另外，我們還講了如何查看 SQL 的執(zhí)行計劃，從而找到索引失效的問題，并有針對性的做索引優(yōu)化。