一文搞懂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并不存在于聯合索引的葉子節點之中，所以需要根據主鍵值進行回表查詢

標籤：Java

上一篇：Java陣列演算法(二分、冒泡、選擇、快排)

下一篇：MyBatis（二）：我的第一個MyBatis程式