活動真實有效，僅限D(zhuǎn)D粉絲

• MySQL索引的本質(zhì)

• MySQL索引的底層原理

• MySQL索引的實戰(zhàn)經(jīng)驗

面試

問：數(shù)據(jù)庫中最常見的慢查詢優(yōu)化方式是什么？ 

同學(xué)A：加索引。

問：為什么加索引能優(yōu)化慢查詢？

同學(xué)A：...不知道

同學(xué)B：因為索引其實就是一種優(yōu)化查詢的數(shù)據(jù)結(jié)構(gòu)，比如Mysql中的索引是用B 樹實現(xiàn)的，而B 樹就是一種數(shù)據(jù)結(jié)構(gòu)，可以優(yōu)化查詢速度，可以利用索引快速查找數(shù)據(jù)，所以能優(yōu)化查詢。

問：你知道哪些數(shù)據(jù)結(jié)構(gòu)可以提高查詢速度？（聽到這個問題就感覺此處有坑...）

同學(xué)B：哈希表、完全平衡二叉樹、B樹、B 樹等等。

問：那這些數(shù)據(jù)結(jié)構(gòu)既然都能優(yōu)化查詢速度，那Mysql種為何選擇使用B 樹？

同學(xué)B：...不知道

提問

SHOW INDEX FROM employees.titles;                            

有一個titles表，主鍵由empno，title，fromdate三個字段組成。那么以下幾個語句會用到索引嗎?

1. select*fromemployees.titleswhereemp_no=1

2. select*fromemployees.titleswheretitle='1'

3. select*fromemployees.titleswhereemp_no='1'andtitle=1

4. select*fromemployees.titleswheretitle='1'andemp_no=1

為什么哈希表、完全平衡二叉樹、B樹、B 樹都可以優(yōu)化查詢，為何Mysql獨獨喜歡B 樹？哈希表有什么特點？

假如有這么一張表(表名：sanguo)：

現(xiàn)在對name字段建立哈希索引：

注意字段值所對應(yīng)的數(shù)組下標是哈希算法隨機算出來的，所以可能出現(xiàn)哈希沖突。那么對于這樣一個索引結(jié)構(gòu)，現(xiàn)在來執(zhí)行下面的sql語句： 

select * from sanguo where name='周瑜'

可以直接對‘周瑜’按哈希算法算出來一個數(shù)組下標，然后可以直接從數(shù)據(jù)中取出數(shù)據(jù)并拿到鎖對應(yīng)那一行數(shù)據(jù)的地址，進而查詢那一行數(shù)據(jù)。那么如果現(xiàn)在執(zhí)行下面的sql語句：

select * from sanguo where name>'周瑜'

則無能為力，因為哈希表的特點就是可以快速的精確查詢，但是不支持范圍查詢。

如果用完全平衡二叉樹呢？

還是上面的表數(shù)據(jù)用完全平衡二叉樹表示如下圖（為了簡單，數(shù)據(jù)對應(yīng)的地址就不畫在圖中了。）：

圖中的每一個節(jié)點實際上應(yīng)該有四部分：

1. 左指針，指向左子樹

2. 鍵值

3. 鍵值所對應(yīng)的數(shù)據(jù)的存儲地址

4. 右指針，指向右子樹

另外需要提醒的是，二叉樹是有順序的，簡單的說就是“左邊的小于右邊的”假如我們現(xiàn)在來查找‘周瑜’，需要找2次（第一次曹操，第二次周瑜），比哈希表要多一次。而且由于完全平衡二叉樹是有序的，所以也是支持范圍查找的。

如果用B樹呢？

還是上面的表數(shù)據(jù)用B樹表示如下圖（為了簡單，數(shù)據(jù)對應(yīng)的地址就不畫在圖中了。）：

可以發(fā)現(xiàn)同樣的元素，B樹的表示要比完全平衡二叉樹要“矮”，原因在于B樹中的一個節(jié)點可以存儲多個元素。

如果用B 樹呢？

還是上面的表數(shù)據(jù)用B 樹表示如下圖（為了簡單，數(shù)據(jù)對應(yīng)的地址就不畫在圖中了。）：

我們可以發(fā)現(xiàn)同樣的元素，B 樹的表示要比B樹要“胖”，原因在于B 樹中的非葉子節(jié)點會冗余一份在葉子節(jié)點中，并且葉子節(jié)點之間用指針相連。

那么B 樹到底有什么優(yōu)勢呢？

