一起聊聊覆寫索引，輔助索引，唯一索引，Hash索引，B-Tree索引......”到底是些什麼東西？？？？
關于MySQL索引相關的内容，一直是一個讓人頭疼的問題，尤其是對于初學者來說。筆者曾在很長一段時間内深陷其中，無法厘清“覆寫索引，輔助索引，唯一索引，Hash索引，B-Tree索引……”到底是些什麼東西，導緻在面試過程中進入比較尴尬的局面。
很多人可能會抱怨”面試造火箭，工作擰螺絲，很多知識都是為了面試學的，工作中根本用不到！“。慶幸的是，MySQL中索引不僅是面試必考知識，還是工作中用到最為頻繁的必備技能，在筆者看來，索引是MySQL中成本效益最高的一部分内容。
由于MySQL中支援多種存儲引擎，在不同的存儲引擎中實作略微有所差距，索引下文中如果沒有特殊聲明，預設指的都是InnoDB存儲引擎。
一、底層資料結構
首先，索引是高效擷取資料的資料結構。就像書中的目錄一樣，我們可以通過它快速定位到資料所在的位置，進而提高資料查詢的效率。
在MySQL中有許多關于索引的名詞和概念，對于初學者來說很容易被迷惑。為了友善了解，我建立了一張表，從具體的案例中嘗試說清楚這些概念到底是什麼。
Hash索引
正如上文中說到，索引是提高查詢效率的資料結構，而能夠提高查詢效率的資料結構有很多，如二叉搜尋樹，紅黑樹，跳表，哈希表（散清單）等，而MySQL中用到了B+Tree和散清單（Hash表）作為索引的底層資料結構。
需要注意的是，MySQL并沒有顯式支援Hash索引，而是作為内部的一種優化，對于熱點的資料會自動生成Hash索引，也叫自适應Hash索引。
Hash索引在等值查詢中，可以O（1）時間複雜度定位到資料，效率非常高，但是不支援範圍查詢。在許多程式設計語言以及資料庫中都會用到這個資料結構，如Redis支援的Hash資料結構。具體結構如下：
B+Tree索引
提到B+Tree首先不得不提B-Tree，B-Tree（多路搜尋樹，并不是二叉的）是一種常見的資料結構。使用B-tree結構可以顯著減少定位記錄時所經曆的中間過程，進而加快存取速度。
B+ 樹是基于B-Tree更新後的一種樹資料結構，通常用于資料庫和作業系統的檔案系統中。B+ 樹的特點是能夠保持資料穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+ 樹元素自底向上插入，這與二叉樹恰好相反。
MySQL索引的實作也是基于這種高效的資料結構。具體資料結構如下：
筆者首先要聲明一下，不要将B樹，B-Tree以及B+Tree弄混淆。首先，B-Tree就是B樹，中間的“-”是一個中劃線，而不是減号，并不存在"B減樹"這種資料結構。其次，就是B+Tree和B-Tree實作索引時有兩個差別，具體可見下圖
①B+Tree隻在葉子節點存儲資料，而B-Tree的資料存儲在各個節點中
②B+Tree的葉子節點間通過指針連結，可以通過周遊葉子節點即可擷取所有資料。
B+Tree是一種神奇的資料結構，如果用語言來講可能會有點費勁，感興趣的同學可以點選文末資料結構可視化工具，操作一番後想必會有所收獲，下圖是筆者示範B+Tree的資料插入方式（自下而上）。
二，資料組織方式
根據資料的組織方式，可以分為聚簇索引和非聚簇索引（也叫聚集索引和非聚集索引）。聚簇索引就是按照每張表的主鍵構造一棵B+Tree，同時葉子節點存放了整張表的行記錄資料。
在InnoDB中聚簇索引和主鍵索引概念等價，MySQL中規定是以每張表都必須有主鍵索引，主鍵索引隻能有一個，不能為null同時必須保證唯一性。建表時如果沒有指定主鍵索引，則會自動生成一個隐藏的字段作為主鍵索引。
與之對應的則是非聚集索引，非聚集索引又可以稱之為為非主鍵索引，輔助索引，二級索引。主鍵索引的葉子節點存儲了完整的資料行，而非主鍵索引的葉子節點存儲的則是主鍵索引值，通過非主鍵索引查詢資料時，會先查找到主鍵索引，然後再到主鍵索引上去查找對應的資料，這個過程叫做回表（下文中會再次提到）。
需要補充的是MyISAM中索引和資料檔案分開存儲，所有的索引都是非聚簇索引。B+Tree的葉子節點存儲的是資料存放的位址，而不是具體的資料 。
三，包含字段個數
為了能應對不同的資料檢索需求，索引即可以僅包含一個字段，也可以同時包含多個字段。單個字段組成的索引可以稱為單值索引，否則稱之為複合索引（或者稱為組合索引或多值索引）。上文中示範的都是單值索引，是以接下來展示一下複合索引作為對比。
複合索引的索引的資料順序跟字段的順序相關，包含多個值的索引中，如果目前面字段的值重複時，将會按照其後面的值進行排序。
四，其他分類
唯一索引
唯一索引，不允許具有索引值相同的行，進而禁止重複的索引或鍵值。系統在建立該索引時檢查是否有重複的鍵值，并在每次使用 INSERT 或 UPDATE 語句添加資料時進行檢查， 如果有重複的值，則會操作失敗，抛出異常。
需要注意的是，主鍵索引一定是唯一索引，而唯一索引不一定是主鍵索引。唯一索引可以了解為僅僅是将索引設定一個唯一性的屬性。
覆寫索引
上文提到了一個回表的概念，既如果通過非主鍵索引查詢資料時，會先查詢到主鍵索引的值，然後再去主鍵索引中查詢具體的資料，整個查詢流程需要掃描兩次索引，顯然回表是一個耗時的操作。
為了減少回表次數，在設計索引時我們可以讓索引中包含要查詢的結果，在輔助索引中檢索到資料後直接傳回，而不需要進行回表操作。
但是需要注意的是，使用覆寫索引的前提是字段長度比較短，對于值長度較長的字段則不适合使用覆寫索引，原因有很多，比如索引一般存儲在記憶體中，如果占用空間較大，則可能會從磁盤中加載，影響性能。當然還有其他原因，具體情況将會在下一篇文章中介紹。
六，總結
本文從不同次元介紹了MySQL中的索引，索引從不同次元劃分可以有很多種名稱，但是需要明确一個問題就是，索引的本質是一種資料結構，其他索引的劃分則是針對實際應用而言。具體分類如下圖所示：
目的是讓大家對于索引有個初步且清晰的認識，解決What的問題。後續将會針對Why以及How，進行深入探讨，當然，首先應當能區分本章文章中講述的概念性問題。
資料結構可視化工具： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
七、Q&A
1. 為什麼MySQL索引使用B+Tree實作，而不是搜尋二叉樹，紅黑樹或者跳表？
這是一個綜合性問題，遠不止看起來那麼簡單，小夥伴們可以把答案寫在留言區我們一起探讨，同樣筆者将會在下一篇文章中重點介紹為什麼，以及如何正确使用索引。