淺入淺出 MySQL 索引
索引是什么?為什么要有mysql 索引，解決了什么問題，其底層的原理是什么?為什么使用B+樹做為解決方案?用其他的像哈希索引或者B樹不行嗎?
簡單了解索引
首先，索引(Index)是什么?如果我直接告訴你索引是數據庫管理系統中的一個有序的數據結構，你可能會有點懵逼。
為了避免這種情況，我打算舉幾個例子來幫助你更容易的認識索引。
- 我們查詢字典的時候可以根據字的部首、筆畫來查找到對應的字，這樣可以快速的找到對應的字所在頁，在字典開頭那玩意就叫索引
- 還有一本書的目錄，可以幫我們快速的跳到不同的章節，此時這里的目錄也是索引
- 甚至，景區的地圖，會告訴你你現在在哪里，其他景點在哪兒，這個地圖從某些方面來說也是索引
再結合開篇較專業的解釋，你可能就能夠理解索引是什么了。
為什么需要索引
了解了索引的概念，我們就需要知道為什么我們需要索引?從剛剛的例子可以看出來，索引的存在的目的就是：
- 字典中的索引幫助我們快速的找到對應的字
- 書的目錄幫助我們快速的跳到我們需要看的章節
- 景區的地圖幫助我們快速的找到想要去的景區的路
在數據庫中，索引可以幫助我們快速的查詢到對應的數據行，從而順利的取出所有列的數據。這個過程必須要快，對于現在的 Web 應用來說，DB 如果響應慢，將會直接影響到整個請求的響應時間，而這對用戶體驗來說是災難性的。
對于點個按鈕，等個好幾秒才有返回，那么之后用戶大概率是不會再使用你開發的應用了。
MySQL中的索引
首先，MySQL 和索引其實沒有直接的關系。索引其實是 MySQL 中使用的存儲引擎 InnoDB 中的概念。在 InnoDB 中，索引分為：
- 聚簇索引
- 非聚簇索引
對于聚簇索引，是 InnoDB 根據主鍵(Primary Key)構建的索引。你可以暫時理解為 key 為主鍵，value 則是整行數據。并且一張表只能有一個聚簇索引。
當然，你可以不定義主鍵。但是正常情況下我們都會創建一個單調遞增的主鍵，或者是通過統一的 ID 生成算法生成。如果沒有定義任何主鍵，InnoDB 會有自己的兜底策略。InnoDB 會選擇我們定義的第一個所有值的都不為空的唯一索引作為聚簇索引。
不過實際的生產環境中，的確會有這樣的 Corner Case。InnoDB 還有一個究極兜底，如果連僅剩的唯一索引也不符合要求，InnoDB 會自己創建一個隱藏的6個字節的主鍵 RowID，然后根據這個隱藏的主鍵來生成聚簇索引。
而對于非聚簇索引，是根據指定的列創建的索引，也叫二級索引(Secondary Index)，一張表最多可以創建64個二級索引。key 為創建二級索引的列的值，value 為主鍵。換句話說，如果通過非聚簇索引查詢，最終只能得到索引列本身的值 + 主鍵的值，如果想要獲取到完整的列數據，還需要根據得到的主鍵去聚簇索引中再查詢一次，這個過程叫回表。
- 這里說明一下，現在有很多的博客說，MySQL 使用 InnoDB 時，一張表最多只能創建 16 個索引，首先這是錯的，明顯是從其他的地方直接抄過來的，自己沒有去做任何的驗證。
- 在 MySQL 的官方文章中，明確的說明了，一張表最多可以創建 64 個非聚簇索引，而且創建非聚簇索引時，列的數量不能超過16個。
注意，是創建非聚簇索引的列不能超過16個!
這也順便提一下題外話，所謂的技術嚴謹，什么叫嚴謹?對你通過其他渠道獲取到的知識，它最多叫作者的觀點，我們持一種懷疑態度，并想辦法自己去求證。求證后，它才會變成事實。
而不是對某些名詞死記硬背，現在的新玩意層出不窮，但當你溯其根源，你會發現就那么回事。
索引底層原理
前面提到了 InnoDB 中索引的類型，簡單的了解了其分類和區別，那 InnoDB 中的索引是如何做到加速查詢的呢?其底層的原理是啥呢?InnoDB 中的索引的底層結構為 B+ 樹，是B樹的一個變種。
先給大家看看B+樹到底長個什么鳥樣，下圖是一顆存儲了數字「1-7」的B+樹。
可以看到，B+樹中，每個節點可以有多個子節點，而像我們平常熟悉的二叉樹中，每個節點最多只能有2個。并且，B+樹中，節點的存儲數據是有序的，而有序的數據結構就可以讓我們進行快速的精確匹配和范圍查詢。而且B+樹中的葉子結點之間有指向下一個節點的指針，而B樹中的葉子節點是沒有的。
- 在 MySQL InnoDB 的實際實現中，頁節點之間其實是個雙鏈表，存儲了分別指向上一個、下一個節點的指針
下圖是包含了整數「1-7」的B樹，這個圖應該會幫助你加深對兩者區別的理解。
并且，在B+樹中，除了葉子節點存儲了真實的數據之外，其余的節點都只存儲了指向下一節點的指針。換句話說，數據全部都在葉子節點上。而在B樹中，所有的節點都可以存儲數據，這是一個最主要的區別。
知道了B樹和B+樹的基礎結構長啥樣之后，我們需要再深入了解 InnoDB 是如何利用B+樹來存儲數據的。首先，MySQL 并不會把數據存儲在內存中，內存只是作為運行時的一種優化，關于 InnoDB 內存架構相關的東西，之前已經寫了一篇文章，感興趣的可以先去看看。
InnoDB 會將數據存儲在磁盤上，而當我們查詢數據的時候，OS 會將存儲在磁盤上的數據一頁一頁的加載到內存里。這里的頁是 OS 管理內存的一種方式，當其加載數據到內存時，會將某個磁盤塊上的數據按照頁的大小加載。在這里，你可以理解為B樹中每個節點就是一個磁盤塊。
那既然B樹和B+樹在查找的時候都需要進行 I/O 操作將需要的節點加載到內存，B+樹相對于B樹的優勢到底在哪兒?
個人認為主要有三點。
一是B+樹能夠減少 I/O 的次數。為啥呢?憑啥數據結構長的差不多，B+樹就能夠減少 I/O 的次數?之前說到，單個節點就代表了一個磁盤塊，而單個磁盤塊的大小是固定的。B+樹僅有葉子結點才存儲值，相對于所有節點都存完整數據的B樹而言，B+樹中單個磁盤塊能夠容納更多的數據。
單個磁盤塊，容量固定的前提下，存儲的元素大小越小，則能夠存儲的元素的數量就會更多。換句話說，一次 I/O 能夠把更多的數據加載進內存，而這些多加載的元素很可能是你會用到的，而這就一定程度上能減少 I/O 的次數。
除此之外，單個節點能夠存儲的元素增多了，還能夠起到減少樹的高度的作用。
二是查詢效率更加穩定。什么叫更穩定呢?那就在數據量相同的情況下，不會因為你查詢的數據 ID 不同而造成查詢所耗費時間大相徑庭，換句話說，這次請求可能花了10ms，下一次同樣的請求啪的一下花了20ms，這就讓人很不能接受，合著接口的性能還要看你數據庫的心情?
那為什么說使用B+樹就能夠做到查詢效率穩定呢?因為B+樹非葉子結點不會存儲數據，所以如果要獲取到最終的數據，必然會查到葉子結點，換句話說，每次查詢的 I/O 次數是相同的。而B樹由于所有節點均可存儲數據，有的數據可能1次 I/O 就查詢到了，而有的則需要查詢到葉子結點才找到數據，而這就會帶來查詢效率的不穩定。
三是能夠更好的支持范圍查詢。那B樹為啥就不能很好的支持呢?讓我們回到B樹這張圖。
假設我們需要查詢 [3, 5] 這個區間內的數據，會經歷什么呢?不廢話，直接把圖給出來。
可以看到，如果到葉子結點仍然沒有查詢到完整的數據，會重新返回到根結點再次進行遍歷。而反觀 B+ 樹，當找到了葉子結點之后就可以通過葉子結點之間的指針直接進行鏈表遍歷，可以大大的提升范圍查詢的效率。
- 知道了這點之后，舉一反三就能夠知道，為什么 InnoDB 不使用 Hash 在做底層的數據結構了。即使查詢時 Hash 的時間復雜度甚至能做到 O(1)
最后聊聊 I/O
全篇提到了很多次 I/O，以及在 MySQL 的索引設計中，需要盡量的減少 I/O 次數，為啥呢?是因為 I/O 很昂貴。當我們執行一次 I/O，到底發生了什么?
本來像詳細講講磁盤結構的，但是看了一眼篇幅，已經快超了，所以這里就簡單的聊聊就好
機械硬盤中，一次 I/O 操作，由三個步驟組成：
首先需要尋道，尋道是指磁盤的磁頭移動道磁盤上的磁道上面，這個時間一般在3-15ms內。
然后是旋轉，磁盤會將存儲對應數據的盤片旋轉至磁頭下方，這又花掉2ms左右，具體的時延與磁盤的轉速有關。
最后是數據傳輸。
一波操作下來，花費就在10ms左右。不要以為10ms還好...對比于SSD(固態硬盤)和內存的微秒、納秒來說，簡直有著天壤之別。
這也是為啥在 MySQL 中，隨機 I/O 對其查詢的性能影響很大的原因。
