《MySQL索引設(shè)計(jì)背后的數(shù)據(jù)結(jié)構(gòu)及算法詳解》要點(diǎn)：
本文介紹了MySQL索引設(shè)計(jì)背后的數(shù)據(jù)結(jié)構(gòu)及算法詳解，希望對(duì)您有用。如果有疑問，可以聯(lián)系我們。

 

在我們公司的DB規(guī)范中,明確規(guī)定：

1、建表語句必須明確指定主鍵

2、無特殊情況,主鍵必須單調(diào)遞增

對(duì)于這項(xiàng)規(guī)定,很多研發(fā)小伙伴不理解.本文就來深入分析MySQL索引設(shè)計(jì)背后的數(shù)據(jù)結(jié)構(gòu)和算法,從而幫你釋疑以下幾個(gè)問題：

1、為什么InnoDB表需要主鍵?

2、為什么建議InnoDB表主鍵是單調(diào)遞增?

3、為什么不建議InnoDB表主鍵設(shè)置過長?

一、B-Tree基礎(chǔ)知識(shí)

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

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

1) 根結(jié)點(diǎn)的孩子數(shù)>=2(前提是樹高度大于1)

2) 除根結(jié)點(diǎn)與葉子結(jié)點(diǎn),其它結(jié)點(diǎn)的孩子數(shù)為[ceil(m/2),m]個(gè).ceil函數(shù)表示上取整數(shù).

3) 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層,葉子結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù).

4) 各個(gè)結(jié)點(diǎn)包含n個(gè)關(guān)鍵字信息：(P0,K1,P1,K2,P2……Kn,Pn)

• Ki(i=1,2……n)為關(guān)鍵字,且K(i-1)<Ki,即從小到大排序
• 關(guān)鍵字的個(gè)數(shù)n必須滿足：[ceil(m/2)-1,m-1]
• 4.3) Pi指向子樹,且指針P(i-1)所指向的子樹結(jié)點(diǎn)中所有關(guān)鍵字均小于Ki.即：父結(jié)點(diǎn)中任何關(guān)鍵字的左孩子都小于它,右孩子大于它.

2、B-Tree插入操作

1)插入新元素,如果葉子結(jié)點(diǎn)空間足夠,則插入其中,遵循從小到大排序；

2)如果該結(jié)點(diǎn)空間滿了,進(jìn)行分裂.將該結(jié)點(diǎn)中一半關(guān)鍵字分裂到新結(jié)點(diǎn)中,中間關(guān)鍵字上移到父結(jié)點(diǎn)中.

【舉例】如果單從上面特性及插入規(guī)則看得不明白,請結(jié)合以下分步驟圖例：

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

首先根據(jù)B-Tree特性知道,每個(gè)結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍是: ? 2<=n<=4

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

到這里,第一個(gè)結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)量剛好滿了.

【第二步】：插入8

由于8是大于7的,故應(yīng)該插入右子樹,一個(gè)結(jié)點(diǎn)中最多存儲(chǔ)4個(gè)關(guān)鍵字,按照插入規(guī)則,將中間關(guān)鍵字7上移形成父結(jié)點(diǎn),其他按照50%分裂成兩個(gè)結(jié)點(diǎn),如上圖.

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

由于5小于7,插入左子樹,11,17大于7,插入右子樹.葉子結(jié)點(diǎn)沒有滿4個(gè)關(guān)鍵字,故可以直接插入5,11,17.

【第四步】：插入13

13大于7,應(yīng)該插入右子樹結(jié)點(diǎn)中,由于該結(jié)點(diǎn)中滿4個(gè)關(guān)鍵字了,需要進(jìn)行分裂.13剛好是中間關(guān)鍵字,上移到父結(jié)點(diǎn)中；其他按照50%分裂成兩個(gè)結(jié)點(diǎn).

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

以上幾個(gè)數(shù)字按照規(guī)則直接插入即可,無需分裂操作.

【第六步】：插入26

由于26大于13,應(yīng)該插入13的右子樹結(jié)點(diǎn)中,但是該結(jié)點(diǎn)已經(jīng)滿了,需要分裂,將中間20上移到父結(jié)點(diǎn)中,其他按照50%分裂成兩個(gè)結(jié)點(diǎn).

【第七步】：插入4

由于4小于7,應(yīng)該插入7的左結(jié)點(diǎn)中,但該結(jié)點(diǎn)滿了,需要進(jìn)行分裂,將中間關(guān)鍵字4上移到父結(jié)點(diǎn)中,其他按照50%分裂成兩個(gè)結(jié)點(diǎn).

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

以上4個(gè)數(shù)字按大小直接插入到相應(yīng)位置即可,無需分裂操作.

【第九步】：插入19

