Categories
程式開發

Mysql學習筆記:InnoDB索引結構淺析


索引是檢索圖書資料的一種工具,把書刊中的內容或項目分類摘錄,註明頁數,按一定次序排列。

針對不同的數據存儲結構有不同的數據查找方式。

1. 數據結構

1.1 B樹

B樹又名平衡多路查找樹,主要用於文件系統中,在B樹中,每個結點的大小為一個磁盤頁,結點中所包含的關鍵字及其孩子的數目取決於頁的大小。

Mysql學習筆記:InnoDB索引結構淺析 1

對於一顆度為m的B樹,需要滿足:

根結點或葉子結點,至少有2顆子樹,至多有m顆。 非葉子結點至少有m/2顆子樹,至多有m顆。 所有葉子結點都在同一層。 每個結點都要包含(n,Ao,K1,A1,K2,A2,K3,A3,Kn,An)n是結點中關鍵字的個數,且(m/2)-1 ≤ n ≤ m-1,n+1為子樹的棵數Ai(i=0,1,…,n)為指向孩子結點的指針,且Ai-1所指向的子樹中所有結點的關鍵字都小於Ki ,Ai所指向的子樹中所有結點的關鍵字都大於KiKi(1≤i≤n)是關鍵字,且Ki

B樹使用二分查找,包含兩個基本操作:

在B樹上查找結點:遍歷整個樹。 在結點中查找關鍵字:每個結點中包含m個關鍵字,通過二分查找查詢目標關鍵字。

B樹上關鍵字的增加和刪除通過平衡算法達到平衡。

1.2 B+樹

B+樹是B樹的變體,在實際的文件系統中基本上不使用B樹。 B+樹和B樹的差異點:

若一個結點有n棵子樹,則必含有n個關鍵字;所有葉子結點中包含了全部記錄的關鍵字信息以及這些關鍵字記錄的指針,而且葉子結點按關鍵字的大小從小到大順序鏈接;所有的非葉子結點可以看成是索引的部分,結點中只含有其子樹的根結點中的最大(或最小)關鍵字。

Mysql學習筆記:InnoDB索引結構淺析 2

B+樹的非葉子結點不保存數據記錄的指針信息,這意味著深度相同時B+樹比B樹的關鍵字更多。

2.InnoDB索引類型

2.1 B+樹索引

InnoDB中的主鍵索引和輔助索引都是採用B+樹。

Mysql學習筆記:InnoDB索引結構淺析 3

B樹的每個結點大小和磁盤頁一致,磁盤每個頁有4k,根據這個我們就可以計算出索引的深度。 假設是一顆完全的m階B+樹,m的大小取決於非葉子結點存儲關鍵字的數量,主鍵一般都是BIGINT 佔8個字節,那麼m=4*1024/8=512。

Mysql學習筆記:InnoDB索引結構淺析 4

輔助索引的關鍵字按索引創建時定義列的順序來的,如:status + create_time,10 2020-8-1

Mysql學習筆記:InnoDB索引結構淺析 5

B+樹結點中的關鍵字都是按順序組織的,所以關鍵字的長度和類型決定了索引的性能:

關鍵字越短,B+樹的結點就越多,樹的深度也會在預期內。 關鍵字值分佈的越均勻(重複少),B+樹就越平衡。 數字比字符串要快,因為字符串需要先做轉換再做排序:字符串排序算法。

在某些特殊場景關鍵字的值不需要均勻,如:status字段有1、2這兩個值,1 -> 100條數據,2 -> 100萬條數據,業務上只需要查詢status為1的記錄就會非常快,否則需要掃全表。

了解InnoDB索引的查找方法有助於我們創建高效的索引:

全值匹配:比較完整的關鍵字。 匹配最左前綴:只和索引定義的第一列進行匹配。 匹配列前綴:只匹配第一列並且匹配關鍵字的前綴而非全值匹配。 匹配範圍值:匹配兩個關鍵字之間的值。 (在B樹中關鍵字是順序組織的,只要查詢到當前關鍵字的父結點就能直接確認範圍)只訪問索引:不會查詢數據行,像count這種操作就不需要再去查具體的行。

2.2 哈希索引

InnoDB中的哈希函數使用除留餘數法,衝突採用鏈地址法。

2.3 自適應哈希索引

哈希是一種非常快的查找方法,時間複雜度為O(1),即只需要查詢一次就能定位數據,而B+樹的查找次數取決於樹的高度。 InnoDB存儲引擎會監控對錶上各索引頁的查詢。 如果觀察到建立哈希索引可以帶來速度提升,則建立哈希索引,稱之為自適應哈希索引(Adaptive Hash Index,AHI)。 AHI是通過緩衝池的B+樹頁構造而來,因此建立的速度很快,而且不需要對整張表構建哈希索引。 InnoDB存儲引擎會自動根據訪問的頻率和模式來自動地為某些熱點頁建立哈希索引。

AHI有一個要求,即對這個頁的連續訪問模式必須是一樣的。 例如對於(a,b)這樣的聯合索引頁,其訪問模式可以是以下情況。

模式:

在哪裡a = xxx在哪裡a = xxx和b = xxx

條件:

以該模式訪問了100次頁通過該模式訪問了N次,其中N=頁中記錄*1/16

自適應hash索引是mysql的功能,開發者並不能控制,儘管如此還是要盡可能的利用,如果性能無法滿足再選擇緩存中間件。

參考:

Mysql官方文檔“《Mysql及時內幕InnoDB存儲引擎》https://blog.csdn.net/voidccc/article/details/40077329“傑里米·科爾 InnoDB索引頁的物理結構“傑里米·科爾 InnoDB中的B + Tree索引結構“傑里米·科爾 InnoDB中記錄的物理結構