MySQL索引改進(jìn)的B+樹的研究

林榮杭 劉小英

摘要：MySQL數(shù)據(jù)庫(kù)采用了B+樹作為索引的數(shù)據(jù)結(jié)構(gòu)，傳統(tǒng)的B+樹的葉子節(jié)點(diǎn)是一個(gè)單向的指針，這使得在范圍搜索數(shù)據(jù)時(shí)，只能單方面查找一個(gè)方向的數(shù)據(jù)，極大地增加了數(shù)據(jù)查找的時(shí)間。為了增加MySQL數(shù)據(jù)庫(kù)中索引的搜索效率，提出一種改進(jìn)的B+樹，通過對(duì)B+樹的葉子節(jié)點(diǎn)增加一個(gè)雙向的指針，提出雙向查找數(shù)據(jù)的B+樹算法，通過與原生B+樹的搜索進(jìn)行對(duì)比發(fā)現(xiàn)，改進(jìn)的B+樹在范圍搜索方面可以極大地減少搜索時(shí)間和I/O次數(shù)。

關(guān)鍵詞：數(shù)據(jù)庫(kù);B+樹;數(shù)據(jù)結(jié)構(gòu);MySQL

中圖分類號(hào)：TP301? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）16-0012-02

數(shù)據(jù)庫(kù)作為目前最有效地管理數(shù)據(jù)的方式被廣泛應(yīng)用于各類應(yīng)用系統(tǒng)中[1-2]。在大量的數(shù)據(jù)庫(kù)選型中，MySQL數(shù)據(jù)庫(kù)因?yàn)樽陨黹_源，輕便，速度快的優(yōu)勢(shì)成了最為頻繁使用的數(shù)據(jù)庫(kù)之一[3-5]。在MySQL數(shù)據(jù)庫(kù)的底層，為了方便對(duì)數(shù)據(jù)的查找、插入、刪除、修改以及維護(hù)，MySQL數(shù)據(jù)庫(kù)在眾多的數(shù)據(jù)結(jié)構(gòu)中選擇了B+樹這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)索引、實(shí)現(xiàn)底層的數(shù)據(jù)信息管理。B+樹是多路查找樹B樹的一個(gè)變種[6]，同時(shí)B+樹的樹結(jié)構(gòu)是多路搜索的平衡樹，數(shù)據(jù)僅存儲(chǔ)在葉子節(jié)點(diǎn)中，非葉子結(jié)點(diǎn)引導(dǎo)搜索，同時(shí)為了有效檢索所有的葉子頁面，葉子節(jié)點(diǎn)間通過指針相互鏈接[7]。本文在研究了傳統(tǒng)B+樹搜索的原理后，對(duì)B+樹的葉子結(jié)點(diǎn)進(jìn)行了優(yōu)化，有效地提高了搜索效率。

1 傳統(tǒng)B+樹

1.1 B+樹的特征

B+ tree 是一種多叉樹，每個(gè)節(jié)點(diǎn)可以擁有大量子節(jié)點(diǎn)，同一個(gè)樹中允許不同的節(jié)點(diǎn)可以擁有不同數(shù)量的子節(jié)點(diǎn)[8]。一棵B+ tree由一個(gè)根節(jié)點(diǎn)、若干個(gè)內(nèi)部節(jié)點(diǎn)和若干個(gè)葉節(jié)點(diǎn)組成。B+樹中數(shù)據(jù)以鍵值對(duì)（Key - value）的形式存儲(chǔ)在樹中，非葉子節(jié)點(diǎn)只存儲(chǔ)鍵（Key），而在葉子節(jié)點(diǎn)中存儲(chǔ)鍵和值（Key - value）。通過觀察圖1，一個(gè)3階的B+樹，可以發(fā)現(xiàn)B+樹一個(gè)節(jié)點(diǎn)可以存放多個(gè)值。一顆階為P的B+樹，它的Root（根）節(jié)點(diǎn)至少應(yīng)該有兩個(gè)子節(jié)點(diǎn)，同時(shí)Root節(jié)點(diǎn)最多只能擁有P個(gè)孩子節(jié)點(diǎn)。同時(shí)這個(gè)B+樹的每個(gè)非葉子節(jié)點(diǎn)最多也只有P個(gè)孩子節(jié)點(diǎn)，最少應(yīng)該存在兩個(gè)節(jié)點(diǎn)，這個(gè)特性和Root節(jié)點(diǎn)一樣。而每個(gè)葉子節(jié)點(diǎn)中最多存在P-1個(gè)元素，最少存在?P/2?個(gè)元素。

1.2 B+樹對(duì)數(shù)據(jù)的操作

