1 索引如何工作，是如何加快查詢速度

索引就好比書本的目錄，提高數據庫表數據訪問速度的數據庫對象。當我們的請求打過來之后，如果有目錄，就會快速的定位到章節(jié)，再從章節(jié)里找到數據。如果沒有目錄，如大海撈針一般，難度可見一斑。這就是我們經常碰到的罪魁禍首，全表掃描。

一條索引記錄中包含的基本信息包括：鍵值（即你定義索引時指定的所有字段的值）+ 邏輯指針（指向數據頁或者另一索引頁）。通常狀況下，由于索引記錄僅包含索引字段值（以及 4-9 字節(jié)的指針），索引實體比真實的數據行要小許多，索引頁相較數據頁來說要密集許多。一個索引頁可以存儲數量更多的索引記錄，這意味著在索引中查找時在 I/O 上占很大的優(yōu)勢，理解這一點有助于從本質上了解使用索引的優(yōu)勢，也是大部分性能優(yōu)化所需要切入的點。

1）沒有索引的情況下訪問數據：

2）使用平衡二叉樹結構索引的情況下訪問數據：

第一張圖沒有使用索引我們會進行順序查找，依照數據順序逐個進行匹配，進行了 5 次尋址才查詢出所需數據，第二張圖用了一個簡單的平衡二叉樹索引之后我們只用了 3 次，這還是數據量小的情況下，數據量大了效果更明顯，所以總結來說創(chuàng)建索引就是為了加快數據查找速度；

2 索引的組成部分和種類

常見的索引的實現方式有很多種，比如 hash、數組、樹，下面為大家介紹下這幾種模型使用上有什么區(qū)別

2.1 hash

hash 思路簡單，就是把我們插入的 key 通過 hash 函數算法 (以前一般是取余數，就好比 hashmap 的計算方式移位異或之類的)，計算出對應的 value，把這個 value 放到一個位置，這個位置叫做哈希槽。對應磁盤位置指針放入 hash 槽里面。一句話總結 hash 索引，就是存儲了索引字段的 hash 值和數據所在磁盤文件指針。

但是不可避免的是，無論什么算法，數據量大了之后難免會出現不同的數據被放在一個 hash 槽里面。比如字典上的 “吳” 和” 武” 就是同音，你查字典的時候到這里只能順序往下去找了。索引的處理也是這樣，會拉出一個鏈表，需要的時候順序遍歷即可。

缺點：無序索引，區(qū)間查詢性能低，因為區(qū)間查詢會造成多次訪問磁盤，多次 io 耗時是很難接受的。

優(yōu)點：insert 迅速，只需往后補就行

場景：等值查詢， 比如 memcached 。不適用大量重復數據的列，避免 hash 沖突

總結：想成 java 的 hashmap 即可

2.2 有序數組

如果我們需要區(qū)間查詢的時候，hash 索引的性能就不盡如人意了。這個時候有序數組的優(yōu)勢就能體現出來了。

當我們需要從一個有序數組里取 A 和 B 之間的值時，只需要通過二分法定位到 A 的位置，時間復雜度 O (log (N)), 接著從 A 遍歷到 B 即可，論速度的話，基本上可以說是最快的了。但是當我們需要更新的時候，需要進行的操作就很多了。如果需要插入一條數據，你需要挪動數據之后的所有數據，浪費性能。所以總結來說，只有不怎么變化的數據適合有序數組結構的索引。

缺點：insert 新數據的時候，需要改變后續(xù)所有數據，成本略高。

優(yōu)點：查詢速度很快，理論最大值。

場景：歸檔查詢，日志查詢等極少變化的

總結：就是順序排的數組

2.3 二叉搜索樹

基本原則是樹的左節(jié)點都小于父節(jié)點，右節(jié)點都大于父節(jié)點

這里我們就能看出來，二叉搜索樹的查詢效率原則上是 O (log (N))，為了保證是平衡二叉樹，更新效率也是 O (log (N))。但是數據很多的情況樹的高度會達到很高，過多次訪問磁盤，是不可取的。并且極端情況下，樹退化成鏈表，查詢的復雜度會被拉成 O (n)。

進化成多叉樹，也就是多個子節(jié)點的時候，會大大的減少樹的高度，降低訪問磁盤。

缺點：數據量大的時候，樹會過高，導致多次訪問磁盤

優(yōu)點：進化成多叉樹，會降低樹高，訪問磁盤次數。

場景：適用很多場景

總結：左小右大的樹

