MySQL數(shù)據(jù)庫(kù)索引的研究

摘要：數(shù)據(jù)庫(kù)索引是用于提高數(shù)據(jù)檢索速度的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，該文結(jié)合常用的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)B樹(shù)，分析索引的原理，并結(jié)合外存儲(chǔ)的原理，分析大多數(shù)數(shù)據(jù)庫(kù)使用B+樹(shù)作為索引結(jié)構(gòu)的原因，并結(jié)合MySQL數(shù)據(jù)庫(kù)中InnoDB存儲(chǔ)引擎中的索引實(shí)現(xiàn)，分析其優(yōu)缺點(diǎn)。

關(guān)鍵詞：B樹(shù)結(jié)構(gòu)；外存儲(chǔ)原理；MySQL索引

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8079-02

本文的內(nèi)容結(jié)構(gòu)如下所示：

第一部分主要從數(shù)據(jù)結(jié)構(gòu)及算法理論層面討論B-Tree。

第二部分結(jié)合外存儲(chǔ)器的存儲(chǔ)原理，討論使用BTree作為索引的原因。

第三部分討論MySQL數(shù)據(jù)庫(kù)中InnoDB數(shù)據(jù)存儲(chǔ)引擎中的索引——改進(jìn)的B+Tree的結(jié)構(gòu)，及其優(yōu)點(diǎn)。

1 索引的數(shù)據(jù)結(jié)構(gòu)及算法基礎(chǔ)

數(shù)據(jù)庫(kù)查詢(xún)是數(shù)據(jù)庫(kù)的最主要功能之一，提高數(shù)據(jù)查詢(xún)速度是數(shù)據(jù)庫(kù)索引的主要目標(biāo)，通常，研究者通過(guò)優(yōu)化檢索算法來(lái)提高查詢(xún)速度。查找算法有幾類(lèi)，一種是順序查找，算法的復(fù)雜度為O（n），另外有二分查找、二叉樹(shù)查找等。一般來(lái)說(shuō)，一種查找算法對(duì)應(yīng)一種數(shù)據(jù)結(jié)構(gòu)，例如順序查找對(duì)應(yīng)連續(xù)的數(shù)據(jù)，二分查找對(duì)應(yīng)排好序的數(shù)據(jù)，二叉樹(shù)搜索對(duì)應(yīng)二叉查找樹(shù)。但是，這類(lèi)數(shù)據(jù)結(jié)構(gòu)還完全不能滿足各種查找需求。比如，二分查找的條件要求將數(shù)據(jù)排序，但是數(shù)據(jù)庫(kù)中不可能同時(shí)將兩列都按順序存儲(chǔ)。所以，數(shù)據(jù)庫(kù)系統(tǒng)必須維護(hù)滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)——索引，以實(shí)現(xiàn)更高級(jí)的查找算法。

當(dāng)前，大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)都采用BTree作為索引結(jié)構(gòu)，其原因在于BTree的數(shù)據(jù)結(jié)構(gòu)和主流外存儲(chǔ)器的存儲(chǔ)原理。下面先介紹B-樹(shù)的基本結(jié)構(gòu)。

B-樹(shù)的基本屬性：

1） 定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子；且M>2；

2） 根結(jié)點(diǎn)的兒子數(shù)為[2， M]；

3） 除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2， M]；

4） 每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵詞；（至少2個(gè)關(guān)鍵詞）；

5） 非葉子結(jié)點(diǎn)的關(guān)鍵詞個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1；

6） 非葉子結(jié)點(diǎn)的關(guān)鍵詞：K[1]， K[2]， …， K[M-1]；且K[i] < K[i+1]；

7） 非葉子結(jié)點(diǎn)的指針：P[1]， P[2]， …， P[M]；其中P[1]指向關(guān)鍵詞小于K[1]的子樹(shù)，P[M]指向關(guān)鍵詞大于K[M-1]的子樹(shù)，其它P[i]指向關(guān)鍵詞屬于（K[i-1]， K[i]）的子樹(shù)；

8） 所有葉子結(jié)點(diǎn)位于同一層；

如圖1所示，是B-樹(shù)的基本結(jié)構(gòu)。關(guān)于如何在一棵B-樹(shù)中按照key的值去檢索數(shù)據(jù)，描述如下：

1） 以根節(jié)點(diǎn)作為入口，對(duì)key集合作二分查找，如果找到目標(biāo)key，則可以直接返回data數(shù)據(jù)。否則進(jìn)入第二步。

2） 找到相應(yīng)區(qū)間，根據(jù)區(qū)間的指針指向的point，得到對(duì)應(yīng)的節(jié)點(diǎn)，執(zhí)行1中過(guò)程。如此遞歸，直到找到目標(biāo)節(jié)點(diǎn)，或者最終返回null point。

