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

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

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

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

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

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

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

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

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

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

B-樹的基本屬性：

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]的子樹，P[M]指向關(guān)鍵詞大于K[M-1]的子樹，其它P[i]指向關(guān)鍵詞屬于（K[i-1]， K[i]）的子樹；

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

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

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

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

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

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

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

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

2 磁盤的存儲原理

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

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

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

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

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

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

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

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

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

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

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

B+樹的性能分析：

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

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

4 總結(jié)

使用數(shù)據(jù)庫索引是提高數(shù)據(jù)庫查詢速度的關(guān)鍵因素，合理利用索引，對于提高數(shù)據(jù)庫性能有很大幫助。數(shù)據(jù)庫的性能優(yōu)化需要對數(shù)據(jù)庫的索引內(nèi)部結(jié)構(gòu)及其原理有深入的了解。該文闡述了BTree索引的基本原理，并說明了MySQL數(shù)據(jù)庫的索引實(shí)現(xiàn)，為索引調(diào)優(yōu)和數(shù)據(jù)庫性能優(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存儲引擎[M].北京：機(jī)械工業(yè)出版社，2011.

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

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

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

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

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

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

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

B+樹的性能分析：

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

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

4 總結(jié)

使用數(shù)據(jù)庫索引是提高數(shù)據(jù)庫查詢速度的關(guān)鍵因素，合理利用索引，對于提高數(shù)據(jù)庫性能有很大幫助。數(shù)據(jù)庫的性能優(yōu)化需要對數(shù)據(jù)庫的索引內(nèi)部結(jié)構(gòu)及其原理有深入的了解。該文闡述了BTree索引的基本原理，并說明了MySQL數(shù)據(jù)庫的索引實(shí)現(xiàn)，為索引調(diào)優(yōu)和數(shù)據(jù)庫性能優(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存儲引擎[M].北京：機(jī)械工業(yè)出版社，2011.

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

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

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

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

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

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

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

B+樹的性能分析：

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

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

4 總結(jié)

使用數(shù)據(jù)庫索引是提高數(shù)據(jù)庫查詢速度的關(guān)鍵因素，合理利用索引，對于提高數(shù)據(jù)庫性能有很大幫助。數(shù)據(jù)庫的性能優(yōu)化需要對數(shù)據(jù)庫的索引內(nèi)部結(jié)構(gòu)及其原理有深入的了解。該文闡述了BTree索引的基本原理，并說明了MySQL數(shù)據(jù)庫的索引實(shí)現(xiàn)，為索引調(diào)優(yōu)和數(shù)據(jù)庫性能優(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存儲引擎[M].北京：機(jī)械工業(yè)出版社，2011.