基于MB+树的数据库查询算法优化

范会芳

摘要：当今社会人们工作、生活中大数据被广泛应用。在运行数据库过程中，操作频率最高的是查询操作。对基于MB+树的数据库查询算法进行优化，通过构建MB+树型、MB+查询算法以及插入算法，实现数据查询算法的优化构建。为验证优化后算法的最优性，分别以传统的基于R树的数据库查询算法、Merkle散列树查询算法为对照组，验证MB+树算法的查询效率和查询消耗。结果表明：优化后的MB+树数据库查询算法，查询效率明显优于传统算法，查询消耗少于传统算法。

关键词：MB+树;数据库;查询算法;优化

中图分类号：TP312      文献标识码：A

文章编号：1009-3044（2019）19-0011-03

MB树是一种基于贝叶斯网络的、结合Merkle的散列概念[1-2]。数据库系统查询结构适合采用B+树，结构宽而浅的树型，其对大型数据库的索引具有出色表现。是一种适用于组织动态的、平衡的多分树索引结构。常规的数据库管理系统之中，广泛应用B树及其变形。MB+树在每一个节点结构中增加散列值项，以贝叶斯网络作为概率图模型解决存储和查询问题，合并当前节点的所有子节点散列值，进行储存，以便于为后续的查询和检验提供辅助信息。MB+树也是一种特殊的R树，具有R树基特性，为减少I/O代价，需要在访问中间节点时，根据MB+树的序关系，进行大量的剪枝，简化查询算法步骤，减少访问节点数。

1 基于MB+树的数据库查询算法优化

1.1 构建MB+树树型

本文采用与构造常规树型数据结构相同的方式，来构建MB+树。在建构一个值为null的MB+树树根节点的基础上，将数据文件块的检索键和指针逐一向对应的null节点结构中加入。进行分裂操作，调整各个节点的数据项数，要符合当前节点中数据项小于等于节点阶的要求，以此确保新MB+树有效[3]。

MB+树的查找效率明显和查找树中任意记录所需的平均节点数有关系。假定MB+树的节点中已包含n个检索键。新的检索键和指针项加入后，会使节点内的数据项数目增加，节点内的数据项数将大于n，需要对节点进行分裂，保持构建MB+树的有效性。

1.2 MB+树节点插入

节点插入算法从根节点逐层向下搜索应插入的节点位置，到找到叶子节点位置为止。利用MB+树中间节点几何位置的有序性，在每层搜索中，可快速定位应出入的节点[4]。查询算法程序的数据插入，第一步查询此数据是否在MB+树中，若数据存在，找到其在MB+树中的对应位置，将数据插入;若数据不存在，就会有可能导致节点分裂。应先找到数据点位置，插入算法之前，查看该位置是否空。如果数据点位置为空，可调整指针，直接插入数据点。为了在插入数据后，仍具有 MB+树的特征，重新生成子树。调整会改变MB+树的有序性，为保证MB+树自身有序性不变化，记录调整结束时节点层数。调整结束后排序方式发生改变，需要按照记录的层数的排序方式，重新生成子树，使得最后得到的整个树都具有MB+树的特性。

存储数据项和索引项时还要知道该节点是否满。已满的数据节点无法进行运算及存储，不能用节点中索引项数量衡量已占用空间[5]。因此，在本文优化的算法中，采用 [Pd]- [Pi]来表示节点中剩余空间。根据（1）、（2）对数据库内数据进行优化查询。

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

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

其中，p为数据项和索引项的总和，T为设定查找周期，Y为数据库内部数据。

如果查找出的数据不是所需要的，要根据记录搜索顺序文件的搜索码链表。快速定位记录位置，保证较高的存储效率，减少节点的插入和删除的开销维护。

1.3 MB+树查询流程优化

基于MB+树的数据库数据查询，应快速检索并得到数据文件块的基本信息的能力。本文采用的MB+树是基于Merkle散列树，发展起来的数据查询流程。根据二路分支的原则，沿二叉树的左右分支向下进行遍历查找。执行查询操作，如果需要随机查找，找到所要求的记录需要通过索引树。从root节点起始找起，通过顺序集找到记录。通过索引树或从顺序集的链头得到的，某一顺序节点开始找起。中间节点中的指针，根据节点结构，指向下一层的某一块数据。除了指向具体记录，这一层最右侧指针还指向下一个叶子节点。由当前节点的出度决定，根据MB+树的定义，基于MB+树的数据查询流程，需进行遍历查找，按照z路分支原则，完成查询流程 [6]。引入枝叶比[Rbl]的概念，用来描述叶子节点和非叶子节点的数量关系。

[Rbl=RbRl]                               （3）

[Rb]為非叶子节点最大关键字数目，[Rl]为叶子节点最大关键字数目。

假定需要查找检索键为K的数据文件块，z路分支的遍历查找过程由以下三个步骤组成：