加速一個(gè)B-樹(shù)的度為d，有N個(gè)key，現(xiàn)在為其建立索引，那么這棵B-樹(shù)的高h(yuǎn)最大為logd（（N+1）/2），查找目標(biāo)key，查找過(guò)程中需要遍歷節(jié)點(diǎn)個(gè)數(shù)的復(fù)雜度為O（logdN），與二叉查找和順序查找相比，B-樹(shù)是一個(gè)效率很高的索引數(shù)據(jù)結(jié)構(gòu)。

圖1 B-Tree的結(jié)構(gòu)

通常，數(shù)據(jù)庫(kù)中數(shù)據(jù)都很多，導(dǎo)致建立的索引也很大，很難全部存儲(chǔ)在內(nèi)存中，因此，通常將索引保存在磁盤(pán)中。這樣，在索引中查找時(shí)，就需要進(jìn)行磁盤(pán)I/O，而與內(nèi)存存取速度比較，磁盤(pán)I/O的速度要慢幾個(gè)數(shù)量級(jí)。所以，通常我們將在查找過(guò)程中磁盤(pán)的操作次數(shù)作為我們?cè)u(píng)價(jià)一種數(shù)據(jù)結(jié)構(gòu)是否適合作為索引的關(guān)鍵信息。那么，建立好的索引就是要盡量減少查找過(guò)程中磁盤(pán)I/O的次數(shù)。

了解磁盤(pán)的存取原理，對(duì)應(yīng)理解使用B-樹(shù)作為索引結(jié)構(gòu)必不可少。

2 磁盤(pán)的存儲(chǔ)原理

磁盤(pán)的內(nèi)部結(jié)構(gòu)如圖2所示。

操作系統(tǒng)在讀取磁盤(pán)數(shù)據(jù)時(shí)，將數(shù)據(jù)邏輯地址傳給磁盤(pán)，磁盤(pán)會(huì)將操作系統(tǒng)傳來(lái)的邏輯地址轉(zhuǎn)換為物理地址以確定需要讀取的數(shù)據(jù)的具體位置，即數(shù)據(jù)所在的磁道和扇區(qū)，那么，為了讀取目標(biāo)數(shù)據(jù)，磁盤(pán)需要將磁頭移動(dòng)到對(duì)應(yīng)的那個(gè)扇區(qū)上，磁盤(pán)是通過(guò)橫向移動(dòng)磁頭做到這點(diǎn)的。移動(dòng)磁頭的過(guò)程叫做尋道，而這個(gè)過(guò)程所耗費(fèi)時(shí)間叫做尋道時(shí)間。然后磁盤(pán)需要通過(guò)旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個(gè)過(guò)程所花費(fèi)的時(shí)間叫做旋轉(zhuǎn)時(shí)間。

圖2 磁盤(pán)的內(nèi)部構(gòu)造圖

磁盤(pán)的存儲(chǔ)結(jié)構(gòu)和尋址方式，導(dǎo)致了磁盤(pán)的存取速度比通常的主存儲(chǔ)器慢幾個(gè)數(shù)量級(jí)。磁盤(pán)在尋址過(guò)程中的需要的機(jī)械運(yùn)動(dòng)的時(shí)間，是導(dǎo)致磁盤(pán)在查找存儲(chǔ)數(shù)據(jù)速度緩慢的主要原因。所以，如果想要提高數(shù)據(jù)庫(kù)存儲(chǔ)速度，減少磁盤(pán)IO次數(shù)是主要途徑。其中一個(gè)可行的操作方案就是：每次尋址之后，預(yù)讀一定的磁盤(pán)空間的內(nèi)容。這樣在讀取相同大小空間的數(shù)據(jù)內(nèi)容時(shí)，減少了機(jī)械尋址的時(shí)間，可以大大減少磁盤(pán)的存儲(chǔ)速度。實(shí)際上，磁盤(pán)也正是這樣做的。通常，磁盤(pán)在讀取數(shù)據(jù)的時(shí)候，都會(huì)預(yù)取出一定長(zhǎng)度的數(shù)據(jù)塊，稱(chēng)為頁(yè)。通常，頁(yè)是4k大小。由前面對(duì)B樹(shù)的介紹我們可以知道，進(jìn)行一次檢索需要訪問(wèn)h（B樹(shù)的高度）個(gè)節(jié)點(diǎn)。那么，h的大小即是衡量一個(gè)索引好壞的標(biāo)準(zhǔn)。假設(shè)一個(gè)數(shù)據(jù)庫(kù)表中需要保存N條信息，B樹(shù)中每個(gè)節(jié)點(diǎn)保存d個(gè)key，那么由前文可知：h=logdN；d越大，h就越小。利用磁盤(pán)的預(yù)讀機(jī)制，我們可以將一棵B的節(jié)點(diǎn)大小設(shè)定為一個(gè)頁(yè)的大小，那么，在磁盤(pán)在預(yù)讀的時(shí)候，取出的一個(gè)頁(yè)都是有用key信息，這樣大大提高了數(shù)據(jù)的存儲(chǔ)效率，加快了檢索的過(guò)程。