這里我們用“反證法”，假如我們現(xiàn)在就用完全平衡二叉樹作為索引的數(shù)據(jù)結(jié)構(gòu)，我們來看一下有什么不妥的地方。實際上，索引也是很“大”的，因為索引也是存儲元素的，我們的一個表的數(shù)據(jù)行數(shù)越多，那么對應(yīng)的索引文件其實也是會很大的，實際上也是需要存儲在磁盤中的，而不能全部都放在內(nèi)存中，所以我們在考慮選用哪種數(shù)據(jù)結(jié)構(gòu)時，我們可以換一個角度思考，哪個數(shù)據(jù)結(jié)構(gòu)更適合從磁盤中讀取數(shù)據(jù)，或者哪個數(shù)據(jù)結(jié)構(gòu)能夠提高磁盤的IO效率。回頭看一下完全平衡二叉樹，當我們需要查詢“張飛”時，需要以下步驟：

1. 從磁盤中取出“曹操”到內(nèi)存，CPU從內(nèi)存取出數(shù)據(jù)進行筆記，“張飛”<“曹操”，取左子樹（產(chǎn)生了一次磁盤IO）

2. 從磁盤中取出“周瑜”到內(nèi)存，CPU從內(nèi)存取出數(shù)據(jù)進行筆記，“張飛”>“周瑜”，取右子樹（產(chǎn)生了一次磁盤IO）

3. 從磁盤中取出“孫權(quán)”到內(nèi)存，CPU從內(nèi)存取出數(shù)據(jù)進行筆記，“張飛”>“孫權(quán)”，取右子樹（產(chǎn)生了一次磁盤IO）

4. 從磁盤中取出“黃忠”到內(nèi)存，CPU從內(nèi)存取出數(shù)據(jù)進行筆記，“張飛”=“張飛”，找到結(jié)果（產(chǎn)生了一次磁盤IO）

同理，回頭看一下B樹，我們發(fā)現(xiàn)只發(fā)送三次磁盤IO就可以找到“張飛”了，這就是B樹的優(yōu)點：一個節(jié)點可以存儲多個元素，相對于完全平衡二叉樹所以整棵樹的高度就降低了，磁盤IO效率提高了。

而B 樹是B樹的升級版，只是把非葉子節(jié)點冗余一下，這么做的好處是為了提高范圍查找的效率。

到這里可以總結(jié)出來，Mysql選用B 樹這種數(shù)據(jù)結(jié)構(gòu)作為索引，可以提高查詢索引時的磁盤IO效率，并且可以提高范圍查詢的效率，并且B 樹里的元素也是有序的。

那么，一個B 樹的節(jié)點中到底存多少個元素合適呢？

其實也可以換個角度來思考B 樹中一個節(jié)點到底多大合適？

答案是：B 樹中一個節(jié)點為一頁或頁的倍數(shù)最為合適。因為如果一個節(jié)點的大小小于1頁，那么讀取這個節(jié)點的時候其實也會讀出1頁，造成資源的浪費；如果一個節(jié)點的大小大于1頁，比如1.2頁，那么讀取這個節(jié)點的時候會讀出2頁，也會造成資源的浪費；所以為了不造成浪費，所以最后把一個節(jié)點的大小控制在1頁、2頁、3頁、4頁等倍數(shù)頁大小最為合適。

那么，Mysql中B 樹的一個節(jié)點大小為多大呢？

這個問題的答案是“1頁”，這里說的“頁”是Mysql自定義的單位（其實和操作系統(tǒng)類似），Mysql的Innodb引擎中一頁的默認大小是16k（如果操作系統(tǒng)中一頁大小是4k，那么Mysql中1頁=操作系統(tǒng)中4頁），可以使用命令SHOW GLOBALSTATUS like 'Innodbpagesize'; 查看。

并且還可以告訴你的是，一個節(jié)點為1頁就夠了。

為什么一個節(jié)點為1頁（16k）就夠了？

解決這個問題，我們先來看一下Mysql中利用B 樹的具體實現(xiàn)。如果想要這篇文章視頻資料的話可以掃一下下面這位小姐姐的微信，暗號：666。

Mysql中MyISAM和innodb使用B 樹

