基于MB+樹的數(shù)據(jù)庫查詢算法優(yōu)化

范會(huì)芳

摘要：當(dāng)今社會(huì)人們工作、生活中大數(shù)據(jù)被廣泛應(yīng)用。在運(yùn)行數(shù)據(jù)庫過程中，操作頻率最高的是查詢操作。對(duì)基于MB+樹的數(shù)據(jù)庫查詢算法進(jìn)行優(yōu)化，通過構(gòu)建MB+樹型、MB+查詢算法以及插入算法，實(shí)現(xiàn)數(shù)據(jù)查詢算法的優(yōu)化構(gòu)建。為驗(yàn)證優(yōu)化后算法的最優(yōu)性，分別以傳統(tǒng)的基于R樹的數(shù)據(jù)庫查詢算法、Merkle散列樹查詢算法為對(duì)照組，驗(yàn)證MB+樹算法的查詢效率和查詢消耗。結(jié)果表明：優(yōu)化后的MB+樹數(shù)據(jù)庫查詢算法，查詢效率明顯優(yōu)于傳統(tǒng)算法，查詢消耗少于傳統(tǒng)算法。

關(guān)鍵詞：MB+樹;數(shù)據(jù)庫;查詢算法;優(yōu)化

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

文章編號(hào)：1009-3044（2019）19-0011-03

MB樹是一種基于貝葉斯網(wǎng)絡(luò)的、結(jié)合Merkle的散列概念[1-2]。數(shù)據(jù)庫系統(tǒng)查詢結(jié)構(gòu)適合采用B+樹，結(jié)構(gòu)寬而淺的樹型，其對(duì)大型數(shù)據(jù)庫的索引具有出色表現(xiàn)。是一種適用于組織動(dòng)態(tài)的、平衡的多分樹索引結(jié)構(gòu)。常規(guī)的數(shù)據(jù)庫管理系統(tǒng)之中，廣泛應(yīng)用B樹及其變形。MB+樹在每一個(gè)節(jié)點(diǎn)結(jié)構(gòu)中增加散列值項(xiàng)，以貝葉斯網(wǎng)絡(luò)作為概率圖模型解決存儲(chǔ)和查詢問題，合并當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)散列值，進(jìn)行儲(chǔ)存，以便于為后續(xù)的查詢和檢驗(yàn)提供輔助信息。MB+樹也是一種特殊的R樹，具有R樹基特性，為減少I/O代價(jià)，需要在訪問中間節(jié)點(diǎn)時(shí)，根據(jù)MB+樹的序關(guān)系，進(jìn)行大量的剪枝，簡化查詢算法步驟，減少訪問節(jié)點(diǎn)數(shù)。

1 基于MB+樹的數(shù)據(jù)庫查詢算法優(yōu)化

1.1 構(gòu)建MB+樹樹型

本文采用與構(gòu)造常規(guī)樹型數(shù)據(jù)結(jié)構(gòu)相同的方式，來構(gòu)建MB+樹。在建構(gòu)一個(gè)值為null的MB+樹樹根節(jié)點(diǎn)的基礎(chǔ)上，將數(shù)據(jù)文件塊的檢索鍵和指針逐一向?qū)?yīng)的null節(jié)點(diǎn)結(jié)構(gòu)中加入。進(jìn)行分裂操作，調(diào)整各個(gè)節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)數(shù)，要符合當(dāng)前節(jié)點(diǎn)中數(shù)據(jù)項(xiàng)小于等于節(jié)點(diǎn)階的要求，以此確保新MB+樹有效[3]。

MB+樹的查找效率明顯和查找樹中任意記錄所需的平均節(jié)點(diǎn)數(shù)有關(guān)系。假定MB+樹的節(jié)點(diǎn)中已包含n個(gè)檢索鍵。新的檢索鍵和指針項(xiàng)加入后，會(huì)使節(jié)點(diǎn)內(nèi)的數(shù)據(jù)項(xiàng)數(shù)目增加，節(jié)點(diǎn)內(nèi)的數(shù)據(jù)項(xiàng)數(shù)將大于n，需要對(duì)節(jié)點(diǎn)進(jìn)行分裂，保持構(gòu)建MB+樹的有效性。

1.2 MB+樹節(jié)點(diǎn)插入