2.4 B 樹

在每個節(jié)點存儲多個元素，在每個節(jié)點盡可能多的存儲數據。每個節(jié)點可以存儲 1000 個索引（16k/16=1000），這樣就將二叉樹改造成了多叉樹，通過增加樹的叉樹，將樹從高瘦變?yōu)榘?。構?1 百萬條數據，樹的高度只需要 2 層就可以（1000*1000=1 百萬），也就是說只需要 2 次磁盤 IO 就可以查詢到數據。磁盤 IO 次數變少了，查詢數據的效率也就提高了。

這種數據結構我們稱為 B 樹，B 樹是一種多叉平衡查找樹

2.5 B + 樹

B + 樹和 B 樹最主要的區(qū)別在于非葉子節(jié)點是否存儲數據的問題。

B 樹：非葉子節(jié)點和葉子節(jié)點都會存儲數據。

B + 樹：只有葉子節(jié)點才會存儲數據，非葉子節(jié)點至存儲鍵值。葉子節(jié)點之間使用雙向指針連接，最底層的葉子節(jié)點形成了一個雙向有序鏈表。

正是因為 B + 樹的葉子節(jié)點是通過鏈表連接的，所以找到下限后能很快進行區(qū)間查詢，比正常的中序遍歷快

3 索引的維護

當你 insert 一條數據的時候，索引需要做出必要的操作來保證數據的有序型。一般自增數據直接在后面加就行了，特殊情況下如果數據加到了中間，就需要挪動后面所有的數據，這樣效率比較受影響。

最糟糕的情況，如果當前的數據頁（頁是 mysql 存儲的最小單位）存滿了，需要申請一個新的數據頁，這個過程被稱為頁分裂。如果造成了頁分裂的話，勢必會造成性能的影響。但是 mysql 并不是無腦的數據分裂，如果你是從中間進行數據分裂的話，對于自增主鍵，會導致一半的性能浪費。mysql 會根據你的索引的類型，和追蹤插入數據的情況決定分裂的方式，一般都存在 mysql 數據頁的 head 里面，如果是零散的插入，會從中間分裂。如果是順序插入，一般是會選擇插入點開始分裂，或者插入點往后幾行導致的。決定是否從中間分裂，還是從最后分裂。

如果插入的是不規(guī)則的數據，沒法保證后一個值比前一個大，就會觸發(fā)上面說的分裂邏輯，最后達到下面的效果

所以絕大多數情況下，我們都需要使用自增索引，除非需要業(yè)務自定義主鍵，最好能保證只有一個索引，且索引是唯一索引。這樣可以避免回表，導致查詢搜索兩棵樹。保證數據頁的有序性，可以更好的使用索引。

4 回表

通俗的講就是，如果索引的列在 select 所需獲得的列中（因為在 mysql 中索引是根據索引列的值進行排序的，所以索引節(jié)點中存在該列中的部分值）或者根據一次索引查詢就能獲得記錄就不需要回表，如果 select 所需獲得列中有大量的非索引列，索引就需要先找到主鍵，再到表中找到相應的列的信息，這就叫回表。

要介紹回表自然就得介紹聚集索引和非聚集索引
InnoDB 聚集索引的葉子節(jié)點存儲行記錄，因此， InnoDB 必須要有，且只有一個聚集索引：

如果表定義了主鍵，則 PK 就是聚集索引；

如果表沒有定義主鍵，則第一個非空唯一索引（not NULL unique）列是聚集索引；

否則，InnoDB 會創(chuàng)建一個隱藏的 row-id 作為聚集索引；

當我們使用普通索引查詢方式，則需要先搜索普通索引樹，然后得到主鍵 ID 后，再到 ID 索引樹搜索一次。因為非主鍵索引的葉子節(jié)點里面，實際存的是主鍵的 ID。這個過程雖然用了索引，但實際上底層進行了兩次索引查詢，這個過程就稱為回表。也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應用中應該盡量使用主鍵查詢?；蛘哂懈哳l請求時，合理建立聯(lián)合索引，防止回表。

5 索引覆蓋

一句話表達的話，是只需要在一棵索引樹上就能獲取 SQL 所需的所有列數據，無需回表，速度更快。落實到 sql 上的話，只要執(zhí)行計劃里面的輸出結果 Extra 字段為 Using index 時，能夠觸發(fā)索引覆蓋。

常見的優(yōu)化手段，就是上面提到的，將查詢的字段都建到索引里面，至于 dba 愿不愿意讓你建，那就需要你們自己 battle 了。