插入19,需要放到18的后面,但是由于該結(jié)點(diǎn)已滿,需要分裂操作,將中間關(guān)鍵字17上移到父結(jié)點(diǎn)中,其它按照50%分裂成14,16以及18,19兩個(gè)結(jié)點(diǎn)；別以為到這就結(jié)束了,再看17被上移到父結(jié)點(diǎn)中,由于父結(jié)點(diǎn)已經(jīng)滿了,所以這時(shí)對(duì)父結(jié)點(diǎn)進(jìn)行分裂,將中間關(guān)鍵字13上移形成新的父結(jié)點(diǎn),其他按照50%分裂成4,7和17,20兩個(gè)結(jié)點(diǎn),到此,數(shù)據(jù)插入全部完成,形成了一棵B-Tree.

?3、刪除操作

刪除操作稍稍復(fù)雜一些,這里就不舉例展開了.大概思路如下：

1)查找B-Tree中需刪除的元素,如果該元素在B-Tree中存在,則將該元素在其結(jié)點(diǎn)中進(jìn)行刪除.

2)刪除該元素后,判斷該元素是否有左右孩子結(jié)點(diǎn),如果有,則上移孩子結(jié)點(diǎn)中的某相近元素到父節(jié)點(diǎn)中,然后進(jìn)入第三步；如果沒有,直接刪除后,進(jìn)入第三步.

3)移動(dòng)相應(yīng)元素后,如果結(jié)點(diǎn)中元素個(gè)數(shù)小于ceil(m/2)-1,則需要看其相鄰兄弟結(jié)點(diǎn)是否足夠(結(jié)點(diǎn)中元素個(gè)數(shù)大于ceil(m/2)-1),如果足夠,則向父節(jié)點(diǎn)借一個(gè)元素；如果其相鄰兄弟都不夠,即借完之后其結(jié)點(diǎn)元素個(gè)數(shù)小于ceil(m/2)-1,那該結(jié)點(diǎn)與其相鄰的某一兄弟結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn),以此來滿足條件.

總之,對(duì)于索引文件,無論是插入還是刪除B-Tree結(jié)點(diǎn),不斷地分裂和合并結(jié)點(diǎn)來維持B-Tree結(jié)構(gòu)是非常昂貴的操作.

4、B+Tree介紹

MySQL索引采用B+Tree,它是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-Tree的變形樹,他們的差異在于：

1) 非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同；

2) B+樹父結(jié)點(diǎn)中的記錄,存儲(chǔ)的是下層子樹中的最小值；

3) 所有葉子結(jié)點(diǎn)通過一個(gè)鏈指針相連；

4) 所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn).

如下面是一棵典型的B+Tree(假設(shè)每個(gè)結(jié)點(diǎn)最多有4個(gè)關(guān)鍵字)

其它特性與操作與B-Tree基本相同.到此,B-Tree和B+Tree基礎(chǔ)知識(shí)已經(jīng)了解了,下面的內(nèi)容都是基于以上的概念.

二、MySQL索引實(shí)現(xiàn)

MySQL索引實(shí)現(xiàn)是在存儲(chǔ)引擎端,不同存儲(chǔ)引擎對(duì)索引實(shí)現(xiàn)方式是不同的,比如InnoDB和MyISAM,下面我們重點(diǎn)介紹InnoDB引擎索引的實(shí)現(xiàn)方式.

1、InnoDB索引實(shí)現(xiàn)方式

對(duì)于InnoDB表,數(shù)據(jù)文件ibd本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu),這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄.

舉例說明,下面是students表,id是主鍵,name上有輔助索引,有6行數(shù)據(jù)記錄.

假如在一棵5階B+Tree(關(guān)鍵字范圍[2,4]),它的主鍵索引組織結(jié)構(gòu)如下：

上圖是InnoDB主鍵索引的B+Tree,葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄,像這種索引叫做聚集索引.因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集,所以InnoDB要求表必須有主鍵(MyISAM可以沒有),如果沒有顯式指定,則MySQL會(huì)優(yōu)先自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵,比如唯一索引列,如果不存在這種列,則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵,長度為6個(gè)字節(jié),類型為longint.

輔助索引結(jié)構(gòu)：

對(duì)于secondary index,非葉子結(jié)點(diǎn)保存的是索引值,比如上面的name字段.

葉子結(jié)點(diǎn)保存的不再是數(shù)據(jù)記錄了,而是主鍵值.

從上面的B+Tree可以總結(jié)到：

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

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

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

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

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

問題1：為什么InnoDB表需要主鍵?

• InnoDB表數(shù)據(jù)文件都是基于主鍵索引組織的,沒有主鍵,MySQL會(huì)想辦法給我搞定,所以主鍵必須要有；
• 基于主鍵查詢效率高；
• 其它類型索引都要引用主鍵索引；

