林榮杭 劉小英

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

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

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

文章編號：1009-3044（2022）16-0012-02

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

1 傳統(tǒng)B+樹

1.1 B+樹的特征

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

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

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

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

2.1改進(jìn)思路

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

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

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

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

輸入：第一個滿足小于搜索值（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)部是個數(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)移動到最右邊的葉子節(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+樹的搜索小于某個值的流程為：

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

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

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

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

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

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

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

為了驗(yàn)證改進(jìn)后的B+樹在MySQL中搜索效率的提升，本文選擇Java為編程語言，在Eclipse上分別對改進(jìn)前后的B+樹進(jìn)行了構(gòu)建，并通過兩者的I/O次數(shù)和查找用時來探討改進(jìn)后的B+樹在數(shù)據(jù)查找方面的優(yōu)勢。在實(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)是一個單向鏈表，無法滿足對數(shù)據(jù)的雙向搜索，所以會產(chǎn)生更多的I/O次數(shù)，當(dāng)數(shù)據(jù)達(dá)到105級別時會出現(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ù)的增加，其搜索時間也突然增加，但是改進(jìn)后的B+樹并不會出現(xiàn)這種現(xiàn)象，這也增加了搜索的穩(wěn)定性，不會出現(xiàn)突然間的時間增大。在數(shù)據(jù)逐漸增大的過程中MySQL使用改進(jìn)后的B+樹時所帶來的時間消耗并不會出現(xiàn)突然性的增加，而是一個平緩的過程，這證明了在將B+樹改進(jìn)后，B+樹的搜索優(yōu)化效果較好。

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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