由以上內(nèi)容可以判斷，B-樹(shù)非常適合作為索引結(jié)構(gòu)，其查找效率是非常高的。

3 MySQL中的索引結(jié)構(gòu)分析

B-樹(shù)有多重改進(jìn)版本，MySQL使用的B+樹(shù)就是其中一種。

B+樹(shù)的改進(jìn)有以下兩點(diǎn)：

1） 節(jié)點(diǎn)的指針數(shù)量可key數(shù)量一一對(duì)應(yīng)。

2） 內(nèi)節(jié)點(diǎn)不保存data，只保存key和指針；葉子節(jié)點(diǎn)只保存key和data，不存儲(chǔ)指針。

MySQL中索引的結(jié)構(gòu)如圖3所示：

B+樹(shù)的性能分析：

從B+樹(shù)的性質(zhì)我們可以知道，B+樹(shù)的內(nèi)節(jié)點(diǎn)不保存data值，只保存key和指針。那么，假設(shè)一個(gè)頁(yè)的大小空間用于保存一個(gè)節(jié)點(diǎn)，這樣在同一個(gè)節(jié)點(diǎn)中能夠保存的key值比B-樹(shù)結(jié)構(gòu)會(huì)更多，即d更大。由h=logdN可知，h更小。所以B+樹(shù)比B-樹(shù)更適合作為索引結(jié)構(gòu)。

由圖3中可以看到，MySQL索引的結(jié)構(gòu)，是一種改進(jìn)的B+樹(shù)，其每個(gè)葉子節(jié)點(diǎn)中都包含一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針。添加這個(gè)指針的目的是為了提高區(qū)間訪問(wèn)的性能。如圖3所示，查詢(xún)key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢(xún)效率。

4 總結(jié)

使用數(shù)據(jù)庫(kù)索引是提高數(shù)據(jù)庫(kù)查詢(xún)速度的關(guān)鍵因素，合理利用索引，對(duì)于提高數(shù)據(jù)庫(kù)性能有很大幫助。數(shù)據(jù)庫(kù)的性能優(yōu)化需要對(duì)數(shù)據(jù)庫(kù)的索引內(nèi)部結(jié)構(gòu)及其原理有深入的了解。該文闡述了BTree索引的基本原理，并說(shuō)明了MySQL數(shù)據(jù)庫(kù)的索引實(shí)現(xiàn)，為索引調(diào)優(yōu)和數(shù)據(jù)庫(kù)性能優(yōu)化提供了有效的幫助。

參考文獻(xiàn)：

[1] D Comer.Ubiquitous B-tree； ACM Computing Surveys （CSUR）， 1979.

[2] Codd E F.A relational model of data for large shared data banks L[M].Communications of the ACM， 1970，13（6）：377-387.

[3] Baron Scbwartz.高性能MySQL[M].王小東，譯.北京：電子工業(yè)出版社，2010.

[4] 姜承堯.MySQL技術(shù)內(nèi)幕-InnoDB存儲(chǔ)引擎[M].北京：機(jī)械工業(yè)出版社，2011.

由以上內(nèi)容可以判斷，B-樹(shù)非常適合作為索引結(jié)構(gòu)，其查找效率是非常高的。

3 MySQL中的索引結(jié)構(gòu)分析

B-樹(shù)有多重改進(jìn)版本，MySQL使用的B+樹(shù)就是其中一種。

B+樹(shù)的改進(jìn)有以下兩點(diǎn)：

1） 節(jié)點(diǎn)的指針數(shù)量可key數(shù)量一一對(duì)應(yīng)。

2） 內(nèi)節(jié)點(diǎn)不保存data，只保存key和指針；葉子節(jié)點(diǎn)只保存key和data，不存儲(chǔ)指針。

MySQL中索引的結(jié)構(gòu)如圖3所示：

B+樹(shù)的性能分析：

從B+樹(shù)的性質(zhì)我們可以知道，B+樹(shù)的內(nèi)節(jié)點(diǎn)不保存data值，只保存key和指針。那么，假設(shè)一個(gè)頁(yè)的大小空間用于保存一個(gè)節(jié)點(diǎn)，這樣在同一個(gè)節(jié)點(diǎn)中能夠保存的key值比B-樹(shù)結(jié)構(gòu)會(huì)更多，即d更大。由h=logdN可知，h更小。所以B+樹(shù)比B-樹(shù)更適合作為索引結(jié)構(gòu)。

