閱讀201 返回首頁    go 阿裏雲 go 技術社區[雲棲]


MySQL索引設計背後的數據結構及算法詳解

一、B-Tree基礎知識

 

B-Tree(多路搜索樹)是一種常見的數據結構。使用B-Tree結構可以顯著減少定位記錄時所經曆的中間過程,從而加快存取速度。B通常認為是Balance的簡稱。這個數據結構一般用於數據庫的索引,綜合效率較高。目前很多數據庫產品的索引都是基於B+Tree結構。MySQL也采用B+Tree,是B-Tree的一個變種,其實特性相差不大,理解了B-Tree也就懂了B+Tree。

 

1、一顆M階B-Tree具有的特性【熟記於心】

 

1) 根結點的孩子數>=2(前提是樹高度大於1)

2) 除根結點與葉子結點,其它結點的孩子數為[ceil(m/2),m]個。ceil函數表示上取整數。

3) 所有葉子結點都出現在同一層,葉子結點不存儲數據。

4) 各個結點包含n個關鍵字信息:(P0,K1,P1,K2,P2......Kn,Pn)

  • Ki(i=1,2......n)為關鍵字,且K(i-1)<Ki,即從小到大排序

  • 關鍵字的個數n必須滿足:[ceil(m/2)-1,m-1]

  • 4.3) Pi指向子樹,且指針P(i-1)所指向的子樹結點中所有關鍵字均小於Ki。即:父結點中任何關鍵字的左孩子都小於它,右孩子大於它。

 

2、B-Tree插入操作

 

1)插入新元素,如果葉子結點空間足夠,則插入其中,遵循從小到大排序;

2)如果該結點空間滿了,進行分裂。將該結點中一半關鍵字分裂到新結點中,中間關鍵字上移到父結點中。

 

【舉例】如果單從上麵特性及插入規則看得不明白,請結合以下分步驟圖例:

 

將下麵數字插入到一棵5階B-Tree中:[3,14,7,1,8,5,11,17,13,6,23,12,20,26,4,16,18,24,25,19]

 

首先根據B-Tree特性知道,每個結點的關鍵字數量範圍是:   2<=n<=4

 

【第一步】:插入3,14,7,1

 

20170511095654473.jpg

 

到這裏,第一個結點中關鍵字數量剛好滿了。

 

【第二步】:插入8

 

20170511095701822.jpg

 

由於8是大於7的,故應該插入右子樹,一個結點中最多存儲4個關鍵字,按照插入規則,將中間關鍵字7上移形成父結點,其他按照50%分裂成兩個結點,如上圖。

 

【第三步】:插入5,11,17

 

20170511095707382.jpg

 

由於5小於7,插入左子樹,11,17大於7,插入右子樹。葉子結點沒有滿4個關鍵字,故可以直接插入5,11,17。

 

【第四步】:插入13

 

20170511095715368.jpg

 

13大於7,應該插入右子樹結點中,由於該結點中滿4個關鍵字了,需要進行分裂。13剛好是中間關鍵字,上移到父結點中;其他按照50%分裂成兩個結點。

 

【第五步】:插入6,23,12,20

 

20170511095722680.jpg

 

以上幾個數字按照規則直接插入即可,無需分裂操作。

 

【第六步】:插入26

 

20170511095729484.jpg

 

由於26大於13,應該插入13的右子樹結點中,但是該結點已經滿了,需要分裂,將中間20上移到父結點中,其他按照50%分裂成兩個結點。

 

【第七步】:插入4

 

20170511095736211.jpg

 

由於4小於7,應該插入7的左結點中,但該結點滿了,需要進行分裂,將中間關鍵字4上移到父結點中,其他按照50%分裂成兩個結點。

 

【第八步】:插入16,18,24,25

 

20170511095743859.jpg

 

以上4個數字按大小直接插入到相應位置即可,無需分裂操作。

 

【第九步】:插入19

 

20170511095750270.jpg

 

