mb-树索引下的查询算法分析word论文.docxVIP

MB-树索引下的查询算法研究摘要近几年来，对空间数据库的查询算法研究受关注程度越来越高，最近邻、反向最近邻、连续最近邻、方向查询等都是热门的研究对象。一直以来，对于这些算法都是用R-树、R*-树、R+-树等无序关系的存储结构来做研究。这使得查询时会访问更多的数据节点，致使磁盘的I/O增加。本文运用具有一定序关系的MB-树作为存储结构进行反最近邻查询和方向查询的算法研究。本文对MB-树索引结构的数据更新、MB-树索引结构的反最近邻查询问题以及方向查询问题进行了深入细致的研究。取得了如下的结果：首先，给出MB-树的数据更新算法，包括数据插入和数据删除算法。给出了数据更新时节点上溢和下溢情况的处理方法。其次，详细分析了反最近邻查询时查询点与MBR 的位置关系的判断方法，给出了相应情况的判别定理，依据这些定理提出了反最近邻查询的剪枝规则，从而建立了反最近邻查询的算法，并给出了查询算法的正确性、可终止性证明，同时给出了算法的时间复杂度的分析。再次，详细分析了方向查询时查询点与MBR 的位置关系的判断方法，给出了相应情况的判别定理，依据这些定理提出了方向查询的剪枝规则，从而建立了方向查询的算法，并给出了查询算法的正确性、可终止性证明，同时给出了算法的时间复杂度的分析。最后，给出了方向查询算法的实验分析，通过实验对比表明了新算法的高效性。关键词MB-树；剪枝规则；反最近邻查询；方向查询Research on QueryAlgorithm Based on MB-Tree AbstractInrecentyears,researchonqueryalgorithmofthespatialdatabaseismoreand moreattentive.Nearestneighborquery,reversenearestneighborquery,continuous nearestneighborquery,directionqueryarethemostfashionableobjectsof investigation.Allthetime, R-tree, R*-tree, R+-treestoragestructureswithoutorder relationshavebeenstudied.Thequerieswillaccessmoredatanodes,whichresulted inincreasingthenumberofdiskI/O.ThispaperusesMB-treethathasanorder relationasthestoragestructure toresearchthereverse nearestneighborquery algorithm and thedirection queryalgorithm.MB-treeupdating,reversenearestneighborqueryanddirectionalquerybases onMB-treewereresearcheddeeplyanddetailedly.Thefollowingresultswere achieved.Firstly,theupdatealgorithmofMB-treewasgiven,includinginsertion algorithmanddeletionalgorithm.Thedealingmethodsweregivenforthecasesof overflow andlowflow.Secondly,thedetailedanalysisforthepositionbetweenthequerypointand MBRwasdonewhenreverse nearestneighborqueryisprocessed.Basedonthis,the correspondingtheoremsfordifferentcasesweregiven.Accordingthem,thepruning rulesforreversenearestneighborqueryweresetupsothatthereversenearest neighborquerybasedonMB-treewasproposed.ThenThealgorithm’scorrectness and finitness wereproved.And the algorithm’s time complexitywasgiven.Thirdly,the detailedanalysis for the position between thequerypoint andMBR wasdonewhendirectionalque