由圖3中可以看到，MySQL索引的結(jié)構(gòu)，是一種改進(jìn)的B+樹(shù)，其每個(gè)葉子節(jié)點(diǎn)中都包含一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針。添加這個(gè)指針的目的是為了提高區(qū)間訪問(wèn)的性能。如圖3所示，查詢(xún)key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢(xún)效率。

4 總結(jié)

使用數(shù)據(jù)庫(kù)索引是提高數(shù)據(jù)庫(kù)查詢(xún)速度的關(guān)鍵因素，合理利用索引，對(duì)于提高數(shù)據(jù)庫(kù)性能有很大幫助。數(shù)據(jù)庫(kù)的性能優(yōu)化需要對(duì)數(shù)據(jù)庫(kù)的索引內(nèi)部結(jié)構(gòu)及其原理有深入的了解。該文闡述了BTree索引的基本原理，并說(shuō)明了MySQL數(shù)據(jù)庫(kù)的索引實(shí)現(xiàn)，為索引調(diào)優(yōu)和數(shù)據(jù)庫(kù)性能優(yōu)化提供了有效的幫助。

參考文獻(xiàn)：

[1] D Comer.Ubiquitous B-tree； ACM Computing Surveys （CSUR）， 1979.

[2] Codd E F.A relational model of data for large shared data banks L[M].Communications of the ACM， 1970，13（6）：377-387.

[3] Baron Scbwartz.高性能MySQL[M].王小東，譯.北京：電子工業(yè)出版社，2010.

[4] 姜承堯.MySQL技術(shù)內(nèi)幕-InnoDB存儲(chǔ)引擎[M].北京：機(jī)械工業(yè)出版社，2011.

由以上內(nèi)容可以判斷，B-樹(shù)非常適合作為索引結(jié)構(gòu)，其查找效率是非常高的。

3 MySQL中的索引結(jié)構(gòu)分析

B-樹(shù)有多重改進(jìn)版本，MySQL使用的B+樹(shù)就是其中一種。

B+樹(shù)的改進(jìn)有以下兩點(diǎn)：

1） 節(jié)點(diǎn)的指針數(shù)量可key數(shù)量一一對(duì)應(yīng)。

2） 內(nèi)節(jié)點(diǎn)不保存data，只保存key和指針；葉子節(jié)點(diǎn)只保存key和data，不存儲(chǔ)指針。

MySQL中索引的結(jié)構(gòu)如圖3所示：

B+樹(shù)的性能分析：

從B+樹(shù)的性質(zhì)我們可以知道，B+樹(shù)的內(nèi)節(jié)點(diǎn)不保存data值，只保存key和指針。那么，假設(shè)一個(gè)頁(yè)的大小空間用于保存一個(gè)節(jié)點(diǎn)，這樣在同一個(gè)節(jié)點(diǎn)中能夠保存的key值比B-樹(shù)結(jié)構(gòu)會(huì)更多，即d更大。由h=logdN可知，h更小。所以B+樹(shù)比B-樹(shù)更適合作為索引結(jié)構(gòu)。

由圖3中可以看到，MySQL索引的結(jié)構(gòu)，是一種改進(jìn)的B+樹(shù)，其每個(gè)葉子節(jié)點(diǎn)中都包含一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針。添加這個(gè)指針的目的是為了提高區(qū)間訪問(wèn)的性能。如圖3所示，查詢(xún)key為從18到49的所有數(shù)據(jù)記錄，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問(wèn)到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢(xún)效率。

4 總結(jié)

使用數(shù)據(jù)庫(kù)索引是提高數(shù)據(jù)庫(kù)查詢(xún)速度的關(guān)鍵因素，合理利用索引，對(duì)于提高數(shù)據(jù)庫(kù)性能有很大幫助。數(shù)據(jù)庫(kù)的性能優(yōu)化需要對(duì)數(shù)據(jù)庫(kù)的索引內(nèi)部結(jié)構(gòu)及其原理有深入的了解。該文闡述了BTree索引的基本原理，并說(shuō)明了MySQL數(shù)據(jù)庫(kù)的索引實(shí)現(xiàn)，為索引調(diào)優(yōu)和數(shù)據(jù)庫(kù)性能優(yōu)化提供了有效的幫助。

參考文獻(xiàn)：

[1] D Comer.Ubiquitous B-tree； ACM Computing Surveys （CSUR）， 1979.

[2] Codd E F.A relational model of data for large shared data banks L[M].Communications of the ACM， 1970，13（6）：377-387.

[3] Baron Scbwartz.高性能MySQL[M].王小東，譯.北京：電子工業(yè)出版社，2010.

[4] 姜承堯.MySQL技術(shù)內(nèi)幕-InnoDB存儲(chǔ)引擎[M].北京：機(jī)械工業(yè)出版社，2011.