插入19,需要放到18的後麵,但是由於該結點已滿,需要分裂操作,將中間關鍵字17上移到父結點中,其它按照50%分裂成14,16以及18,19兩個結點;別以為到這就結束了,再看17被上移到父結點中,由於父結點已經滿了,所以這時對父結點進行分裂,將中間關鍵字13上移形成新的父結點,其他按照50%分裂成4,7和17,20兩個結點,到此,數據插入全部完成,形成了一棵B-Tree。

 

 3、刪除操作

 

 刪除操作稍稍複雜一些,這裏就不舉例展開了。大概思路如下:

 

1)查找B-Tree中需刪除的元素,如果該元素在B-Tree中存在,則將該元素在其結點中進行刪除。

2)刪除該元素後,判斷該元素是否有左右孩子結點,如果有,則上移孩子結點中的某相近元素到父節點中,然後進入第三步;如果沒有,直接刪除後,進入第三步。

3)移動相應元素後,如果結點中元素個數小於ceil(m/2)-1,則需要看其相鄰兄弟結點是否足夠(結點中元素個數大於ceil(m/2)-1),如果足夠,則向父節點借一個元素;如果其相鄰兄弟都不夠,即借完之後其結點元素個數小於ceil(m/2)-1,那該結點與其相鄰的某一兄弟結點合並成一個結點,以此來滿足條件。

 

總之,對於索引文件,無論是插入還是刪除B-Tree結點,不斷地分裂和合並結點來維持B-Tree結構是非常昂貴的操作。

 

4、B+Tree介紹

 

MySQL索引采用B+Tree,它是應文件係統所需而產生的一種B-Tree的變形樹,他們的差異在於:

 

1) 非葉子結點的子樹指針與關鍵字個數相同;

2) B+樹父結點中的記錄,存儲的是下層子樹中的最小值;

3) 所有葉子結點通過一個鏈指針相連;

4) 所有關鍵字都在葉子結點出現。

 

如下麵是一棵典型的B+Tree(假設每個結點最多有4個關鍵字)

 

 

20170511095759187.jpg

 

其它特性與操作與B-Tree基本相同。到此,B-Tree和B+Tree基礎知識已經了解了,下麵的內容都是基於以上的概念。

 

二、MySQL索引實現

 

MySQL索引實現是在存儲引擎端,不同存儲引擎對索引實現方式是不同的,比如InnoDB和MyISAM,下麵我們重點介紹InnoDB引擎索引的實現方式。

 

1、InnoDB索引實現方式

 

 對於InnoDB表,數據文件ibd本身就是按B+Tree組織的一個索引結構,這棵樹的葉節點data域保存了完整的數據記錄。

 

舉例說明,下麵是students表,id是主鍵,name上有輔助索引,有6行數據記錄。

 

20170511095806764.jpg

 

假如在一棵5階B+Tree(關鍵字範圍[2,4]),它的主鍵索引組織結構如下:

 

20170511095812528.jpg

 

上圖是InnoDB主鍵索引的B+Tree,葉節點包含了完整的數據記錄,像這種索引叫做聚集索引。因為InnoDB的數據文件本身要按主鍵聚集,所以InnoDB要求表必須有主鍵(MyISAM可以沒有),如果沒有顯式指定,則MySQL會優先自動選擇一個可以唯一標識數據記錄的列作為主鍵,比如唯一索引列,如果不存在這種列,則MySQL自動為InnoDB表生成一個隱含字段作為主鍵,長度為6個字節,類型為longint。

 

輔助索引結構:

 

20170511095820659.jpg

 

對於secondary index,非葉子結點保存的是索引值,比如上麵的name字段。

 

葉子結點保存的不再是數據記錄了,而是主鍵值。

 

從上麵的B+Tree可以總結到:

MySQL聚集索引使得按主鍵的搜索非常高效的。

 

輔助索引需要搜索兩遍索引:

第一:檢索輔助索引獲得主鍵值

第二:用主鍵值到主鍵索引中檢索獲得記錄

 

到這裏,再來分析本文開頭提出的問題:

 