通常我們認為B 樹的非葉子節(jié)點不存儲數(shù)據(jù)，只有葉子節(jié)點才存儲數(shù)據(jù)；而B樹的非葉子和葉子節(jié)點都會存儲數(shù)據(jù)，會導(dǎo)致非葉子節(jié)點存儲的索引值會更少，樹的高度相對會比B 樹高，平均的I/O效率會比較低，所以使用B 樹作為索引的數(shù)據(jù)結(jié)構(gòu)，再加上B 樹的葉子節(jié)點之間會有指針相連，也方便進行范圍查找。上圖的data區(qū)域兩個存儲引擎會有不同。

MyISAM中的B 樹

MYISAM中葉子節(jié)點的數(shù)據(jù)區(qū)域存儲的是數(shù)據(jù)記錄的地址

主鍵索引

輔助索引

MyISAM存儲引擎在使用索引查詢數(shù)據(jù)時，會先根據(jù)索引查找到數(shù)據(jù)地址，再根據(jù)地址查詢到具體的數(shù)據(jù)。并且主鍵索引和輔助索引沒有太多區(qū)別。

InnoDB中的B 樹

InnoDB中主鍵索引的葉子節(jié)點的數(shù)據(jù)區(qū)域存儲的是數(shù)據(jù)記錄，輔助索引存儲的是主鍵值

主鍵索引

輔助索引

Innodb中的主鍵索引和實際數(shù)據(jù)時綁定在一起的，也就是說Innodb的一個表一定要有主鍵索引，如果一個表沒有手動建立主鍵索引，Innodb會查看有沒有唯一索引，如果有則選用唯一索引作為主鍵索引，如果連唯一索引也沒有，則會默認建立一個隱藏的主鍵索引（用戶不可見）。另外，Innodb的主鍵索引要比MyISAM的主鍵索引查詢效率要高（少一次磁盤IO），并且比輔助索引也要高很多。所以，我們在使用Innodb作為存儲引擎時，我們最好：

1. 手動建立主鍵索引

2. 盡量利用主鍵索引查詢

回到我們的問題：為什么一個節(jié)點為1頁（16k）就夠了？

對著上面Mysql中Innodb中對B 樹的實際應(yīng)用（主要看主鍵索引），可以發(fā)現(xiàn)B 樹中的一個節(jié)點存儲的內(nèi)容是：

§ 非葉子節(jié)點：主鍵 指針

§ 葉子節(jié)點：數(shù)據(jù)

那么，假設(shè)我們一行數(shù)據(jù)大小為1K，那么一頁就能存16條數(shù)據(jù)，也就是一個葉子節(jié)點能存16條數(shù)據(jù)；再看非葉子節(jié)點，假設(shè)主鍵ID為bigint類型，那么長度為8B，指針大小在Innodb源碼中為6B，一共就是14B，那么一頁里就可以存儲16K/14=1170個(主鍵 指針)，那么一顆高度為2的B 樹能存儲的數(shù)據(jù)為：117016=18720條，一顆高度為3的B 樹能存儲的數(shù)據(jù)為：11701170*16=21902400（千萬級條）。所以在InnoDB中B 樹高度一般為1-3層，它就能滿足千萬級的數(shù)據(jù)存儲。在查找數(shù)據(jù)時一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。所以也就回答了我們的問題，1頁=16k這么設(shè)置是比較合適的，是適用大多數(shù)的企業(yè)的，當然這個值是可以修改的，所以也能根據(jù)業(yè)務(wù)的時間情況進行調(diào)整。

最左前綴原則

我們模擬數(shù)據(jù)建立一個聯(lián)合索引 select*,concat(right(emp_no,1),'-',right(title,1),'-',right(from_date,2))fromemployees.titleslimit10;

那么對應(yīng)的B 樹為

我們判斷一個查詢條件能不能用到索引，我們要分析這個查詢條件能不能利用某個索引縮小查詢范圍

對于 select * from employees.titles where emp_no=1是能用到索引的，因為它能利用上面的索引所有查詢范圍，首先和第一個節(jié)點“4-r-01”比較，1<4，所以可以直接確定結(jié)果在左子樹，同理，依次按順序進行比較，逐步可以縮小查詢范圍。對于select * from employees.titles where title='1'是不能用到索引的，因為它不能用到上面的所以，和第一節(jié)點進行比較時，沒有empno這個字段的值，不能確定到底該去左子樹還是右子樹繼續(xù)進行查詢。對于 select * from employees.titles where title='1' and emp_no=1是能用到索引，按照我們的上面的分析，先用title='1'這個條件和第一個節(jié)點進行比較，是沒有結(jié)果的，但是mysql會對這個sql進行優(yōu)化，優(yōu)化之后會將empno=1這個條件放到第一位，從而可以利用索引。