節(jié)點(diǎn)插入算法從根節(jié)點(diǎn)逐層向下搜索應(yīng)插入的節(jié)點(diǎn)位置，到找到葉子節(jié)點(diǎn)位置為止。利用MB+樹中間節(jié)點(diǎn)幾何位置的有序性，在每層搜索中，可快速定位應(yīng)出入的節(jié)點(diǎn)[4]。查詢算法程序的數(shù)據(jù)插入，第一步查詢此數(shù)據(jù)是否在MB+樹中，若數(shù)據(jù)存在，找到其在MB+樹中的對(duì)應(yīng)位置，將數(shù)據(jù)插入;若數(shù)據(jù)不存在，就會(huì)有可能導(dǎo)致節(jié)點(diǎn)分裂。應(yīng)先找到數(shù)據(jù)點(diǎn)位置，插入算法之前，查看該位置是否空。如果數(shù)據(jù)點(diǎn)位置為空，可調(diào)整指針，直接插入數(shù)據(jù)點(diǎn)。為了在插入數(shù)據(jù)后，仍具有 MB+樹的特征，重新生成子樹。調(diào)整會(huì)改變MB+樹的有序性，為保證MB+樹自身有序性不變化，記錄調(diào)整結(jié)束時(shí)節(jié)點(diǎn)層數(shù)。調(diào)整結(jié)束后排序方式發(fā)生改變，需要按照記錄的層數(shù)的排序方式，重新生成子樹，使得最后得到的整個(gè)樹都具有MB+樹的特性。

存儲(chǔ)數(shù)據(jù)項(xiàng)和索引項(xiàng)時(shí)還要知道該節(jié)點(diǎn)是否滿。已滿的數(shù)據(jù)節(jié)點(diǎn)無法進(jìn)行運(yùn)算及存儲(chǔ)，不能用節(jié)點(diǎn)中索引項(xiàng)數(shù)量衡量已占用空間[5]。因此，在本文優(yōu)化的算法中，采用 [Pd]- [Pi]來表示節(jié)點(diǎn)中剩余空間。根據(jù)（1）、（2）對(duì)數(shù)據(jù)庫內(nèi)數(shù)據(jù)進(jìn)行優(yōu)化查詢。

[Y′=Y-Y/T]? ? ? ? ? ? ? ? ? ? ? ? ? （1）

[T=jPYj-Y2p-1]? ? ? ? ? ? ? ? ? ? ? ?（2）

其中，p為數(shù)據(jù)項(xiàng)和索引項(xiàng)的總和，T為設(shè)定查找周期，Y為數(shù)據(jù)庫內(nèi)部數(shù)據(jù)。

如果查找出的數(shù)據(jù)不是所需要的，要根據(jù)記錄搜索順序文件的搜索碼鏈表。快速定位記錄位置，保證較高的存儲(chǔ)效率，減少節(jié)點(diǎn)的插入和刪除的開銷維護(hù)。

1.3 MB+樹查詢流程優(yōu)化

基于MB+樹的數(shù)據(jù)庫數(shù)據(jù)查詢，應(yīng)快速檢索并得到數(shù)據(jù)文件塊的基本信息的能力。本文采用的MB+樹是基于Merkle散列樹，發(fā)展起來的數(shù)據(jù)查詢流程。根據(jù)二路分支的原則，沿二叉樹的左右分支向下進(jìn)行遍歷查找。執(zhí)行查詢操作，如果需要隨機(jī)查找，找到所要求的記錄需要通過索引樹。從root節(jié)點(diǎn)起始找起，通過順序集找到記錄。通過索引樹或從順序集的鏈頭得到的，某一順序節(jié)點(diǎn)開始找起。中間節(jié)點(diǎn)中的指針，根據(jù)節(jié)點(diǎn)結(jié)構(gòu)，指向下一層的某一塊數(shù)據(jù)。除了指向具體記錄，這一層最右側(cè)指針還指向下一個(gè)葉子節(jié)點(diǎn)。由當(dāng)前節(jié)點(diǎn)的出度決定，根據(jù)MB+樹的定義，基于MB+樹的數(shù)據(jù)查詢流程，需進(jìn)行遍歷查找，按照z路分支原則，完成查詢流程 [6]。引入枝葉比[Rbl]的概念，用來描述葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)的數(shù)量關(guān)系。

[Rbl=RbRl]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

