一文搞懂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+樹也會進行分裂，詳情如下個動圖所示：

我們用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並不存在於聯合索引的葉子節點之中，所以需要根據主鍵值進行回表查詢