問題1:為什麼InnoDB表需要主鍵?

 

  • InnoDB表數據文件都是基於主鍵索引組織的,沒有主鍵,MySQL會想辦法給我搞定,所以主鍵必須要有;

  • 基於主鍵查詢效率高;

  • 其它類型索引都要引用主鍵索引;

 

問題3:為什麼不建議InnoDB表主鍵設置過長?

 

  • 因為輔助索引都保存引用主鍵索引,過長的主鍵索引使輔助索引變得過大;

 

三、InnoDB對B+Tree的改進

 

 在上麵的例子中:將下麵數字插入到一棵5階B-Tree中:[3,14,7,1,8,5,11,17,13,6,23,12,20,26,4,16,18,24,25,19]

 

插入這些無序數據一共經曆了6次分裂,對於磁盤索引文件而言,每次分裂都是很昂貴的操作;如果將以上數據排好序,再次插入是不是效果會好,我試驗了下,雖然每次都是插入到最右結點,涉及遷移數據量會少,但是分裂的次數依然挺多,需要7次分裂。

 

每次分裂都是按照50%進行,這樣存在明顯的缺點就是導致索引頁麵的空間利用率在50%左右;而且對於遞增插入效率也不好,平均每兩次插入,最右結點就得進行一次分裂。那InnoDB是如何進行改進的呢?

 

InnoDB其實隻是針對遞增/遞減情況進行了改進優化,不再采用50%的分裂策略,而是使用下麵的分裂策略:

 

1、插入新元素,判斷葉子結點空間是否足夠,如果足夠,直接插入;

2、如果葉子結點空間滿了,判斷父結點空間是否足夠,如果足夠,將該新元素插入到父結點中;如果父結點空間滿了,則進行分裂。

 

比如下麵一棵5階B+Tree:

 

20170511095829618.jpg

 

現在連續插入10,11,14,15,17,采用優化後分裂策略的分步圖例如下:

 

【第一步】:插入10

 

20170511095836642.jpg

 

由於最右結點還有空間,直接插入即可。

 

【第二步】:插入11

 

20170511095844456.jpg

 

插入11時,由於最右結點空間已滿,如果使用50%分裂策略,則需要分裂操作了,但是使用優化後的分裂策略,當該結點空間已滿,還要判斷該結點的父結點是否滿了,如果父結點還有空間,那麼插入到父結點中,所以11插入到父結點中了,同時形成一個子結點。

 

 【第三步】:插入14,15,17

 

20170511095851937.jpg

 

優化後的分裂策略僅僅針對遞增/遞減情況,顯著的減少了分裂次數並且大大提高了索引頁麵空間的利用率。

 

如果是隨機插入,可能會引起更高代價的分裂概率。所以InnoDB存儲引擎會為每個索引頁維護一個上次插入的位置變量,以及上次插入是遞增/遞減的標識。InnoDB能夠根據這些信息判斷新插入數據是否滿足遞增/遞減條件,若滿足,則采用改進後的分裂策略;若不滿足,則進行50%的分裂策略。

 

到此,我們可以回答本文開頭提出的另一個問題了:

 

問題2:為什麼建議InnoDB表主鍵是單調遞增?

 

  • 如果InnoDB表主鍵是單調遞增的,可以使用改進後的B+Tree分裂策略,顯著減少B-Tree分裂次數和數據遷移,從而提高數據插入效率。

  • 不僅如此,它還大大提高索引頁空間利用率。

 

小結

 

通過學習B+Tree數據結構,從而加深對MySQL索引存儲結構的理解,對我們設計、優化索引非常有幫助。以上就是我想跟大家分享的內容,歡迎大家一起交流學習。

 原文發布時間為:2017-05-11

本文來自雲棲社區合作夥伴DBAplus

最後更新:2017-05-17 14:02:18

  上一篇:go  一個執行計劃異常變更引發的Oracle性能診斷優化
  下一篇:go  餓了麼:日訂單量超900萬的架構設計及演進之路