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

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

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

1）沒有索引的情況下訪問數(shù)據(jù)：

2）使用平衡二叉樹結(jié)構(gòu)索引的情況下訪問數(shù)據(jù)：

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

2 索引的組成部分和種類

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

2.1 hash

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

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

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

優(yōu)點(diǎn)：insert 迅速，只需往后補(bǔ)就行

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

總結(jié)：想成 java 的 hashmap 即可

2.2 有序數(shù)組

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

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

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

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

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

總結(jié)：就是順序排的數(shù)組

2.3 二叉搜索樹

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

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

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

缺點(diǎn)：數(shù)據(jù)量大的時候，樹會過高，導(dǎo)致多次訪問磁盤

優(yōu)點(diǎn)：進(jìn)化成多叉樹，會降低樹高，訪問磁盤次數(shù)。

場景：適用很多場景

總結(jié)：左小右大的樹

2.4 B 樹

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

這種數(shù)據(jù)結(jié)構(gòu)我們稱為 B 樹，B 樹是一種多叉平衡查找樹

2.5 B + 樹

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

B 樹：非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)都會存儲數(shù)據(jù)。

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

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

3 索引的維護(hù)

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

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

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

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

4 回表

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

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

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

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

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

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

5 索引覆蓋

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

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

一般索引覆蓋適用的場景包括 全表 count 查詢優(yōu)化、列查詢回表、分頁回表。高版本的 mysql 已經(jīng)做了優(yōu)化，當(dāng)命中聯(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ā)現(xiàn) a 在等值的情況下，b 值又是按順序排列的，但是這種順序是相對的。這是因為 MySQL 創(chuàng)建聯(lián)合索引的規(guī)則是首先會對聯(lián)合索引的最左邊第一個字段排序，在第一個字段的排序基礎(chǔ)上，然后在對第二個字段進(jì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 是不符合索引字段的順序的，應(yīng)該不能使用索引才對，但是實際情況卻和我們期望的不太一樣，這是為啥呢？

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

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

6.1 條件轉(zhuǎn)化

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

6.3 提前計算

包含數(shù)學(xué)運(yùn)算的部分，例如 where a= 1+2 會幫你算好，where a=3

6.4 存取類型

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

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

const 常量表

eq_ref unique/primary 索引，并且使用的是’=’進(jìn)行存取

ref 索引使用’=’進(jìn)行存取

ref_or_null 索引使用’=’進(jìn)行存取，并且有可能為 NULL

range 索引使用 BETWEEN、IN、>=、LIKE 等進(jìn)行存取

index 索引全掃描

ALL 表全掃描

經(jīng)?？磮?zhí)行計劃的，一眼就能看出來這是啥意思，舉個例子

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

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 索引存取類型

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

6.7 轉(zhuǎn)換

簡單的表達(dá)式可以進(jìn)行轉(zhuǎn)換，比如 where -2 = a 會自動變成 where a= -2 ，但是如果牽扯到數(shù)學(xué)運(yùn)算，就不能轉(zhuǎn)換了 比如 where 2= -a 這時候不會自動轉(zhuǎn)成 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 每條語句單獨(dú)優(yōu)化

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

3）order by

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

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

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

4）group by

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

7 索引下推

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

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

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

8 小表驅(qū)動大表

小表驅(qū)動大表，也是我們聽?wèi)T了的話了，其含義主要是指小表的數(shù)據(jù)集驅(qū)動大表的數(shù)據(jù)集，減少連接次數(shù)。打個比方:

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

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

準(zhǔn)備兩張表，一張表 ib_asn_d 數(shù)據(jù) 9175， 一張表 bs_itembase_ext_attr 數(shù)據(jù) 1584115，都在商品編碼字段上有索引。

首先小表驅(qū)動大表

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

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

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

大表驅(qū)動小表，大表全表掃描，需要掃描 147w 行。
經(jīng)過多次測試得出了結(jié)論:

當(dāng)使用 left join 時，左表是驅(qū)動表，右表是被驅(qū)動表；

當(dāng)使用 right join 時，右表是驅(qū)動表，左表是被驅(qū)動表；

當(dāng)使用 inner join 時，mysql 會選擇數(shù)據(jù)量比較小的表作為驅(qū)動表，大表作為被驅(qū)動表；

驅(qū)動表索引不生效，非驅(qū)動表索引生效

保證小表是驅(qū)動表很重要。

9 總結(jié)

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

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

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







審核編輯：劉清