前言
前面已經寫了有兩篇章長度的文章，第三篇我一直在尋思著要寫什麼（其實並沒有），按照腦圖來的話，這篇文章我們該來講講關於索引的知識了，這可是 MySQL 性能優化很關鍵的知識點，千萬千萬不要錯過，不過我這裡會相對比較深入地探究，相信大家讀完之後多少會有點收穫。
先送上兩張飛機票還沒讀過前面文章的夥伴可以先前往閱讀，由淺入深：
MySQL相關（一）- 一條查詢語句是如何執行的
MySQL相關（二）- 一條更新語句是如何執行的
由於索引的知識點比較多，官網的內容也很多，如果大家想詳細瞭解可以到官網，想先通讀了解的話可以先看看我對索引的總結，這一章節分為三部分來講：
- innodb 邏輯存儲結構需要了解，作為番外篇
MySQL相關（番外篇）- innodb 邏輯存儲結構；
- 索引的數據結構也作為另外的篇章，通過對查詢算法的數據模型進行演算分析
MySQL相關（三）- 索引數據模型推演及 B+Tree 的詳細介紹；
- 對索引的使用及優化規則也會作為單獨的篇章
MySQL相關（四）- 性能優化關鍵點索引
前面提到的腦圖如下，想要完整高清圖片可以到微信我的公眾號下【6曦軒】下回復 MySQL 腦圖獲取：
正文
MySQL索引數據模型推演
二分查找
雙十一過去之後，你女朋友跟你玩了一個猜數字的遊戲。(假設程序員 new 了一個會購物的女朋友出來) 猜猜我昨天買了多少錢，給你五次機會。 10000？低了。30000？高了。 接下來你會猜多少？ 20000。為什麼你不猜 11000，也不猜 29000 呢？
其實這個就是二分查找的一種思想，也叫折半查找，每一次，我們都把候選數據縮小了一半。如果數據已經排過序的話，這種方式效率比較高。
所以第一個，我們可以考慮用有序數組作為索引的數據結構。
有序數組的等值查詢和比較查詢效率非常高，但是更新數據的時候會出現一個問題，可能要挪動大量的數據（改變 index），所以只適合存儲靜態的數據。
為了支持頻繁的修改，比如插入數據，我們需要採用鏈表。鏈表的話，如果是單鏈表，它的查找效率還是不夠高。
那麼，有沒有可以使用二分查找的鏈表呢？
為了解決這個問題，BST（Binary Search Tree）也就是我們所說的二叉查找樹誕生了。
二叉查找樹
二叉查找樹的特點是什麼？ 左子樹所有的節點都小於父節點，右子樹所有的節點都大於父節點。投影到平面以後，就是一個有序的線性表。
二叉查找樹既能夠實現快速查找，又能夠實現快速插入。
- 但是二叉查找樹有一個問題：
它的查找耗時是和這棵樹的深度相關的，在最壞的情況下時間複雜度會退化成 O(n)。
- 什麼情況是最壞的情況呢？
我們打開這樣一個網站來看一下，這裡面有各種各樣的數據結構的動態演示，包括 BST 二叉查找樹： www.cs.usfca.edu/~galles/vis… 還是剛才的這一批數字，如果我們插入的數據剛好是有序的，2、6、11、13、17、 22。 這個時候我們的二叉查找樹變成了什麼樣了呢？
它會變成鏈表（這種樹也叫做“斜樹”），這種情況下不能達到加快檢索速度的目的，和順序查找效率是沒有區別的。
- 造成它傾斜的原因是什麼呢？
因為左右子樹深度差太大，這棵樹的左子樹根本沒有節點——也就是它不夠平衡。
- 所以，我們有沒有左右子樹深度相差不是那麼大，更加平衡的樹呢？
這個就是平衡二叉樹，叫做 Balanced binary search trees，或者 AVL 樹（AVL 是發明這個數據結構的人的名字）。
平衡二叉樹
AVL Trees (Balanced binary search trees) 平衡二叉樹的定義：
左右子樹深度差絕對值不能超過 1。
- 是什麼意思呢？
比如左子樹的深度是 2，右子樹的深度只能是 1 或者 3。 這個時候我們再按順序插入 1、2、3、4、5、6，一定是這樣，不會變成一棵“斜樹”。
- 那它的平衡是怎麼做到的呢？怎麼保證左右子樹的深度差不能超過 1 呢？
www.cs.usfca.edu/~galles/vis… 插入 1、2、3。 我們注意看：當我們插入了 1、2 之後，如果按照二叉查找樹的定義，3 肯定是要在 2 的右邊的，這個時候根節點 1 的右節點深度會變成 2，但是左節點的深度是 0，因為它沒有子節點，所以就會違反平衡二叉樹的定義。
那應該怎麼辦呢？因為它是右節點下面接一個右節點，右-右型，所以這個時候我們要把 2 提上去，這個操作叫做左旋。 同樣的，如果我們插入 7、6、5，這個時候會變成左左型，就會發生右旋操作，把 6 提上去。 所以為了保持平衡，AVL 樹在插入和更新數據的時候執行了一系列的計算和調整的操作。
- 平衡的問題我們解決了，那麼平衡二叉樹作為索引怎麼查詢數據？
- 在平衡二叉樹中，一個節點，它的大小是一個固定的單位，作為索引應該存儲什麼內容？
它應該存儲三塊的內容：
- 索引的鍵值。比如我們在 id 上面創建了一個索引，我在用 where id =1 的條件查詢的時候就會找到索引裡面的 id 的這個鍵值。
- 數據的磁盤地址，因為索引的作用就是去查找數據的存放的地址。
- 因為是二叉樹，它必須還要有左子節點和右子節點的引用，這樣我們才能找到下一個節點。比如大於 26 的時候，走右邊，到下一個樹的節點，繼續判斷。
如果是這樣存儲數據的話，我們來看一下會有什麼問題。 在分析用 AVL 樹存儲索引數據之前，我們先來學習一下 InnoDB 的邏輯存儲結構。 innodb 的邏輯存儲結構
AVL 樹用於存儲索引數據
首先，索引的數據，是放在硬盤上的。查看數據和索引的大小：
<code>SELECTCONCAT(ROUND(SUM(DATA_LENGTH / 1024 / 1024) , 2) ,'MB') AS data_len ,CONCAT(ROUND(SUM(INDEX_LENGTH / 1024 / 1024) , 2) ,'MB') AS index_lenFROMinformation_schema. TABLESWHEREtable_schema = 'gupao'AND table_name = 'user_innodb';複製代碼/<code>
當我們用樹的結構來存儲索引的時候，訪問一個節點就要跟磁盤之間發生一次 IO。
InnoDB 操作磁盤的最小的單位是一頁（或者叫一個磁盤塊），大小是 16K(16384 字節)。
那麼，一個樹的節點就是 16K 的大小。
如果我們一個節點只存一個鍵值+數據+引用，例如整形的字段，可能只用了十幾個或者幾十個字節，它遠遠達不到 16K 的容量，所以訪問一個樹節點，進行一次 IO 的時候，浪費了大量的空間。
所以如果每個節點存儲的數據太少，從索引中找到我們需要的數據，就要訪問更多的節點，意味著跟磁盤交互次數就會過多。
如果是機械硬盤時代，每次從磁盤讀取數據需要 10ms 左右的尋址時間，交互次數越多，消耗的時間就越多。
比如上面這張圖，我們一張表裡面有 6 條數據，當我們查詢 id=37 的時候，要查詢兩個子節點，就需要跟磁盤交互 3 次，如果我們有幾百萬的數據呢？這個時間更加難以估計。
- 所以我們的解決方案是什麼呢？
讓每個節點存儲更多的數據。 節點上的關鍵字的數量越多，我們的指針數也越多，也就是意味著可以有更多的分叉（我們把它叫做“路數”）。
因為分叉數越多，樹的深度就會減少（根節點是 0）。
這樣，我們的樹是不是從原來的高瘦高瘦的樣子，變成了矮胖矮胖的樣子？
這個時候，我們的樹就不再是二叉了，而是多叉，或者叫做多路。
多路平衡查找樹（B Tree）（分裂、合併）
Balanced Tree 這個就是我們的多路平衡查找樹，叫做 B Tree（B 代表平衡）。 跟 AVL 樹一樣，B 樹在枝節點和葉子節點存儲鍵值、數據地址、節點引用。 它有一個特點：分叉數（路數）永遠比關鍵字數多 1。比如我們畫的這棵樹，每個節 點存儲兩個關鍵字，那麼就會有三個指針指向三個子節點。
B Tree 的查找規則是什麼樣的呢？ 比如我們要在這張表裡面查找 15。 因為 15 小於 17，走左邊。 因為 15 大於 12，走右邊。 在磁盤塊 7 裡面就找到了 15，只用了 3 次 IO。 這個是不是比 AVL 樹效率更高呢？ 那 B Tree 又是怎麼實現一個節點存儲多個關鍵字，還保持平衡的呢？跟 AVL 樹有什 麼區別？
www.cs.usfca.edu/~galles/vis…
比如 Max Degree（路數）是 3 的時候，我們插入數據 1、2、3，在插入 3 的時候， 本來應該在第一個磁盤塊，但是如果一個節點有三個關鍵字的時候，意味著有 4 個指針， 子節點會變成 4 路，所以這個時候必須進行分裂。把中間的數據 2 提上去，把 1 和 3 變 成 2 的子節點。
如果刪除節點，會有相反的合併的操作。 注意這裡是分裂和合並，跟 AVL 樹的左旋和右旋是不一樣的。 我們繼續插入 4 和 5，B Tree 又會出現分裂和合並的操作。
從這個裡面我們也能看到，在更新索引的時候會有大量的索引的結構的調整，所以解釋了為什麼我們不要在頻繁更新的列上建索引，或者為什麼不要更新主鍵。 節點的分裂和合並，其實就是 InnoDB 頁的分裂和合並。
B+樹（加強版多路平衡查找樹）
B Tree 的效率已經很高了，為什麼 MySQL 還要對 B Tree 進行改良，最終使用了 B+Tree 呢？總體上來說，這個 B 樹的改良版本解決的問題比 B Tree 更全面。 我們來看一下 InnoDB 裡面的 B+樹的存儲結構：
MySQL 中的 B+Tree 有幾個特點：
它的關鍵字的數量是跟路數相等的； B+Tree 的根節點和枝節點中都不會存儲數據，只有葉子節點才存儲數據。搜索 到關鍵字不會直接返回，會到最後一層的葉子節點。比如我們搜索 id=28，雖然在第一 層直接命中了，但是全部的數據在葉子節點上面，所以我還要繼續往下搜索，一直到葉 子節點。 舉個例子：假設一條記錄是 1K，一個葉子節點（一頁）可以存儲 16 條記錄。非葉 子節點可以存儲多少個指針？ 假設索引字段是 bigint 類型，長度為 8 字節。指針大小在 InnoDB 源碼中設置為 6 字節，這樣一共 14 字節。非葉子節點（一頁）可以存儲 16384 / 14 = 1170 個這樣的 單元（鍵值+指針），代表有 1170 個指針。 樹深度為 2 的時候， 有 1170^2 個葉子節點 ，可以存儲的數據為 1170 * 1170 * 16 = 21902400。 在查找數據時一次頁的查找代表一次 IO，也就是說，一張 2000 萬左右的表，查詢數據最多需要訪問 3 次磁盤。 所以在 InnoDB 中 B+ 樹深度一般為 1-3 層，它就能滿足千萬級的數據存儲。 B+Tree 的每個葉子節點增加了一個指向相鄰葉子節點的指針，它的最後一個數 據會指向下一個葉子節點的第一個數據，形成了一個有序鏈表的結構。 它是根據左閉右開的區間 [ )來檢索數據。
我們來看一下 B+Tree 的數據搜尋過程：
1）比如我們要查找 28，在根節點就找到了鍵值，但是因為它不是頁子節點，所以會繼續往下搜尋，28 是[28,66)的左閉右開的區間的臨界值，所以會走中間的子節點，然後繼續搜索，它又是[28,34)的左閉右開的區間的臨界值，所以會走左邊的子節點，最後在葉子節點上找到了需要的數據。
2）第二個，如果是範圍查詢，比如要查詢從 22 到 60 的數據，當找到 22 之後，只需要順著節點和指針順序遍歷就可以一次性訪問到所有的數據節點，這樣就極大地提高了區間查詢效率（不需要返回上層父節點重複遍歷查找）。
總結一下，InnoDB 中的 B+Tree 的特點：
它是 B Tree 的變種，B Tree 能解決的問題，它都能解決。B Tree 解決的兩大問題是什麼？（每個節點存儲更多關鍵字；路數更多） 掃庫、掃表能力更強（如果我們要對錶進行全表掃描，只需要遍歷葉子節點就可以了，不需要遍歷整棵 B+Tree 拿到所有的數據） B+Tree 的磁盤讀寫能力相對於 B Tree 來說更強（根節點和枝節點不保存數據區，所以一個節點可以保存更多的關鍵字，一次磁盤加載的關鍵字更多） 排序能力更強（因為葉子節點上有下一個數據區的指針，數據形成了鏈表） 效率更加穩定（B+Tree 永遠是在葉子節點拿到數據，所以 IO 次數是穩定的）
為什麼不用紅黑樹？
紅黑樹也是 BST 樹，但是不是嚴格平衡的。
必須滿足 5 個約束：
- 節點分為紅色或者黑色。
- 根節點必須是黑色的。
- 葉子節點都是黑色的 NULL 節點。
- 紅色節點的兩個子節點都是黑色（不允許兩個相鄰的紅色節點）。
- 從任意節點出發，到其每個葉子節點的路徑中包含相同數量的黑色節點。
插入：60、56、68、45、64、58、72、43、49
基於以上規則，可以推導出：
從根節點到葉子節點的最長路徑（紅黑相間的路徑）不大於最短路徑（全部是黑色節點）的 2 倍。
- 為什麼不用紅黑樹？
只有兩路； 不夠平衡。 紅黑樹一般只放在內存裡面用。例如 Java 的 TreeMap。
索引方式：真的是用的 B+Tree 嗎？
在 Navicat 的工具中，創建索引，索引方式有兩種，Hash 和 B Tree。
HASH：以 KV 的形式檢索數據，也就是說，它會根據索引字段生成哈希碼和指針，指針指向數據。
- 哈希索引有什麼特點呢？
它的時間複雜度是 O(1)，查詢速度比較快。因為哈希索引裡面的數據不是按順序存儲的，所以不能用於排序。 我們在查詢數據的時候要根據鍵值計算哈希碼，所以它只能支持等值查詢（= IN），不支持範圍查詢（> < >= <= between and）。 另外一個就是如果字段重複值很多的時候，會出現大量的哈希衝突（採用拉鍊法解決），效率會降低。
- 問題： InnoDB 可以在客戶端創建一個索引，使用哈希索引嗎？
我們先到官網看看介紹： dev.mysql.com/doc/refman/… InnoDB utilizes hash indexes internally for its Adaptive Hash Index feature 直接翻譯過來就是：InnoDB 內部使用哈希索引來實現自適應哈希索引特性。 這句話的意思是 InnoDB 只支持顯式創建 B+Tree 索引，對於一些熱點數據頁， InnoDB 會自動建立自適應 Hash 索引，也就是在 B+Tree 索引基礎上建立 Hash 索引，這個過程對於客戶端是不可控制的，隱式的。 我們在 Navicat 工具裡面選擇索引方法是哈希，但是它創建的還是 B+Tree 索引，這個不是我們可以手動控制的。 在 buffer pool 裡面有一塊區域是 Adaptive Hash Index 自適應哈希索引，就是指這個。
這個開關默認是 ON：
<code>show variables like 'innodb_adaptive_hash_index';複製代碼/<code>
從存儲引擎的運行信息中可以看到：
<code>show engine innodb status\\G複製代碼/<code>
<code>----------------------BUFFER POOL AND MEMORY-----------------------------------------------------------INSERT BUFFER AND ADAPTIVE HASH INDEX-------------------------------------複製代碼/<code>
因為 B Tree 和 B+Tree 的特性，它們廣泛地用在文件系統和數據庫中，例如Windows 的 HPFS 文件系統，Oracel、MySQL、SQLServer 數據庫。
B+Tree落地形式
MySQL 架構
通過上節課我們知道，MySQL 是一個支持插件式存儲引擎的數據庫。在 MySQL 裡面，每個表在創建的時候都可以指定它所使用的存儲引擎。
這裡我們主要關注一下最常用的兩個存儲引擎，MyISAM 和 InnoDB 的索引的實現。
MySQL 數據存儲文件
首先，MySQL 的數據都是文件的形式存放在磁盤中的，我們可以找到這個數據目錄的地址。在 MySQL 中有這麼一個參數，我們來看一下：
<code>show VARIABLES LIKE 'datadir';複製代碼/<code>
每個數據庫有一個目錄，我們新建了一個叫做 checkit 的數據庫，那麼這裡就有一個checkit 的文件夾。
這個數據庫裡面我們又建了 5 張表：archive、innodb、memory、myisam、csv。
我們進入 checkit 的目錄，發現這裡面有一些跟我們創建的表名對應的文件。
在這裡我們能看到，每張 InnoDB 的表有兩個文件（.frm 和.ibd），MyISAM 的表有三個文件（.frm、.MYD、.MYI）。
有一個是相同的文件，.frm。
.frm 是 MySQL 裡面表結構定義的文件，不管你建表的時候選用任何一個存儲引擎都會生成。
我們主要看一下其他兩個文件是怎麼實現 MySQL 不同的存儲引擎的索引的。
在 MyISAM 裡面，另外有兩個文件：
一個是.MYD 文件，D 代表 Data，是 MyISAM 的數據文件，存放數據記錄，比如我們的 user_myisam 表的所有的表數據。
一個是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我們在 id 字段上面創建了一個主鍵索引，那麼主鍵索引就是在這個索引文件裡面。
也就是說，在 MyISAM 裡面，索引和數據是兩個獨立的文件。
那我們怎麼根據索引找到數據呢？
MyISAM 的 B+Tree 裡面，葉子節點存儲的是數據文件對應的磁盤地址。所以從索引文件.MYI 中找到鍵值後，會到數據文件.MYD 中獲取相應的數據記錄。
這裡是主鍵索引，如果是輔助索引，有什麼不一樣呢？
在 MyISAM 裡面，輔助索引也在這個.MYI 文件裡面。
輔助索引跟主鍵索引存儲和檢索數據的方式是沒有任何區別的，一樣是在索引文件
裡面找到磁盤地址，然後到數據文件裡面獲取數據。
再看看 innodb：
InnoDB 只有一個文件（.ibd 文件），那索引放在哪裡呢？
在 InnoDB 裡面，它是以主鍵為索引來組織數據的存儲的，所以索引文件和數據文件是同一個文件，都在.ibd 文件裡面。
在 InnoDB 的主鍵索引的葉子節點上，它直接存儲了我們的數據。
作者：焯傑
鏈接：https://juejin.im/post/5e3a8c86f265da571e260a4e
來源：掘金
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。
閱讀更多 追逐仰望星空 的文章