第一步，判断ROOT中包含的各个检索键与待索检的K之间的大小关系。从MB+树的根节点ROOT开始，如果ROOT中，包含有[Ki>K]，即ROOT中所有大于K的最小检索键，且[Ki]是ROOT中所有的检索键，查找路径会转向与[Ki]对应指向[Pi]的子树，查找过程将在该子树的根节点上继续进行。如果ROOT中不包含所有的检索键[Ki]，表明[Ki]大于ROOT中包含的所有检索键。根据MB+树型结构定义，遍历查找过程将在该子树的根节点上继续进行。

在[Pod]或者几指向的子树根节点上继续第一步骤的遍历查找过程，并根据实际情况继续向MB+树的叶节点进行延伸[7]。

MB+算法查询失效总代价[FsL]如下，

关键字数目[Ki]，叶节点[pi]，f为约束条件，m为设定参数。如果查询过程已经延伸到叶节点，若叶节点中包含[Ki]=[K]，说明与[K]对应的数据文件块存在;若叶节点中的所有[Ki]≠[K]，说明树型结构中不存在被查询的数据文件块。本文优化的MB+树查询算法的程序（部分）如下，

设不能立即确定某个记录在MB+树中找到，则需继续在数据块中查找。本次优化算法查找可分为顺序查找和插入查找，MB+树中顺序查找，是按照从链头开始，顺着整个数据链，对数据库文件顺序处理;如果是要求从某一节点或者树根开始，则需要从对應的某个记录层起始。就是使用随机的查找方法，从中间节点或者树根开始，查找到要求的数据记录。再按照顺序查找的方法，从这一记录开始顺序查找其它记录。如果在算法中，为插入的节点寻找插入地址，运用二分法在每一层节点找到插入的位置，保证在该节点插入后，该MB+树仍保持原有有序性[8]。进行窗口查询时，在MB+树上可以有效地进行过滤，各中间节点中的child节点按其顺序排列就是其关键之处。正是因为有序性使得基于MB+这种结构的查询速度很快。

2 实验

2.1 验证MB+树节点访问效率

实验是在Windows 8 系统， Inter i7中央处理处理器 4GHz，8GB RAM硬件平台上，用c++ 程序语言实现的，由计算机随机产生实验数据。以传统R树为基础的数据库查询算法为对照组，优化的MB+算法为实验组。随机产生数据，生成 MB+树中 M= 20， P1（10，30），P2（40，110），方向查询向量（1，0.5）。通过计算机随机产生实验数据，该算法访问对应的数据时，统计经过的节点数而得到实验结果， MB+树的中间隔值参数为 50。由上文优化流程可知，即使每次访问的数据相同，但是根据MB+树本身特性可知，由于数据储存的不同分布，会使得访问节点数也不同。下表数值为进行十次实验后计算的平均值。

2.2 MB+树查询消耗比较

从节点的查询检验时间来考察，本文基于MB+树的数据库查询优化算法为实验组，传统的Merkle散列树查询算法为对照组，计算机随机生成数据组，对节点查询时间进行比较。结果如下图所示：

实验组和对照组两种不同算法的节点查询时间都在随数据项增加而减少，并且下减幅度都逐渐趋于稳定但是基于MB+树的查询算法消耗明显少于基于Merkle散列树的查询算法。

3 结语

大数据的发展将不同产业、领域、行业的信息整合到一起，构成完整数据库。互联网的不断发展，对数据库的查询算法的要求越来越高。快速、准确、消耗小的查询算法是未来的发展趋势。本次优化的基于MB+树的数据库查询算法，从查询节点、查询消耗等方面，相比传统算法有所提升。而且优化后的算法无论在理论步骤简化的层面上，还是对比实验的效果上都要优于之前的数据库查询算法，可以进行推广。

参考文献：

[1] 李凌， 张蕾， 杨洋，等. 一种基于MB+树的网络共享数据查询和检验方法[J]. 计算机应用研究， 2018， 35（3）： 782-787.

[2] 施恩， 顾大权， 冯径等. B+树索引机制的研究及优化[J]. 计算机应用研究， 2017， 34（6）： 1766-1769.

[3] 高洁. 基于改进和声搜索群算法的数据库查询优化[J]. 现代电子技术， 2017， 40（3）： 114-116.

[4] 邓小鸿， 刘惠文. 基于四叉树分解和MB_LBP模式的人脸识别算法[J]. 电视技术， 2017（Z3）.

[5] 丁建立， 罗云生， 王家亮，等. 基于B+树的发布/订阅并行匹配算法[J]. 计算机工程与设计， 2018（1）： 66-71.

[6] 陈晋音， 施晋， 杜文耀，等. 基于MB-RRT～*的无人机航迹规划算法研究[J]. 计算机科学， 2017， 44（8）： 198-206.

[7] 王科俊， 曹逸， 邢向磊. 基于MB-CSLBP的指静脉加密算法研究[J]. 智能系统学报， 2018 （4）： 55-61.

[8] 岑瑶， 潘新， 郜晓晶，等. 基于MB-LBP和HOG的掌纹识别[J]. 计算机应用研究， 2017， 34（3）： 920-923.

【通联编辑：张薇】