一般索引覆蓋適用的場景包括 全表 count 查詢優(yōu)化、列查詢回表、分頁回表。高版本的 mysql 已經做了優(yōu)化，當命中聯(lián)合索引的其中一個字段，另外一個是 id 的時候，會自動優(yōu)化，無需回表。因為二級索引的葉子上存了 primary key，也算索引覆蓋，無需額外成本。

6 最左匹配原則

簡單來說，就是你使用 ‘xx%’的時候，符合條件的話也會使用索引。
如果是聯(lián)合索引的話，我舉個例子，創(chuàng)建一個（a,b）的聯(lián)合索引

可以看到 a 的值是有順序的，1，1，2，2，3，3，而 b 的值是沒有順序的 1，2，1，4，1，2。但是我們又可發(fā)現 a 在等值的情況下，b 值又是按順序排列的，但是這種順序是相對的。這是因為 MySQL 創(chuàng)建聯(lián)合索引的規(guī)則是首先會對聯(lián)合索引的最左邊第一個字段排序，在第一個字段的排序基礎上，然后在對第二個字段進行排序。所以 b=2 這種查詢條件沒有辦法利用索引。舉個例子，我弄一個索引，
KEYidx_time_zone(time_zone,time_string) USING BTREE
執(zhí)行第一條 sql, 全表掃描

執(zhí)行第二條 sql，可以看到使用了索引。

再看兩條 sql，建立的索引是 KEYidx_time_zone(time_zone,time_string) USING BTREE

按照正常邏輯來說，第二條 sql 是不符合索引字段的順序的，應該不能使用索引才對，但是實際情況卻和我們期望的不太一樣，這是為啥呢？

從 mysql 被 oracle 收購以后，mysql 加入了很多 oracle 以前的技術，高版本 mysql 自動優(yōu)化了 where 條件的先后順序。簡單來說就是查詢優(yōu)化器做了這一步操作，sql 會做預處理，那一條能更好的查詢就會使用那種規(guī)則。

順便提一下 mysql 的查詢優(yōu)化器能幫忙干的一些事

6.1 條件轉化

例如 where a=b and b=2，可以得到 a=2, 條件傳遞。最后的 sql 是 a=2 and b=2 > < = like 都可以傳遞

6.2 無效代碼的排除

例如 where 1=1 and a=2, 1=1 永遠是正確的，所以最后會優(yōu)化成 a=2
在比如 where 1=0 永遠是 false 的，這樣的也會被排除掉，整 sql 無效
或者非空字段 where a is null , 這樣的也會被排除

6.3 提前計算

包含數學運算的部分，例如 where a= 1+2 會幫你算好，where a=3

6.4 存取類型

當我們評估一個條件表達式，MySQL 判斷該表達式的存取類型。下面是一些存取類型，按照從最優(yōu)到最差的順序進行排列：

system 系統(tǒng)表，并且是常量表

const 常量表

eq_ref unique/primary 索引，并且使用的是’=’進行存取

ref 索引使用’=’進行存取

ref_or_null 索引使用’=’進行存取，并且有可能為 NULL

range 索引使用 BETWEEN、IN、>=、LIKE 等進行存取

index 索引全掃描

ALL 表全掃描

經常看執(zhí)行計劃的，一眼就能看出來這是啥意思，舉個例子

where index_col=2 and normal_col =3 這里就會選用 index_col=2 會作為驅動項。驅動項的意思是指一個 sql 選定他的執(zhí)行計劃的時候，可能有多條執(zhí)行路徑，一個是全表掃描，再過濾是否符合索引字段及非索引字段的值。另一種是通過索引字段，鍵值 = 2 找到對應的索引樹，過濾后的結果，再比較是否符合非索引字段的值。一般情況下，走索引都比全表掃描需要讀取磁盤的次數少，所以稱它為更好的執(zhí)行路徑，也就是通過索引字段，作為其驅動表達式

6.5 范圍存取

簡單來說，a in (1,2,3) 和 a=1 or a=2 or a=3 是一樣的，between 1 and 2 和 a>1 and a<2 也是一樣的， 無需可以優(yōu)化。

6.6 索引存取類型

避免使用相同前綴的索引，也就是一個字段不要在多個索引上有相同的前綴。比如一個字段已經建立了唯一索引，這個時候如果再給他建立一個聯(lián)合索引，會導致優(yōu)化器并不知道你要使用哪個索引?；蛘吣憬饲熬Y相同的一個單索引，一個聯(lián)合索引，就算你寫上了條件，也不一定能用上聯(lián)合索引。當然，可以 force，這就另說了。