[Rb]為非葉子節(jié)點(diǎn)最大關(guān)鍵字?jǐn)?shù)目，[Rl]為葉子節(jié)點(diǎn)最大關(guān)鍵字?jǐn)?shù)目。

假定需要查找檢索鍵為K的數(shù)據(jù)文件塊，z路分支的遍歷查找過程由以下三個(gè)步驟組成：

第一步，判斷ROOT中包含的各個(gè)檢索鍵與待索檢的K之間的大小關(guān)系。從MB+樹的根節(jié)點(diǎn)ROOT開始，如果ROOT中，包含有[Ki>K]，即ROOT中所有大于K的最小檢索鍵，且[Ki]是ROOT中所有的檢索鍵，查找路徑會(huì)轉(zhuǎn)向與[Ki]對(duì)應(yīng)指向[Pi]的子樹，查找過程將在該子樹的根節(jié)點(diǎn)上繼續(xù)進(jìn)行。如果ROOT中不包含所有的檢索鍵[Ki]，表明[Ki]大于ROOT中包含的所有檢索鍵。根據(jù)MB+樹型結(jié)構(gòu)定義，遍歷查找過程將在該子樹的根節(jié)點(diǎn)上繼續(xù)進(jìn)行。

在[Pod]或者幾指向的子樹根節(jié)點(diǎn)上繼續(xù)第一步驟的遍歷查找過程，并根據(jù)實(shí)際情況繼續(xù)向MB+樹的葉節(jié)點(diǎn)進(jìn)行延伸[7]。

MB+算法查詢失效總代價(jià)[FsL]如下，

關(guān)鍵字?jǐn)?shù)目[Ki]，葉節(jié)點(diǎn)[pi]，f為約束條件，m為設(shè)定參數(shù)。如果查詢過程已經(jīng)延伸到葉節(jié)點(diǎn)，若葉節(jié)點(diǎn)中包含[Ki]=[K]，說明與[K]對(duì)應(yīng)的數(shù)據(jù)文件塊存在;若葉節(jié)點(diǎn)中的所有[Ki]≠[K]，說明樹型結(jié)構(gòu)中不存在被查詢的數(shù)據(jù)文件塊。本文優(yōu)化的MB+樹查詢算法的程序（部分）如下，

設(shè)不能立即確定某個(gè)記錄在MB+樹中找到，則需繼續(xù)在數(shù)據(jù)塊中查找。本次優(yōu)化算法查找可分為順序查找和插入查找，MB+樹中順序查找，是按照從鏈頭開始，順著整個(gè)數(shù)據(jù)鏈，對(duì)數(shù)據(jù)庫文件順序處理;如果是要求從某一節(jié)點(diǎn)或者樹根開始，則需要從對(duì)應(yīng)的某個(gè)記錄層起始。就是使用隨機(jī)的查找方法，從中間節(jié)點(diǎn)或者樹根開始，查找到要求的數(shù)據(jù)記錄。再按照順序查找的方法，從這一記錄開始順序查找其它記錄。如果在算法中，為插入的節(jié)點(diǎn)尋找插入地址，運(yùn)用二分法在每一層節(jié)點(diǎn)找到插入的位置，保證在該節(jié)點(diǎn)插入后，該MB+樹仍保持原有有序性[8]。進(jìn)行窗口查詢時(shí)，在MB+樹上可以有效地進(jìn)行過濾，各中間節(jié)點(diǎn)中的child節(jié)點(diǎn)按其順序排列就是其關(guān)鍵之處。正是因?yàn)橛行蛐允沟没贛B+這種結(jié)構(gòu)的查詢速度很快。

2 實(shí)驗(yàn)

2.1 驗(yàn)證MB+樹節(jié)點(diǎn)訪問效率