B+樹對(duì)數(shù)據(jù)的操作主要包括查找、插入和刪除。對(duì)數(shù)據(jù)進(jìn)行插入和刪除的時(shí)候，B+樹會(huì)判斷每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)是否滿足最多存在P-1個(gè)元素，最少存在?P/2?個(gè)元素的規(guī)則，不滿足則實(shí)現(xiàn)上溢或者下溢操作，調(diào)整樹的平衡，在自我平衡后B+樹每個(gè)葉子節(jié)點(diǎn)到Root節(jié)點(diǎn)的深度也是一樣的。在進(jìn)行數(shù)據(jù)插入操作時(shí)，B+樹會(huì)對(duì)插入數(shù)據(jù)進(jìn)行排序，實(shí)現(xiàn)自身數(shù)據(jù)結(jié)構(gòu)的有序性。在對(duì)數(shù)據(jù)進(jìn)行有序排序后，B+樹在葉子節(jié)點(diǎn)會(huì)利用一個(gè)單向鏈表形式的數(shù)據(jù)結(jié)構(gòu)將葉子節(jié)點(diǎn)的所有節(jié)點(diǎn)有序的串聯(lián)在一起。在進(jìn)行查找操作時(shí)，B+樹會(huì)通過非葉子節(jié)點(diǎn)來逐個(gè)定位到一個(gè)需要查找的范圍，然后在這個(gè)范圍的葉子節(jié)點(diǎn)進(jìn)行搜索，搜索的方式則是通過葉子節(jié)點(diǎn)的單向鏈表來查找數(shù)據(jù)。

2 改進(jìn)的B+樹

2.1改進(jìn)思路

通過觀察B+樹的查找方式不難發(fā)現(xiàn)，B+樹在查找一個(gè)數(shù)據(jù)時(shí)首先定位某個(gè)非葉節(jié)點(diǎn)是否存在該數(shù)據(jù)，不存在則在一個(gè)范圍內(nèi)的葉子節(jié)點(diǎn)中通過單向鏈表查找，但是當(dāng)葉子節(jié)點(diǎn)過多時(shí)就會(huì)發(fā)生鏈表長(zhǎng)度過長(zhǎng)，此時(shí)采用單向鏈表查找模式就會(huì)出現(xiàn)極大的時(shí)間浪費(fèi)，同時(shí)也不利于MySQL數(shù)據(jù)庫(kù)對(duì)數(shù)據(jù)的精確范圍查找，因?yàn)閱蜗蜴湵碇挥幸粋€(gè)方向，無法滿足在使用MySQL數(shù)據(jù)庫(kù)時(shí)出現(xiàn)的雙向查找，所以需要讓B+樹的葉子節(jié)點(diǎn)不只是單向的鏈接，而是可以雙向循環(huán)的鏈接，讓數(shù)據(jù)查找時(shí)可以隨意沿著某個(gè)方向去查找，如圖2所示。

2.2改進(jìn)后的B+樹算法

MySQL數(shù)據(jù)庫(kù)在進(jìn)行數(shù)據(jù)操作時(shí)常會(huì)使用范圍的查找，例如使用select * from * where x（字段）

以下是改進(jìn)后的B+樹搜索算法

輸入：第一個(gè)滿足小于搜索值（Key）的位置

輸出：獲取到所有滿足小于搜索值（Key）的值

List findless（V key，List list） {

if（this.number <=0）? //判斷當(dāng)前葉子節(jié)點(diǎn)是否存在值

return null;

Integer left = 0;? ?//葉子節(jié)點(diǎn)內(nèi)部是個(gè)數(shù)組

Integer right = this.number;

Integer i = 0;

while（true） {

if（key.compareTo（i） <= 0） { //獲取所有小于Key的值

list.add（this.values[i++]）;

}else {? //表示已經(jīng)遍歷完當(dāng)前葉子節(jié)點(diǎn)中所有小于Key的值

if（this.prev.title.equals（"end"））{

break; //判斷指針是否已經(jīng)移動(dòng)到最右邊的葉子節(jié)點(diǎn)

}

this.key = prev.key; //將當(dāng)前的key數(shù)組指向葉子節(jié)點(diǎn)左邊的葉子節(jié)點(diǎn)的key數(shù)組

this.values = prev.values;//同上操作，讓values數(shù)組指向左邊的values數(shù)組

}

}

return list;}

在改進(jìn)了B+樹的搜索算法后，B+樹的搜索小于某個(gè)值的流程為：

1）調(diào)用搜索算法先定位到第一個(gè)小于或等于搜索值的臨界值;

2）對(duì)臨界值的葉子節(jié)點(diǎn)進(jìn)行遍歷，因?yàn)槭菙?shù)組，其遍歷的時(shí)間復(fù)雜度為O（1）;

3）遇到第一個(gè)大于搜索值的數(shù)據(jù)時(shí)，將Key和Values數(shù)組移動(dòng)到前一個(gè)葉子節(jié)點(diǎn)中;

4）遍歷前一個(gè)葉子節(jié)點(diǎn)數(shù)據(jù);

