范會芳

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

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

中圖分類號：TP312? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）19-0011-03

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

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

1.1 構建MB+樹樹型

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

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

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

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

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

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

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

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

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

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

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

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

[Rb]為非葉子節(jié)點最大關鍵字數(shù)目，[Rl]為葉子節(jié)點最大關鍵字數(shù)目。

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

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

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

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

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

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

2 實驗

2.1 驗證MB+樹節(jié)點訪問效率

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

2.2 MB+樹查詢消耗比較

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

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

3 結語

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

參考文獻：

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

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

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

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

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

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

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

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

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