R树和四叉树的空间索引结构“RQOP”树

《R树和四叉树的空间索引结构“RQOP”树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第42卷第2期哈尔滨工业大学学报Vol.42No.22010年2月JOURNALOFHARBININSTITUTEOFTECHNOLOGYFeb.2010R－树和四叉树的空间索引结构:RQOP树－11，2刘润涛，郝忠孝(1.哈尔滨理工大学计算机科学与技术学院，哈尔滨150080，liurt@hrbust.edu.cn;2.哈尔滨工业大学计算机科学与技术学院，哈尔滨150001)摘要:针对现有的基于R－树和四叉树的空间索引结构中存在的问题，通过建立数据矩形间的序关系对数据空间进行分割，提出了一种新的空间数据索引结构:RQOP树.在此结

2、构中，节点的构造是按照空间数据的分布来进行的而不是像其它基于R－树和四叉树的空间索引结构只是对数据空间进行均匀划分而得到，使树的高度尽可能低，同时使兄弟节点间的交叠相对较小.在区域查询算法中引入了查询窗口包含节点MBR的判断加快了查询的速度.给出了RQOP树的生成、节点插入和区域查询算法，并给出了相应算法的可行性和正确性定理及时间复杂度分析.实验表明:新索引结构的查询速度明显加快.关键词:空间数据;索引结构;RQOP树;区域查询中图分类号:TP311文献标志码:A文章编号:0367－6234(2010)02－0323－05Spati

3、alindexstructurebasedonR-treeandquadtree:RQOP－tree11，2LIURun-tao，HAOZhong-xiao(1.CollegeofComputerScienceandTechnology，HarbinUniversityofScienceandTechnology，Harbin150080，China，liurt@hrbust.edu.cn;2.SchoolofComputerScienceandTechnology，HarbinInstituteofandTechnology，Ha

4、rbin150001，China)Abstract:Anewindexstructureforspatialdata，RQOP－tree，isproposedbysettinguptheorderrelationbe-tweendatarectanglestopartitionthedataspaces，aimedattheexistingproblemsincurrentindexstructuresbasedonR-treeandquadtree.Inthisstructure，themiddlenodesareconstruc

5、tedaccordingtothedistributionofspatialdatainsteadofpartitioningthedataspaceevenly，thereforetheheightofthetreeisguaranteedaslowaspossibleandacomparativelysmalloverlapbetweenbrothernodescanbekept.Intherangequeryalgo-rithm，thecheckofquerywindowcontaininganode’sMBRisintrod

6、ucedtospeedupthequeryeffectivelyforacomparativelylargequerywindow.Thealgorithmforconstructingtheindexstructureisgiven，anditstimecomplexityaswellasitscorrectnessispresented.Thealgorithmsfornodeinsertionandrangequeryareob-tained.Theexperimentshowsthatthequeryspeedisincre

7、asedgreatly.Keywords:spatialdata;indexstructure;RQOP_tree;rangequery空间数据索引技术是提高空间数据库查询性四叉树，用于索引空间矩形数据的CIF－四叉［1］［2－3］*［4］［5－6］能的关键技术，直接影响到空间数据库系统的性树、QR－树，QR－树和PMR树.能.四叉树是一种层次结构，其结构清晰、易于实然而，这些索引结构在生成相应的索引结构时采现，广泛用于很多领域.在空间数据库中，将四叉用的是对数据空间进行四等分的分割或采用超节树与R－树结合得到的空间数据索引结构将用

8、于点策略.因此，当数据分布非均匀时，所产生的相索引空间数据点的点四叉树、MX－四叉树、PR－应的空间索引四叉树将会是严重不平衡的，即，树的高度将会变得很高，会严重地影响查询的速度.收稿日期:2008－05－29.本文针对这一问题，结合