實(shí)驗(yàn)是在Windows 8 系統(tǒng)， Inter i7中央處理處理器 4GHz，8GB RAM硬件平臺(tái)上，用c++ 程序語言實(shí)現(xiàn)的，由計(jì)算機(jī)隨機(jī)產(chǎn)生實(shí)驗(yàn)數(shù)據(jù)。以傳統(tǒng)R樹為基礎(chǔ)的數(shù)據(jù)庫查詢算法為對(duì)照組，優(yōu)化的MB+算法為實(shí)驗(yàn)組。隨機(jī)產(chǎn)生數(shù)據(jù)，生成 MB+樹中 M= 20， P1（10，30），P2（40，110），方向查詢向量（1，0.5）。通過計(jì)算機(jī)隨機(jī)產(chǎn)生實(shí)驗(yàn)數(shù)據(jù)，該算法訪問對(duì)應(yīng)的數(shù)據(jù)時(shí)，統(tǒng)計(jì)經(jīng)過的節(jié)點(diǎn)數(shù)而得到實(shí)驗(yàn)結(jié)果， MB+樹的中間隔值參數(shù)為 50。由上文優(yōu)化流程可知，即使每次訪問的數(shù)據(jù)相同，但是根據(jù)MB+樹本身特性可知，由于數(shù)據(jù)儲(chǔ)存的不同分布，會(huì)使得訪問節(jié)點(diǎn)數(shù)也不同。下表數(shù)值為進(jìn)行十次實(shí)驗(yàn)后計(jì)算的平均值。

2.2 MB+樹查詢消耗比較

從節(jié)點(diǎn)的查詢檢驗(yàn)時(shí)間來考察，本文基于MB+樹的數(shù)據(jù)庫查詢優(yōu)化算法為實(shí)驗(yàn)組，傳統(tǒng)的Merkle散列樹查詢算法為對(duì)照組，計(jì)算機(jī)隨機(jī)生成數(shù)據(jù)組，對(duì)節(jié)點(diǎn)查詢時(shí)間進(jìn)行比較。結(jié)果如下圖所示：

實(shí)驗(yàn)組和對(duì)照組兩種不同算法的節(jié)點(diǎn)查詢時(shí)間都在隨數(shù)據(jù)項(xiàng)增加而減少，并且下減幅度都逐漸趨于穩(wěn)定但是基于MB+樹的查詢算法消耗明顯少于基于Merkle散列樹的查詢算法。

3 結(jié)語

大數(shù)據(jù)的發(fā)展將不同產(chǎn)業(yè)、領(lǐng)域、行業(yè)的信息整合到一起，構(gòu)成完整數(shù)據(jù)庫?；ヂ?lián)網(wǎng)的不斷發(fā)展，對(duì)數(shù)據(jù)庫的查詢算法的要求越來越高?？焖?、準(zhǔn)確、消耗小的查詢算法是未來的發(fā)展趨勢(shì)。本次優(yōu)化的基于MB+樹的數(shù)據(jù)庫查詢算法，從查詢節(jié)點(diǎn)、查詢消耗等方面，相比傳統(tǒng)算法有所提升。而且優(yōu)化后的算法無論在理論步驟簡化的層面上，還是對(duì)比實(shí)驗(yàn)的效果上都要優(yōu)于之前的數(shù)據(jù)庫查詢算法，可以進(jìn)行推廣。

參考文獻(xiàn)：

[1] 李凌， 張蕾， 楊洋，等. 一種基于MB+樹的網(wǎng)絡(luò)共享數(shù)據(jù)查詢和檢驗(yàn)方法[J]. 計(jì)算機(jī)應(yīng)用研究， 2018， 35（3）： 782-787.

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

[3] 高潔. 基于改進(jìn)和聲搜索群算法的數(shù)據(jù)庫查詢優(yōu)化[J]. 現(xiàn)代電子技術(shù)， 2017， 40（3）： 114-116.

[4] 鄧小鴻， 劉惠文. 基于四叉樹分解和MB_LBP模式的人臉識(shí)別算法[J]. 電視技術(shù)， 2017（Z3）.

[5] 丁建立， 羅云生， 王家亮，等. 基于B+樹的發(fā)布/訂閱并行匹配算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2018（1）： 66-71.

[6] 陳晉音， 施晉， 杜文耀，等. 基于MB-RRT～*的無人機(jī)航跡規(guī)劃算法研究[J]. 計(jì)算機(jī)科學(xué)， 2017， 44（8）： 198-206.

[7] 王科俊， 曹逸， 邢向磊. 基于MB-CSLBP的指靜脈加密算法研究[J]. 智能系統(tǒng)學(xué)報(bào)， 2018 （4）： 55-61.

[8] 岑瑤， 潘新， 郜曉晶，等. 基于MB-LBP和HOG的掌紋識(shí)別[J]. 計(jì)算機(jī)應(yīng)用研究， 2017， 34（3）： 920-923.

【通聯(lián)編輯：張薇】