問題3：為什么不建議InnoDB表主鍵設(shè)置過長?

• 因?yàn)檩o助索引都保存引用主鍵索引,過長的主鍵索引使輔助索引變得過大；

三、InnoDB對(duì)B+Tree的改進(jìn)

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

插入這些無序數(shù)據(jù)一共經(jīng)歷了6次分裂,對(duì)于磁盤索引文件而言,每次分裂都是很昂貴的操作；如果將以上數(shù)據(jù)排好序,再次插入是不是效果會(huì)好,我試驗(yàn)了下,雖然每次都是插入到最右結(jié)點(diǎn),涉及遷移數(shù)據(jù)量會(huì)少,但是分裂的次數(shù)依然挺多,需要7次分裂.

每次分裂都是按照50%進(jìn)行,這樣存在明顯的缺點(diǎn)就是導(dǎo)致索引頁面的空間利用率在50%左右；而且對(duì)于遞增插入效率也不好,平均每兩次插入,最右結(jié)點(diǎn)就得進(jìn)行一次分裂.那InnoDB是如何進(jìn)行改進(jìn)的呢?

InnoDB其實(shí)只是針對(duì)遞增/遞減情況進(jìn)行了改進(jìn)優(yōu)化,不再采用50%的分裂策略,而是使用下面的分裂策略：

1、插入新元素,判斷葉子結(jié)點(diǎn)空間是否足夠,如果足夠,直接插入；

2、如果葉子結(jié)點(diǎn)空間滿了,判斷父結(jié)點(diǎn)空間是否足夠,如果足夠,將該新元素插入到父結(jié)點(diǎn)中；如果父結(jié)點(diǎn)空間滿了,則進(jìn)行分裂.

比如下面一棵5階B+Tree：

現(xiàn)在連續(xù)插入10,11,14,15,17,采用優(yōu)化后分裂策略的分步圖例如下：

【第一步】：插入10

由于最右結(jié)點(diǎn)還有空間,直接插入即可.

【第二步】：插入11

插入11時(shí),由于最右結(jié)點(diǎn)空間已滿,如果使用50%分裂策略,則需要分裂操作了,但是使用優(yōu)化后的分裂策略,當(dāng)該結(jié)點(diǎn)空間已滿,還要判斷該結(jié)點(diǎn)的父結(jié)點(diǎn)是否滿了,如果父結(jié)點(diǎn)還有空間,那么插入到父結(jié)點(diǎn)中,所以11插入到父結(jié)點(diǎn)中了,同時(shí)形成一個(gè)子結(jié)點(diǎn).

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

優(yōu)化后的分裂策略僅僅針對(duì)遞增/遞減情況,顯著的減少了分裂次數(shù)并且大大提高了索引頁面空間的利用率.

如果是隨機(jī)插入,可能會(huì)引起更高代價(jià)的分裂概率.所以InnoDB存儲(chǔ)引擎會(huì)為每個(gè)索引頁維護(hù)一個(gè)上次插入的位置變量,以及上次插入是遞增/遞減的標(biāo)識(shí).InnoDB能夠根據(jù)這些信息判斷新插入數(shù)據(jù)是否滿足遞增/遞減條件,若滿足,則采用改進(jìn)后的分裂策略；若不滿足,則進(jìn)行50%的分裂策略.

到此,我們可以回答本文開頭提出的另一個(gè)問題了：

問題2：為什么建議InnoDB表主鍵是單調(diào)遞增?

• 如果InnoDB表主鍵是單調(diào)遞增的,可以使用改進(jìn)后的B+Tree分裂策略,顯著減少B-Tree分裂次數(shù)和數(shù)據(jù)遷移,從而提高數(shù)據(jù)插入效率.
• 不僅如此,它還大大提高索引頁空間利用率.

小結(jié)

通過學(xué)習(xí)B+Tree數(shù)據(jù)結(jié)構(gòu),從而加深對(duì)MySQL索引存儲(chǔ)結(jié)構(gòu)的理解,對(duì)我們設(shè)計(jì)、優(yōu)化索引非常有幫助.以上就是我想跟大家分享的內(nèi)容,歡迎大家一起交流學(xué)習(xí).

作者介紹：

趙海亮,現(xiàn)任職58趕集集團(tuán)安居客MySQL DBA,主要從事安居客MySQL數(shù)據(jù)庫的優(yōu)化、升級(jí)、遷移等工作.

文章來自微信公眾號(hào)：DBAplus社群

轉(zhuǎn)載請注明本頁網(wǎng)址：
http://www.fzlkiss.com/jiaocheng/4141.html