6.7 轉換

簡單的表達式可以進行轉換，比如 where -2 = a 會自動變成 where a= -2 ，但是如果牽扯到數學運算，就不能轉換了 比如 where 2= -a 這時候不會自動轉成 where a =-2.

第二條 sql 就可以使用索引

所以 我們在開發(fā)的過程中，需要注意 sql 的寫法，自覺寫成 where a=-2

6.8 and、union、order by、group by 等

1）and

and 條件后，如果都沒索引，掃描全表。有一個存取類型更好，見 5.4 , 會使用存儲類型更好的索引，如果都一樣，哪個索引先創(chuàng)建，用哪個。

2）union

union 每條語句單獨優(yōu)化

這里就會分別執(zhí)行兩條 sql，用到索引，再合并結果集

3）order by

order by 會過濾無效排序，比如一個字段本來就有索引

第二條 sql 和第一條的查詢效果是一樣的

所以，寫 sql 的時候，不要寫無用排序，比如 order by ‘xxx’ 這樣沒有意義。

4）group by

簡單來說 group by 的字段，有索引會走索引，group by a order by a 這里的 order by 等于沒寫，結果集已經是排序完畢的了，參考 6.8-3 order by
select distinct col_a from table a 等價于 select col_a from a group by col_a

7 索引下推

主要的核心點就在于把數據篩選的過程放在了存儲引擎層去處理，而不是像之前一樣放到 Server 層去做過濾。

如果在一張表上，name 和 age 都建立索引，查詢條件為 where name like ‘xx%’ and age=11, 在低版本的 mysql (5.6 以下) 的根據索引的最左匹配原則，可以得到放棄了 age，只根據 name 過濾數據。根據 name 拿到所有的 id 之后，再根據 id 回表。

高版本 mysql 里，沒有忽略 age 這個屬性，帶著 age 屬性過濾，直接過濾掉了 age 為 11 的數據，假設不根據 age 過濾的數據為 10 條，過濾后只剩 3 條，就少了 7 次回表。減少了 io 會大量減少性能消耗

8 小表驅動大表

小表驅動大表，也是我們聽慣了的話了，其含義主要是指小表的數據集驅動大表的數據集，減少連接次數。打個比方:

表 A 有 1w 數據，表 B 有 100w 數據，如果 A 表作為驅動表，處于循環(huán)的外層，那么只需要 1w 次的連接即可。如果 B 表在外層，那么則需要循環(huán) 100w 次。

下面我們實際測試看看，準備環(huán)境 mysql 5.7+

準備兩張表，一張表 ib_asn_d 數據 9175， 一張表 bs_itembase_ext_attr 數據 1584115，都在商品編碼字段上有索引。

首先小表驅動大表

多次反復測試，執(zhí)行時間大概 7 秒。
接下來看看大表驅動小表。

將近 300 秒，不是一個量級的。
接下來分別分析執(zhí)行計劃，執(zhí)行計劃里第一條就是驅動表。

小表驅動大表，大表用了索引，小表全表掃描，只掃描 8000 多行

大表驅動小表，大表全表掃描，需要掃描 147w 行。
經過多次測試得出了結論:

當使用 left join 時，左表是驅動表，右表是被驅動表；

當使用 right join 時，右表是驅動表，左表是被驅動表；

當使用 inner join 時，mysql 會選擇數據量比較小的表作為驅動表，大表作為被驅動表；

驅動表索引不生效，非驅動表索引生效

保證小表是驅動表很重要。

9 總結

覆蓋索引：如果查詢條件使用的是普通索引（或是聯(lián)合索引的最左原則字段），查詢結果是聯(lián)合索引的字段或是主鍵，不用回表操作，直接返回結果，減少 IO 磁盤讀寫讀取整行數據，所以高頻字段建立聯(lián)合索引是很有必要的

最左前綴：聯(lián)合索引的最左 N 個字段，也可以是字符串索引的最左 M 個字符。建立索引的時候，注意左前綴不要重復，避免查詢優(yōu)化器無法判定如何使用索引

索引下推：name like ‘hello%’and age >10 檢索，MySQL 5.6 版本之前，會對匹配的數據進行回表查詢。5.6 版本后，會先過濾掉 age<10 的數據，再進行回表查詢，減少回表率，提升檢索速度。







審核編輯：劉清