一、什麼是索引
在MYSQL中,索引是一種特殊的資料庫結構,由數據表中的一列或多列組合而成,可以用來快速查詢數據表中有某一特定值的記錄。通過索引,查詢數據時不用讀完記錄的所有信息,而只是查詢索引列即可，索引是幫助Mysql高效獲取數據且以排好序的數據結構，直觀的說，索引就類似書的目錄頁，沒有目錄（即索引）我們就要一頁一頁的找，有了目錄（索引）我們就可以按照目錄中標記的頁數去相應的頁數去查找。
二、為什麼要用索引
例如，我們通過查詢語句查詢一條記錄：select * from table where Col2 = 85,如果沒有索引的話，那麼它將從第一行[1,35]開始找，一行一行的找，直到找到[6,85]這條數據，並且數據存放的位置也不規則，拿取一行記錄就需要與磁碟進行一次交互，即IO讀取，如果數據多，這種效率將會很低下，只要把這種交互次數控制在一定範圍之內，那他的效率將會比一行行查找要高很多，如給col2加索引，來執行select * from table where Col2 = 85，通過二叉樹接口，第一次我們查到的是35，85比35大，所以查找右子節點，查到85，與條件種的85為一條數據，所以，這裡就只需要兩次交互就可以查到。所以索引就誕生了。
三、索引的數據結構
1、二叉樹
1.1、二叉樹的特點：
1、每個節點最多有兩個子樹，所以二叉樹不存在度大於2的節點（結點的度：結點擁有的 子樹的數目。），可以沒有子樹或者一個子樹。
2.左子樹和右子樹有順序，次序不能任意顛倒。
3、二叉樹支持動態的插⼊和查找，保證操作在O(height)時間，這就是完成了哈希表不便完成的⼯作，動態性。但是⼆叉樹有可能出現worst-case，如果
輸⼊序列已經排序，則時間複雜度為O(N)。為什麼不用二叉樹來作為索引，就是因為二叉樹的worst-case，如果輸入序列是排好序的，那麼二叉樹的結構就會變成如下圖所示的特殊狀態：
所以二叉書並不適合去做索引，遇到這種極端情況，就會導致有索引和無索引效果一樣。
2、平衡二叉樹
AVL樹是嚴格的平衡二叉樹，所有節點的左右子樹高度差不能超過1；AVL樹查找、插入和刪除在平均和最壞情況下都是O(lgn)。AVL實現平衡的關鍵在於旋轉操作：插入和刪除可能破壞二叉樹的平衡，此時需要通過一次或多次樹旋轉來重新平衡這個樹。當插入數據時，最多只需要1次旋轉(單旋轉或雙旋轉)；但是當刪除數據時，會導致樹失衡，AVL需要維護從被刪除節點到根節點這條路徑上所有節點的平衡，旋轉的量級為O(lgn)。由於旋轉的耗時，AVL樹在刪除數據時效率很低；在刪除操作較多時，維護平衡所需的代價可能高於其帶來的好處，因此AVL實際使用並不廣泛。
3、紅黑樹
與AVL樹相比，紅黑樹並不追求嚴格的平衡，而是大致的平衡：只是確保從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。從實現來看，紅黑樹最大的特點是每個節點都屬於兩種顏色(紅色或黑色)之一，且節點顏色的劃分需要滿足特定的規則。在java8中的HashMap就是使用鍊表+紅黑樹。紅黑樹的缺點就是太高了，如下圖所示：
當數據量特別大的時候，樹的高度很高，假設你要查找的節點為當前樹的葉子節點，那麼要查找這個節點，至少要循環h(這棵樹的高度)次，所以說，紅黑樹在這種情況下也並不適用。
4、B-tree
Tree就是我們常說的B樹，它是一種多路搜索樹而非二叉樹，使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度
在B樹中，每個節點包含：
1、本結點所含關鍵字的個數；
2、指向父節點的指針
3、關鍵字
4、指向子節點的指針
對於一棵m階B-tree，每個結點至多可以擁有m個子結點。各結點的關鍵字和可以擁有的子結點數都有限制，規定m階B-tree中，根結點至少有2個子結點，除非根結點為葉子節點，相應的，根結點中關鍵字的個數為1~m-1;非根結點至少有[m/2]([]，向上取整)個子結點，相應的，關鍵字個數為[m/2]-1~m-1。
B-tree有以下特性:
1、關鍵字集合分布在整棵樹中;
2、任何一個關鍵字出現且只出現在一個結點中; 所有索引元素不重複
3、搜索有可能在非葉子結點結束;
4、其搜索性能等價於在關鍵字全集內做一次二分查找;
5、自動層次控制;
6、所有葉節點都在同一層，每個節點最多有m-1個key，並且以升序排列
葉節點具有相同的深度，葉節點的指針為空
由於限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少利用率，其最低搜索性能為:
其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數;
所以B-樹的性能總是等價於二分查找(與M值無關)，也就沒有B樹平衡的問題;
由於M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占M/2的結點;刪除結點時，需將兩個不足M/2的兄弟結點合併。
B樹的查詢：
B樹是二叉排序樹的擴展，二叉排序樹是二路查找，B-樹是多路查找。因為B-樹節點內的關鍵字是有序的，在節點內查找的時候除了順序查找之外，還可以用折半查找提高效率，B-樹的具體查找步驟可以參照折半查找方法。
以查找42為例：
首先獲取關鍵點的關鍵字進行比較，當前根節點關鍵字為30，42>30，所以找右子節點，拿到關鍵字39，45，39<42<45，所以直接找到39和45的中間的節點，拿到40,42,44,因為42=42，所以直接返回關鍵字和指針信息（如果樹結構中沒有包含所要查找的節點則返回null）
5、B+Tree（B-Tree變種）
B+樹是一種樹數據結構，通常用於資料庫和作業系統的文件系統中。B+樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+樹元素自底向上插入，這與二叉樹恰好相反。
B+樹的
非葉子節點不存儲data，只存儲索引（冗餘），可以放更多的索引，只有葉子節點才存儲數據
葉子節點包含所有索引欄位
葉子節點增加了一個指向相鄰子節點的指針，它的最後一個數據會指向下一個葉子節點的第一個數據，形成一個有序鍊表的結構，提高區間訪問的性能。
與B樹相比它的不同體現在：
(1).如果非葉子節點包含n個關鍵碼，則這個節點有n個子樹。
(2).非葉子節點僅包含關鍵碼信息，葉子節點包含關鍵碼以及含有這個關鍵碼的記錄的指針。所以查找時，B+樹必須到達葉子節點才會命中。
(3).葉子節點包含有兄弟葉子節點的指針，而且葉子節點的關鍵碼值是有序的，有利於遍歷。
(4).所有的非葉子節點可看成是索引部分(稀疏索引)
為什麼說B+樹比B樹更適合實際應用中作為作業系統的文件索引和資料庫索引
(1)B+樹的磁碟讀寫代價更低
非葉子節點包含的信息更少，如果把同一節點的所有信息放在一個磁碟塊中，則可以比B樹放入更多的關鍵碼。一次讀入內存當中(讀一個塊)就能讀入更多的關鍵碼，所以降低了磁碟I/O總數。
(2)查詢效率更加穩定
對任何關鍵字的查找都必須從根節點走到葉子節點，路徑長度相同，所以對每條數據的查詢效率相當，在存儲相等的關鍵字上，B+樹樹的高度會更低。
(3)B樹在提高磁碟I/O性能的同時並沒有解決元素遍歷效率低下的問題。而B+樹因為葉子節點有鏈指針存在，所以遍歷葉子節點即可以實現對整棵樹的遍歷。而在資料庫中基於範圍的查詢是非常頻繁的，B+樹就能更好的支持。
四、存儲引擎索引實現
數據存儲引擎是形容資料庫表層面的，而不是形容資料庫的，我們點擊表設計，在選項中證實這一問題。
1、MYISAM存儲引擎索引實現
MYISAM基於ISAM存儲引擎，並對其進行擴展。它是在web、數據倉儲和其他應用環境下最常用的存儲引擎之一。MYISAM擁有較高的插入、查詢速度，但不支持事務和外鍵。所以對事務完整性沒有要求或者以SELECT、INSERT為主的應用基本上都可以使用這個引擎來創建表。 數據文件和索引文件可以放置在不同的目錄，平均分布 IO，獲得更快的速度。要指定索引文件和數據文件的路徑，需要在創建表的時候通過 DATA DIRECTORY 和 INDEX DIRECTORY 語句指定，也就是說不同 MyISAM 表的索引文件和數據文件可以放置到不同的路徑下。文件路徑需要是絕對路徑，並且具有訪問權限。
MYISAM存儲引擎的索引
1)MyISAM默認使用B+Tree索引，只把索引載入內存，存儲的是數據的索引
2)MyISAM資料庫中的數據是按照插入的順序保存，在每個索引節點中保存對應的數據行的地址，理論上說主鍵索引和其他索引是一樣的。
3)MYISAM的索引文件和數據文件是分離的(非聚集)
MYD文件存的是表的數據
MYI文件存的是表的索引
frm文件存的是表的結構
2、InnoDB存儲索引實現
InnoDB存儲引擎提供了具有提交、回滾和崩潰恢復能力的事務安全。但是對比MYISAM的存儲引擎，InnoDB寫的處理效率差一些並且會占用更多的磁碟空間以保留數據和索引。但是由於其其他方面的優勢，在5.5版本之後，MYSQL的默認引擎變成了InnoDB.
2.1InnoDB索引實現(聚集)
InnoDB表只有一個聚集索引
表數據文件本身就是按B+Tree組織的一個索引結構文件，聚集索引-葉子節點包含了完整的數據記錄
InnoDB存儲引擎存儲資料庫數據，一共有兩個文件
frm文件：表的結構
ibd文件: 數據和索引存儲文件。數據以主鍵進行聚集存儲，把真正的數據保存到葉子節點中
接下來我們能也從幾個問題當中去了解InnoDB索引引擎
1、為什麼建議InnoDB表最好建主鍵？
因為在InnoDB中，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄。這個索引的Key是資料庫的主鍵，因此InnoDB表數據文件本身就是主索引。綜上所述，InnoDB數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵(MYISAM可以沒有，因為數據和索引是分開的)，如果沒有指定，那麼Mysql系統會自動選擇一個所有元素均不相等的列作為主鍵，如果不存在這種列，則Mysql自動為InnoDB表生成一個隱含欄位作為主鍵，這個欄位長度未6個字節，類型為長整型。
2、為什麼推薦使用整型的自增主鍵？
因為B+Tree再找數據的時候會去比較大小，整型數值比大小要相對簡單和快速，且索引節點占的內存會更小。再有就是主鍵id是非自增的，這個時候就會導致頁分裂,也會導致B+樹節點分裂。
什麼是頁分裂：
首先來一張數據頁的圖
上面就是數據也的結構了，兩個數據頁之間會有指針指向上一個和下一個數據頁，形成一個雙向鍊表，（也就是InnoDB中B+Tree的葉子節點）在數據頁中存儲的就是一行行數據了，每個數據行之間會有單向指針連接，組成一個單向鍊表，假設你不停的往表里插數據，那麼剛開始就會在一個數據頁裡面插入數據，比如說我們在左側的數據頁中插入數據，先插入主鍵id為1，3，5的數據，數據越來越多，我們就要搞另外一個數據頁，這個數據頁裡面我們就插入了主鍵id為2，4，6的數據，關鍵點來了，當我們使用索引的時候，最基本的條件就是後面數據頁中的數據行主鍵值要都大於前一個數據頁中數據行的主鍵值，所以，當我們發現後一個主鍵id要小於前一頁的主鍵id值，我們就要進行數據挪動，從而滿足索引的基本要求，這個過程就是頁分裂如下圖所示：
1）為了索引更快找到數據所以進行頁分裂有以下幾個作用：
讀操作：對索引來說，其實就是通過平衡二叉樹不斷減少要篩選的數據，而主鍵值就是篩選的標準，以儘快定位到我們需要的數據。
寫操作：在平衡二叉樹中，假設插入的數據的主鍵是自增長的，那麼根據二叉樹算法會很快的把該數據添加到某個節點下，而其他節點不用動；但是如果插入的是不規則的數據，那麼每次插入都會改變二叉樹之前的數據狀態。從而導致了頁分裂。直白一點來講就是為了更快的找到需要的數據。
那麼從B+樹的角度來看也可以看出，當插入非自增的數據時，B+樹也會進行分裂，詳情如下個動圖所示：
3、為什麼非主鍵索引結構葉子節點存儲的是主鍵值？
我們用col3這個列建索引，注意：InnoDB表只有一個聚集索引
為了節省存儲空間，為了保證數據的一致性，減少他的複雜度，減少了出現行移動或者數據頁分裂時二級索引的維護工作（當數據需要更新的時候，二級索引不需要修改，只需要修改聚簇索引，一個表只能有一個聚簇索引，其他的都是二級索引，這樣只需要修改聚簇索引就可以了，不需要重新構建二級索引）否則，你就需要在每個索引文件中進行數據更新。
五、聯合索引的底層存儲結構
然後我們建立聯合索引
alter table user add index idx_name_age (name,age)索引是幫助MySQL高效獲取數據的排好序的數據結構，聯合索引想當然的就是已經排好序的B+樹結構，我們這裡使用了一個三個欄位的聯合索引，那麼他是如何存儲的呢？帶著這個問題我們一起取了解一下聯合索引的存儲結構。
1、索引最左前綴原理
通常我們在建立聯合索引的時候，也就是多個欄位建立索引，mysql都會讓我們選擇索引的順序，比如我們想在a,b,c三個欄位建立一個聯合索引，我們可以選擇自己想要的優先級，a、b、c,或者是b、a、c 或者是c、a、b等順序。為什麼資料庫會讓我們選擇欄位的順序呢？不都是三個欄位的聯合索引麼？這裡就引出了資料庫索引的最左前綴原理。
mysql建立多列索引（聯合索引）有最左前綴的原則，即最左優先，如：
如果有一個2列的索引(col1,col2),則已經對(col1)、(col1,col2)上建立了索引，當然在紅黑樹中，也是排好序來維護此索引；
如果有一個3列索引(col1,col2,col3)，則已經對(col1)、(col1,col2)、(col1,col2,col3)上建立了索引；
select * from table where c = '1'這個sql語句是不會走index1索引的，
select * from table where b =『1』 and c ='2'這個語句也不會走index1索引。
比如：索引index1:(a,b,c)有三個欄位，我們在使用sql語句來查詢的時候，會發現很多情況下不按照我們想像的來走索引。
什麼語句會走index1索引呢？
答案是：
select * from table where a = '1'
select * from table where a = '1' and b = 『2』
select * from table where a = '1' and b = 『2』 and c='3'我們可以發現一個共同點，就是所有走索引index1的sql語句的查詢條件裡面都帶有a欄位，那麼問題來了，index1的索引的最左邊的列欄位是a，是不是查詢條件中包含a就會走索引呢？
select * from table where a = '1' and c= 『2』這個sql語句呢？
這也是最左前綴原理的一部分，索引index1:(a,b,c)，只會走a、a,b、a,b,c 三種類型的查詢，其實這裡說的有一點問題，a,c也走，但是只走a欄位索引，不會走c欄位。我們可以發現一個共同點，就是所有走索引index1的sql語句的查詢條件裡面都帶有a欄位，那麼問題來了，index1的索引的最左邊的列欄位是a，是不是查詢條件中包含a就會走索引呢？
那麼這是為什麼呢？
如上圖所示，我們給(name,age,id)三列建聯合索引，你們可以發現，在name相等的情況下（籃框部分），age欄位（紅框部分）的數據是有序的，但是放在整張表中看去，age欄位(紅框部分)的數據是亂序，何為索引？索引是幫助MySQL高效獲取數據的排好序的數據結構，而age欄位放在整張表中已經是亂序，已經不符合索引的原理，例如我想找到age為12的數據，如果是排好序的，我就在找到他以後就不需要再繼續往下找了，因為後面的都是比我大的，但是在亂序的情況下，我就需要全表掃描進行尋找，有索引和無索引效果一樣的，所以
select * from table where a = '1'
select * from table where a = '1' and b = 『2』
select * from table where a = '1' and b = 『2』 and c='3'只有上述三句會走聯合索引，三個欄位以此類推...
附：
1、回表：
通過非主鍵索引查詢數據時，會先查找到主鍵索引，然後再到主鍵索引上去查找對應的數據，這個過程叫做回表
2、聯合索引和覆蓋索引
聯合索引：指索引中包含多個列
覆蓋索引：指的是從索引中可以得到所有想要查詢的列
比如
select id，age from user where name = 『a』 and age = 12聯合索引是說的是where後面的部分，即查詢條件；覆蓋索引是說的select後面的部分，即查詢列。
假設我們有id(主鍵)，age，adderss,name這四個欄位，且age，name兩列為聯合索引的兩個列
select id，age from user where name = 『a』 and age = 12。這是覆蓋索引，因為不會回表查詢。
因為聯合索引的葉子節點就包括聯合索引中包含的列（age，name）還有主鍵(id)，所以不需要回表。
select id，address from user where name = 『a』 and age = 12這不是覆蓋索引，因為會回表查詢。address並不存在於聯合索引的葉子節點之中，所以需要根據主鍵值進行回表查詢