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