全面透徹，深刻理解 MySQL 索引
對(duì)于 MySQL 索引，相信每位后端同學(xué)日常工作中經(jīng)常會(huì)用到，但是對(duì)其索引原理，卻可能未曾真正深入了解。B- 樹(shù)和 B+ 樹(shù)是 MySQL 索引使用的數(shù)據(jù)結(jié)構(gòu)，對(duì)于索引優(yōu)化和原理理解都非常重要，下面就揭開(kāi) B- 樹(shù)和 B+ 樹(shù)的神秘面紗，讓大家在面試的時(shí)候碰到這個(gè)知識(shí)點(diǎn)一往無(wú)前，不再成為你前進(jìn)的羈絆！
本文主要內(nèi)容：
- MySQL 查詢耗時(shí)分析，抓性能優(yōu)化核心問(wèn)題點(diǎn)
- 常見(jiàn)用于查詢的數(shù)據(jù)結(jié)構(gòu)，性能優(yōu)劣對(duì)比
- B-Tree 與 B+Tree 如何選擇，結(jié)合場(chǎng)景來(lái)做分析更靠譜
- InnoDB 中的索引介紹，知己知彼，應(yīng)用得心應(yīng)手
一、查詢耗時(shí)分析
我們首先進(jìn)行下查詢耗時(shí)分析，抓性能優(yōu)化核心問(wèn)題點(diǎn)。
1.1 記錄讀取順序
MYSQL維護(hù)著自己的緩存空間，如果要讀取一條記錄，根據(jù)優(yōu)先順序，路徑如下：
緩存區(qū) => 磁盤(pán)緩存區(qū) => 磁盤(pán)1.1.1 緩存區(qū)讀取
這是成本最低的方式，可以直接被CPU使用，不涉及磁盤(pán)IO，可以考慮IO時(shí)間為0。
1.1.2 從磁盤(pán)緩存區(qū)讀取
如果磁盤(pán)緩存區(qū)有需要的記錄，則只需要直接讀出，傳輸時(shí)間考慮為1ms。
1.1.3 從磁盤(pán)讀取
由于SSD比較貴，常用的還是機(jī)械硬盤(pán)，對(duì)于機(jī)械硬盤(pán)，要讀取指定地址的數(shù)據(jù)，是需要經(jīng)過(guò)尋道的，機(jī)械臂需要先移動(dòng)到指定位置，因此無(wú)論讀取多少數(shù)據(jù)，準(zhǔn)備工作都會(huì)耗費(fèi)一段時(shí)間。整個(gè)IO流程包括：排隊(duì)等待 => 尋道 => 半圈旋轉(zhuǎn) => 傳輸。
圖片
一次隨機(jī)讀取中，有90%的時(shí)間都花費(fèi)在排隊(duì)和準(zhǔn)備工作，真正的傳輸時(shí)間只有1ms，但總I/O時(shí)間卻為10ms。
當(dāng)隨機(jī)讀取10頁(yè)，就需要 10*10=100ms，但如果是順序讀，對(duì)于傳輸速度為40MB/s的硬盤(pán)，讀取一個(gè)4kb的頁(yè)僅需要0.1ms，即使順序讀取100頁(yè)，也只需要1頁(yè)隨機(jī)讀99頁(yè)順序讀，也就是10ms+9.9ms=19.9ms。
速度差距幾十倍，這也是為何我們想要盡量保證需要讀取的數(shù)據(jù)都在物理上排列在一起，因?yàn)檫@樣就可以順序讀取多個(gè)頁(yè)，而不需要進(jìn)行多次隨機(jī)讀取。
這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：
當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。
通過(guò)以上分析可知：對(duì)于數(shù)據(jù)讀取速度的優(yōu)化，主要就是需要降低IO時(shí)間，而降低IO時(shí)間的關(guān)鍵，就在于減少隨機(jī)讀次數(shù)以及讀取更少的數(shù)據(jù)。
二、常見(jiàn)查詢數(shù)據(jù)結(jié)構(gòu)對(duì)比
在此梳理常見(jiàn)用于查詢的數(shù)據(jù)結(jié)構(gòu)，性能優(yōu)劣大比拼。
2.1 二叉查找樹(shù)
二叉查找樹(shù)（Binary Search Tree），亦稱二叉搜索樹(shù)。是數(shù)據(jù)結(jié)構(gòu)中的一類。在一般情況下，查詢效率比鏈表結(jié)構(gòu)要高。
如圖所示：
圖片
查詢數(shù)據(jù)的效率不穩(wěn)定，若樹(shù)左右比較平衡的時(shí)，最差情況為O(logN)，如果插入數(shù)據(jù)是有序的，退化為了鏈表，查詢時(shí)間變成了O(N)。
數(shù)據(jù)量大的情況下，會(huì)導(dǎo)致樹(shù)的高度變高，如果每個(gè)節(jié)點(diǎn)對(duì)應(yīng)磁盤(pán)的一個(gè)塊來(lái)存儲(chǔ)一條數(shù)據(jù)，需IO次數(shù)大幅增加，顯然用此結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)是不可取的。
2.2 平衡二叉樹(shù)（AVL樹(shù)）
平衡二叉樹(shù)（Balanced Binary Tree）指的是棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。
如圖所示：
圖片
如果數(shù)據(jù)都存儲(chǔ)在內(nèi)存中，采用AVL樹(shù)來(lái)存儲(chǔ)，還是可以的，查詢效率非常高。不過(guò)我們的數(shù)據(jù)是存在磁盤(pán)中，用過(guò)采用這種結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)磁盤(pán)塊，數(shù)據(jù)量大的時(shí)候，也會(huì)和二叉樹(shù)一樣，會(huì)導(dǎo)致樹(shù)的高度變高，這樣邏輯上很近的節(jié)點(diǎn)實(shí)際可能非常遠(yuǎn)，無(wú)法很好的利用磁盤(pán)預(yù)讀（局部性原理），會(huì)增加IO次數(shù)，顯然用這種結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)也是不可取的。
2.3 B-樹(shù)
B樹(shù)（英語(yǔ)：B-tree），這里的 B 表示 balance( 平衡的意思)，是一種自平衡的樹(shù)，能夠保持?jǐn)?shù)據(jù)有序，B-樹(shù)允許每個(gè)節(jié)點(diǎn)有更多的子節(jié)點(diǎn)。
如圖所示：
圖片
B-樹(shù)不利于范圍查找，范圍查找也是我們經(jīng)常用到的，所以B-樹(shù)也不太適合在磁盤(pán)中存儲(chǔ)需要檢索的數(shù)據(jù)。
2.4 B+樹(shù)
B+樹(shù)是 B-樹(shù)的一個(gè)升級(jí)版，也是一種多路搜索樹(shù)，相對(duì)于 B 樹(shù)來(lái)說(shuō) B+樹(shù)更充分的利用了節(jié)點(diǎn)的空間，讓查詢速度更加穩(wěn)定，其速度完全接近于二分法查找。B+樹(shù)元素自底向上插入，這與二叉樹(shù)恰好相反。
如圖所示：
圖片
如上圖所示，每個(gè)節(jié)點(diǎn)占用一個(gè)盤(pán)塊的磁盤(pán)空間，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹(shù)根節(jié)點(diǎn)的指針，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤(pán)塊的地址。
2.5 B-Tree vs B+Tree
對(duì)于B-Tree和B+Tree，我們?cè)撊绾芜x擇呢？結(jié)合場(chǎng)景來(lái)做分析更靠譜。
讓我們來(lái)想想平時(shí)的高頻查詢場(chǎng)景吧，大概存在如下幾種：
- 按照id查詢唯一一條記錄
- 查找某個(gè)范圍的所有記錄
接下來(lái)，just do it！
2.5.1 場(chǎng)景：按照id查詢唯一一條記錄
圖片
B-樹(shù) 模擬查找關(guān)鍵字20的過(guò)程(3次io操作+內(nèi)存中二分法))：
- 根據(jù)根節(jié)點(diǎn)找到磁盤(pán)塊1，讀入內(nèi)存?！敬疟P(pán)I/O操作第1次】
- 比較關(guān)鍵字20在區(qū)間（12，32），找到磁盤(pán)塊1的指針P2
- 根據(jù)P2指針找到磁盤(pán)塊3，讀入內(nèi)存?！敬疟P(pán)I/O操作第2次】
- 比較關(guān)鍵字20在區(qū)間（15，26），找到磁盤(pán)塊3的指針P2
- 根據(jù)P2指針找到磁盤(pán)塊7，讀入內(nèi)存。【磁盤(pán)I/O操作第3次】
- 在磁盤(pán)塊7中的關(guān)鍵字列表中找到關(guān)鍵字20
如果我們是關(guān)鍵字 15 的話 ,那就是2次io操作+內(nèi)存中二分法。但是如果是B+樹(shù)，就只能通讀到底了。
2.5.2 場(chǎng)景：查找某個(gè)范圍的所有記錄
圖片
B-樹(shù)要查找[8，52]區(qū)間的數(shù)據(jù)，需要訪問(wèn)8個(gè)磁盤(pán)塊（1/2/6/3/7/8/4/9），IO次數(shù)又上去了。
2.5.3 小結(jié)
故B-Tree vs B+Tree兩種在索引的區(qū)別如下：
1.B-Tree查找某個(gè)關(guān)鍵字的效率更高
B-Tree因?yàn)榉侨~子結(jié)點(diǎn)也保存具體數(shù)據(jù)，所以在查找某個(gè)關(guān)鍵字的時(shí)候找到即可返回。而B(niǎo)+Tree所有的數(shù)據(jù)都在葉子結(jié)點(diǎn)，每次查找都得到葉子結(jié)點(diǎn)。所以在同樣高度的B-Tree和B+Tree中，B-Tree查找某個(gè)關(guān)鍵字的效率更高。
2.B-Tree不利于范圍查詢
由于B+Tree所有的數(shù)據(jù)都在葉子結(jié)點(diǎn)，并且結(jié)點(diǎn)之間有指針連接，在找大于某個(gè)關(guān)鍵字或者小于某個(gè)關(guān)鍵字的數(shù)據(jù)的時(shí)候，B+Tree只需要找到該關(guān)鍵字然后沿著鏈表遍歷就可以了，而B(niǎo)-Tree還需要遍歷該關(guān)鍵字結(jié)點(diǎn)的根結(jié)點(diǎn)去搜索。
3.B-Tree的深度會(huì)更大
由于B-Tree的每個(gè)結(jié)點(diǎn)（這里的結(jié)點(diǎn)可以理解為一個(gè)數(shù)據(jù)頁(yè)）都存儲(chǔ)主鍵+實(shí)際數(shù)據(jù)，而B(niǎo)+Tree非葉子結(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字信息，而每個(gè)頁(yè)的大小有限是有限的，所以同一頁(yè)能存儲(chǔ)的B-Tree的數(shù)據(jù)會(huì)比B+Tree存儲(chǔ)的更少。這樣同樣總量的數(shù)據(jù)，B-Tree的深度會(huì)更大，增大查詢時(shí)的磁盤(pán)I/O次數(shù)，進(jìn)而影響查詢效率。
4.B+樹(shù)的磁盤(pán)讀寫(xiě)代價(jià)更低
B+樹(shù)的內(nèi)部節(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針，因此其內(nèi)部節(jié)點(diǎn)相對(duì)B樹(shù)更小，如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多，一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多，相對(duì)IO讀寫(xiě)次數(shù)就降低了。
5.B+樹(shù)的查詢效率更加穩(wěn)定
由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。
三、InnoDB中的索引
InnoDB 中的索引介紹，知己知彼，應(yīng)用起來(lái)得心應(yīng)手。
3.1 InnoDB索引實(shí)現(xiàn)
InnoDB數(shù)據(jù)頁(yè)有7個(gè)組成部分，各個(gè)數(shù)據(jù)頁(yè)可以組成一個(gè)雙向鏈表。而每個(gè)數(shù)據(jù)頁(yè)中的記錄會(huì)按照主鍵值從小到大的順序組成一個(gè)單向鏈表，每個(gè)數(shù)據(jù)頁(yè)都會(huì)為存儲(chǔ)在它里邊兒的記錄生成一個(gè)頁(yè)目錄。在通過(guò)主鍵查找某條記錄的時(shí)候可以在頁(yè)目錄中使用二分法快速定位到對(duì)應(yīng)的槽，然后再遍歷該槽對(duì)應(yīng)分組中的記錄即可快速找到指定的記錄。
頁(yè)和記錄的關(guān)系示意圖如下：
圖片
索引同樣存儲(chǔ)在數(shù)據(jù)頁(yè)中，只不過(guò)目錄項(xiàng)中的兩個(gè)列是主鍵和頁(yè)號(hào)。
那InnoDB怎么區(qū)分一條記錄是普通的用戶記錄還是目錄項(xiàng)記錄呢？是根據(jù)記錄頭信息里的record_type屬性，它的各個(gè)取值代表的意思如下：
0：普通的用戶記錄
1：目錄項(xiàng)記錄
2：最小記錄
3：最大記錄
3.2 查找步驟
整體結(jié)構(gòu)如下：
圖片
現(xiàn)在如果我們想根據(jù)主鍵值查找一條用戶記錄大致需要3個(gè)步驟，以查找主鍵值為20的記錄為例：
1、確定目錄項(xiàng)記錄頁(yè)。
2、通過(guò)目錄項(xiàng)記錄頁(yè)確定用戶記錄真實(shí)所在的頁(yè)。
3、在真實(shí)存儲(chǔ)用戶記錄的頁(yè)中定位到具體的記錄。
四、InnoDB中的索引分類
InnoDB 中的索引類別介紹，明確后期應(yīng)用注意事項(xiàng)。
4.1 聚簇索引
上邊介紹的B+樹(shù)索引。它有兩個(gè)特點(diǎn)：
1.根據(jù)記錄主鍵值的大小進(jìn)行記錄和頁(yè)的排序
這包括三個(gè)方面的含義：
- 頁(yè)內(nèi)的記錄是按照主鍵的大小順序排成一個(gè)單向鏈表。
- 各個(gè)存放用戶記錄的頁(yè)也是根據(jù)主鍵大小順序排成一個(gè)雙向鏈表。
- 存放目錄項(xiàng)記錄的頁(yè)分為不同的層次，在同一層次中的頁(yè)也是根據(jù)頁(yè)中目錄項(xiàng)記錄的主鍵大小順序排成一個(gè)雙向鏈表。
2.B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)的是完整的用戶記錄
我們把具有這兩種特性的B+樹(shù)稱為聚簇索引，所有完整的用戶記錄都存放在這個(gè)聚簇索引的葉子節(jié)點(diǎn)處。
4.2 二級(jí)索引
上邊介紹的聚簇索引只能在搜索條件是主鍵值時(shí)才能發(fā)揮作用，因?yàn)锽+樹(shù)中的數(shù)據(jù)都是按照主鍵進(jìn)行排序的。
那如果我們想以別的列作為搜索條件該咋辦呢？
難道只能從頭到尾沿著鏈表依次遍歷記錄么？
我們可以多建幾棵B+樹(shù)，不同的B+樹(shù)中的數(shù)據(jù)采用不同的排序規(guī)則。比方說(shuō)我們用c2列的大小作為數(shù)據(jù)頁(yè)、頁(yè)中記錄的排序規(guī)則，再建一棵B+樹(shù)，效果如下圖所示：
圖片
但是但是這個(gè)B+樹(shù)的葉子節(jié)點(diǎn)中的記錄只存儲(chǔ)了c2和c1（也就是主鍵）兩個(gè)列，所以我們必須再根據(jù)主鍵值去聚簇索引中再查找一遍完整的用戶記錄。
由于主鍵值具有唯一性，二級(jí)索引不具有唯一性，那么 新的問(wèn)題來(lái)了：
圖片
在上圖中，如果我們想新插入一行記錄，其中c1、c2、c3的值分別是：9、1、'c'。
那么在修改這個(gè)為c2列建立的二級(jí)索引對(duì)應(yīng)的B+樹(shù)時(shí)便碰到了個(gè)大問(wèn)題：
由于頁(yè)3中存儲(chǔ)的目錄項(xiàng)記錄是由c2列 + 頁(yè)號(hào)的值構(gòu)成的，頁(yè)3中的兩條目錄項(xiàng)記錄對(duì)應(yīng)的c2列的值都是1，而我們新插入的這條記錄的c2列的值也是1，那我們這條新插入的記錄到底應(yīng)該放到頁(yè)4中，還是應(yīng)該放到頁(yè)5中?。裤卤屏恕?/p>
為了讓新插入記錄能找到自己在那個(gè)頁(yè)里，我們需要保證在B+樹(shù)的同一層內(nèi)節(jié)點(diǎn)的目錄項(xiàng)記錄除頁(yè)號(hào)這個(gè)字段以外是唯一的。
所以對(duì)于二級(jí)索引的內(nèi)節(jié)點(diǎn)的目錄項(xiàng)記錄的內(nèi)容實(shí)際上是由三個(gè)部分構(gòu)成的：1、索引列的值2、主鍵值3、頁(yè)號(hào)。
我們?yōu)閏2列建立二級(jí)索引后的示意圖實(shí)際上應(yīng)該是這樣子的：
圖片
4.3 聯(lián)合索引
我們可以同時(shí)以多個(gè)列的大小作為排序規(guī)則，也就是同時(shí)為多個(gè)列建立索引，比方說(shuō)我們想讓B+樹(shù)按照c2和c3列的大小進(jìn)行排序，這個(gè)包含兩層含義：
1.先把各個(gè)記錄和頁(yè)按照c2列進(jìn)行排序；
2.在記錄的c2列相同的情況下，采用c3列進(jìn)行排序。
五、總結(jié)
MySQL 普遍采用 B+Tree 實(shí)現(xiàn)，索引本身很大，不可能全部存儲(chǔ)內(nèi)存，因此需要以索引文件的形式存儲(chǔ)磁盤(pán)。相對(duì)于內(nèi)存讀取，I/O 存取的消耗要高幾個(gè)數(shù)量級(jí)，由于 MySQL 數(shù)據(jù)存儲(chǔ)保存在磁盤(pán)中，所以在查詢時(shí)磁盤(pán) I/O 是其主要查詢性能瓶頸，而使用索引就可以減少磁盤(pán) I/O。
索引的原理其實(shí)是不斷的縮小查找范圍， 就如我們平時(shí)用字典查單詞一樣，先找首字母縮小范圍，再第二個(gè)字母等等。
對(duì)于B-樹(shù)、B+樹(shù)而言，當(dāng)高固定情況下，寬度越大索引性能越好。