5）遍歷完后檢查前一個(gè)葉子節(jié)點(diǎn)是否為右邊最后一個(gè)節(jié)點(diǎn)，如果是則結(jié)束遍歷操作，并返回值，不是繼續(xù)移動(dòng)指針并遍歷。

3 實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)對(duì)比

為了驗(yàn)證改進(jìn)后的B+樹在MySQL中搜索效率的提升，本文選擇Java為編程語言，在Eclipse上分別對(duì)改進(jìn)前后的B+樹進(jìn)行了構(gòu)建，并通過兩者的I/O次數(shù)和查找用時(shí)來探討改進(jìn)后的B+樹在數(shù)據(jù)查找方面的優(yōu)勢(shì)。在實(shí)驗(yàn)中采取了控制變量法用于提高實(shí)驗(yàn)的可信性，實(shí)驗(yàn)中的B+樹為512階，并且搜索5條數(shù)據(jù)（搜索結(jié)果只有5條數(shù)據(jù)，格式為大于x和小于y），得到結(jié)果如表1、表2所示。

3.2實(shí)驗(yàn)數(shù)據(jù)分析

由表1可以得出，隨著數(shù)據(jù)量的增加，雖然搜索的數(shù)據(jù)一直都只有5條數(shù)據(jù)，但是由于搜索的5條數(shù)據(jù)是雙向的，而初始的B+樹當(dāng)中葉子節(jié)點(diǎn)是一個(gè)單向鏈表，無法滿足對(duì)數(shù)據(jù)的雙向搜索，所以會(huì)產(chǎn)生更多的I/O次數(shù)，當(dāng)數(shù)據(jù)達(dá)到105級(jí)別時(shí)會(huì)出現(xiàn)I/O次數(shù)驟升的情況。改進(jìn)后的B+樹，因?yàn)槿~子節(jié)點(diǎn)是雙向循環(huán)的，所以每次搜索的I/O次數(shù)都十分平均，沒有出現(xiàn)驟升的情況。由表2可以得出，原B+樹在數(shù)據(jù)量為105由于I/O次數(shù)的增加，其搜索時(shí)間也突然增加，但是改進(jìn)后的B+樹并不會(huì)出現(xiàn)這種現(xiàn)象，這也增加了搜索的穩(wěn)定性，不會(huì)出現(xiàn)突然間的時(shí)間增大。在數(shù)據(jù)逐漸增大的過程中MySQL使用改進(jìn)后的B+樹時(shí)所帶來的時(shí)間消耗并不會(huì)出現(xiàn)突然性的增加，而是一個(gè)平緩的過程，這證明了在將B+樹改進(jìn)后，B+樹的搜索優(yōu)化效果較好。

4 結(jié)論

通過分析原生B+樹的基本特點(diǎn)，提出了一種MySQL索引改進(jìn)的B+樹，通過將B+樹葉子節(jié)點(diǎn)的單向鏈表變?yōu)殡p向鏈表來提升B+樹在對(duì)范圍數(shù)據(jù)進(jìn)行查找的效率。改進(jìn)后的B+樹在對(duì)范圍數(shù)據(jù)進(jìn)行查找時(shí)帶來了極高的效率，無論是從I/O次數(shù)還是時(shí)間消耗上來看都得到了極大的提升，這些提升對(duì)于數(shù)據(jù)存儲(chǔ)量極大的MySQL數(shù)據(jù)庫(kù)而言有現(xiàn)實(shí)意義。

參考文獻(xiàn)：

[1] 侯金彪.一種基于Jsp和MySQL的外賣系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].安順學(xué)院學(xué)報(bào)，2021，23（3）：129-136.

[2] 朱寶善，陳光浦，李鵬程，等.基于B/S模式和MySQL的人力資源管理系統(tǒng)設(shè)計(jì)[J].現(xiàn)代電子技術(shù)，2021，44（14）：65-69.

[3] 宋永鵬.基于MySQL的數(shù)據(jù)庫(kù)查詢性能優(yōu)化[J].電子設(shè)計(jì)工程，2021，29（12）：43-47.

[4] 豆利.基于MySQL的查詢優(yōu)化技術(shù)[J].電腦知識(shí)與技術(shù)，2021，17（15）：35-36.

[5] 石怡.基于MySQL數(shù)據(jù)庫(kù)的查詢性能優(yōu)化研究[J].四川職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2021，31（1）：164-168.

[6] 王瀾.內(nèi)存數(shù)據(jù)庫(kù)中B+樹和CSB+樹的性能比較[J].通訊世界，2015（12）：277.

[7] 施恩，顧大權(quán)，馮徑，等.B+樹索引機(jī)制的研究及優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究，2017，34（6）：1766-1769.

[8] 時(shí)亞南.B+樹算法的Java實(shí)現(xiàn)方法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015，25（1）：111-114.

【通聯(lián)編輯：王力】