并行R树空间索引中叶节点大小的确定方法研究

并行R树空间索引中叶节点大小的确定方法研究 第33卷第4期2008年7月测绘科学ScienceofSurveyingandMappingVol133No14Jul1作者简介:赵园春19782女助研主要从事地图学与地理信息系统研究。 E2mail:zhaoyccasm1ac1cn收稿日期:2007209212基金项目:科技部863项目2001AA136010并行R树空间索引中叶节点大小的确定方法研究赵园春??李成名?赵春宇??山东科技大学 地球信息科学与工程学院山东青岛 266510?中国测绘科学研究院北京 100039?武汉大学遥感信息与工程学院武汉 430079【摘 要】并行R树空间索引结构中叶节点的大小是影响索引效率的主要因素其确定方法是并行R树索引结构性能优劣的关键。本文讨论并设计了一种多层并行R树空间索引结构文中以系统的查询响应时间作为性能评估指标给出了并行R树叶节点大小的确定方法并通过实验验证了该方法的有效性和适用性同时也论证了本文所设计的多层并行R树索引结构是合理的和高效的。【关键词】并行空间索引并行R树空间索引并行GIS分布式并行计算环境【中图分类号】P208TP391 【文献标识码】A 【文章编号】 10092230720080420094204DOI:1013771/j1issn11009223071200810410321 引言海量空间数据的组织与管理技术是诸如空间数据挖掘、空间决策支持、空间多维动态可视化分析与模拟等各类复杂空间应用的基础也是GIS技术的核心问题。其中空间索引技术是数据组织与管理的重要研究内容。目前在数据库管理系统及GIS等科研领域空间索引技术的研究成果非常丰富应用较为广泛。然而针对海量空间数据的组织、管理、存取、处理与应用的分布式并行空间索引技术的研究成果较少已有的研究成果也由于其应用平台和应用领域的不同而各具优缺点。本文讨论并设计了一种分布式并行计算环境下的基于R树索引和线性链结构的多层并行R树空间索引结构并给出了该索引结构中叶节点大小的确定方法及其评估方法。文中给出的多层并行R树空间索引的设计与开发是以经典的IanFoster的并行计算方法论为依据充分考虑数据划分、负载平衡等影响并行索引机制效率的因素使得该索引结构更适合于网格等分布式并行计算环境中的各类复杂应用。2 并行空间索引机制概述并行计算理论和技术的应用无疑是解决传统GIS计算能力不足的重要途径。并行GIS实质上是并行计算理论和方法与GIS相结合的产物1。在并行GIS研究领域已有的研究成果中并未涉及太多的海量空间数据存储方面的问题。然而在分布式并行计算环境下海量空间数据的组织与管理将是关系到并行GIS整体性能优劣与否的关键。因此人们开始研究和探索并行化的空间索引以提高空间数据访问的效率其中针对R树并行化方法的研究成果较多2。Kamel和Faloutsos最早提出了并行R树索引方法其并行R树的硬件基础为单CPU多磁盘系统使用并发I/O方法提高查询的数据吞吐量。Schnitzer和Leutenegger提出了M2R树和MC2R树Master2clientR树的方法这两种方法的相同之处在于均是将R树的所有非叶节点存储在多机环境中的主计算机上3。两者的区别在于M2R树的叶节点和实体对象直接存储在子节点上而MC2R树的各个子节点存放的是一个子R树。以上三种并行R树结构均采用主从模式所以主节点很容易成为访问的热点和瓶颈这将增加事务处理的响应时间进而降低了系统的整体性能。R树空间索引结构具有固有的并行性特征4适合于并行GIS和并行空间数据库的应用但从目前已有的并行R树索引研究成果也不难发现R树在并行计算环境下应用时自身存在的缺点和不足:?R树中越靠近根节点的非叶节点被数据库事务访问的概率越大其成为热点的可能性越大?当R树的叶节点进行分裂或是合并时通常会影响该节点邻近的节 点最坏的情况下整棵R树都需要做相应调整?访问R树中的节点时通常需要在该节点上附加共享锁或排它锁如果对R树进行更新等操作那么被访问的节点将被锁住其他事务也不能对这棵R树进行任何操作从而降低了R树的事务并发处理能力。虽然R树存在着自身的弊端但实践证明经过优化设计其仍是构建并行空间索引的最佳选择。从对已有的并行R树索引机制的分析可以看出在分布式并行计算环境下并行R树的构建关键在于新创建的叶节点如何在多个磁盘间进行分配其原则包括:?数据平衡准则即理想状态下每个磁盘具有同等数量的叶节点同时需保证数据总量上的平衡?面积平衡准则即每个磁盘上存储的空间实体所覆盖的空间区域的面积保持平衡否则存储空间区域面积较大的磁盘很可能成为访问的热点和瓶颈?空间关系平衡准则即尽量将重叠或空间距离较近的叶节点分布到不同的磁盘进行存储以提高查询时的吞吐能力。3 并行R树空间索引机制311 空间数据划分策略在数据库领域数据划分技术是实现并行数据库系统中并行I/O操作的有效方法。同样空间数据划分技术在空间数据库中也发挥着重要的作用在避免产生数据倾斜的前提下可提高空间数据的并行查询与检索效率。空间数据划分策略是本文所提出的并行R树空间索引结构的基础同样也是保证该索引机制具有高效率与高性能的前提条件。为遵循前一小节的创建并行空间索引机制的原则并满足空间数据划分策略的需求本文将采用文献5中提出的空间划分策略即HCSDPSpatialDataPartitioningbasedonHilbertCurve算法该算法是一种基于Hilbert空间填充曲线的、适合于矢量空间数据的数据划分算法在充分考虑到空间信息的海量特征以及矢量数据存储记录的不定长等特点的前提下该算法可实现空间数据库中海量空间数据记录在多个存储设备上的均衡划分可避免出 第4期 赵园春等 并行R树空间索引中叶节点大小的确定方法研究现数据倾斜现象从而提高空间数据的检索与查询效率。312 并行R树空间索引结构设计前面所分析的已有的并行R树索引机制大部分采用了两层或多层的索引结构67。本文构造的并行R树空间索引结构是基于HCSDP空间数据划分算法的多层并行R树索引 HilbertSpace2FillingCurvebasedMulti2tiersParallelR2treeHCMPR2tree其突出特点是将空间数据划分策略同空间索引机制有机融合在保证得到较好的空间数据划分的前提下可以获得结构良好的空间索引。图1给出了HCM2PR2tree索引结构组成。图1 HCMPR2tree索引结构图1中并行R树索引结构的设计遵循IanFoster的并行算法设计方法论指导即经过划分、通信、聚集和映射四个步骤以使得并行R树索引结构更适合于并行计算环境下的应用。其各层的功能说明如下:1待划分空间区域层这一层包括所有的具有统一空间参考系统的空间实体对象和对应的属性数据的集合。该层使用Hilbert_Partition函数对整个待划分空间区域进行划分处理其输入为待划分的空间区域和划分的子区间个数输出结果为n个子区域。2子区域层该层是待划分空间区域经由HCSDP算法处理后的结果集层。每个子区域所拥有的空间实体对象均具有连续的Hilbert排列码这就避免了经由数据划分后空间实体对象彼此之间的空间关系被严重割裂情况的发生。3虚拟处理单元层虚拟处理单元VirtualProcessingElementVPE概念的引入有助于“聚集”操作的实现。该层中的虚拟处理单元的个数为m通常mltltn。VPE物理上是不存在的其将被映射到实际的处理单元上。实践证明影响R树索引性能的一个主要因素是节点之间的重叠度而产生重叠的重要因素之一是聚集后的空间实体对象之间彼此邻近即MBR之间重叠度较高。虚拟处理单元将为解决这一问题提 供较好的策略。4处理单元层该层对应实际的物理存储单元或处理单元ProcessingEle2mentPE即网络集群环境中的控制节点、计算节点和存储节点。该层实现了并行计算程序设计方法论中的第四步———映射即将虚拟处理单元映射到物理的处理单元上。VPE到PE的映射通常也可以使用轮循法或其他数据划分算法。5空间实体对象的物理存储层如图1所示通过一次划分、一次聚集和一次映射操作最终将所有的子区域分发存放到物理处理单元上。因为每个处理单元包含两个或两个以上的子区域而子区域所覆盖的空间范围彼此是分离的因此每个处理单元上R树的建立可以按照所包含的子区域进行分块处理从而加快R树索引的创建速度。就每个处理单元而言其上所建立的R树索引实质上就是一般的R树索引其空间数据访问方法和R树索引的插入与删除操作均与传统R树索引的处理方法相同而对集群环境中所有的处理单元来说所有的R树索引之间是彼此独立的可以实现空间数据的并行查询与更新。313 HCMPR2tree索引的物理存储结构本文提出的HCMPR2tree索引结构的叶节点包括一组项其格式为I元组标识符其中I为MBR元组标识符是数据库中存储对应于MBR的对象的元组惟一标识符。HCMPR2tree索引结构的非叶节点分为两类一类是子区域对应的非叶节点其由一组RIDI子节点指针表示RID用于标识子区域I为该节点对应的MBR即子区域对应的MBR子节点指针指向该子区域对应的R树的根节点另一类是子区域对应的R树内的非叶节点由I子节点指针表示I为MBR子节点指针指向下一层节点。每个处理单元上的R树的根节点由SIDI子节点指针表示SID标识该R树所在的处理单元的标识符I为该处理单元所覆盖的MBR子节点指针指向非叶节点。与前人提出的并行R树索引不同HCMPR2tree索引结构的最上层用链表保存链表中每一个元素包含五项RIDSIDIHSHE:RID用于标识子区域SID是存储该元素对应的子区域的处理单元的标识符I表示该元素对应的子区域的MBRHS表示该元素对应的Hilbert排列码值的起始值而HE表示其终止值。该链表保存于网络集群系统的主控制节点上。由于n的个数是有限的因此可一次性装入内存使其具有很快的查询速度。4 实验与分析如前所述HCMPR2tree索引结构的最下一层是对每个处理单元上的子区域建立的R树索引。而与传统R树索引不同的是HCMPR2tree索引的叶节点大小的确定将关系到并行计算环境中针对并行R树进行的空间数据查询与检索的效率问题。叶节点大小的确定一般分为两种情况:?如果叶节点的大小选择的过小例如只包含一个空间实体对象那么在进行较小的范围查询时可能必须访问多个处理单元这就增加了网络通信量从而会造成网络的阻塞?如果叶节点的大小选择的过大那么在进行较大的范围查询时很可能只在一个处理单元上进行这样就大大降低了空间数据查询与检索的并行化程度进而减弱了并行GIS和并行空间数据库的整体性能优势。HCMPR2tree索引的叶节点大小的确定受多种因素影响如网络数据传输速度、处理单元的计算能力和处理单元的个数等。本文把范围查询的系统响应时间作为性能评估指标在努力获得最小化的系统响应时间的同时找到最优的叶节点的大小的值。表1是确定系统响应时间的代价模型参数的说明其参考为运行 Windows2000profes2sional的IntelPentiumIV214GHz的计算机。表2是确定最优叶节点的大小所需要使用的参数列表及其说明。表1 代价模型的参数及其说明参数描述取值Npe计算机网络集群系统中处理单元的个数28B计算机网络集群系统中的互联网带宽100MBit/sTpage随机的磁盘页I/O操作所需时间0101sTcpu2msgCPU组成一个消息所需要的时间01001sSpage磁盘页的大小4KbytesSmsg数据传输中每个消息的大小 IEEE802131500bytesSheader每条消息的消息头的大小IEEE80213协议72bytesTidle在空闲网络上发送一个消息所需要的时间 0101s592012-05-182012-05-182012-05-182012-05-182012-05-182012-05-18测绘科学 第33卷表2 确定最优的叶节点大小所需参数及说明参数描述Tmsg在非空闲网络上发送一个消息所需要的时间qxqy查询的范围边界D空间数据集中总共的空间实体对象个数Qdata测试数据集的总的容量单位为bytesQqxqy查询边界所对应的空间实体对象所占用的磁盘页个数C叶节点的大小以磁盘页为计量单位pagesCopt最优的叶节点大小以磁盘页为计量单位pages1空间查询的系统响应时间函数使用K表示某个查询需要访问的处理单元的个数这样的处理单元也被称为是处于活动状态的处理单元。为确定HCMPR2tree索引的叶节点的大小需要建立C、K和Q的函数关系与系统响应时间函数密切相关。任何一个空间数据查询首先必须通过对主控制节点上的HCMPR2tree树的顶层链表结构进行操作以确定查询范围qx和qy所覆盖的处理单元的个数及其SID。然后由主控制节点向这K个处理单元发送数据查询的消息并等待查询结果从这K个处理单元返回到主控制节点。首先将空间区域进行归一化处理即将空间坐标映射到R01的单位空间上。针对不同的精度Q的取值是变化的本文采用如下表达式进行Q值的大致估算。Qqx×qy×QdataSpage1假设RTqxqy表示进行范围为qx×qy的系统查询响应时间其包含三个部分即处理单元的本地R树遍历与搜索时间Tlocal将查询的消息由主控制节点发送给每个活动处理单元的时间Tcommunication以及将查询结果向主控制节点反馈的时间Tresult有如下表达式成 立:RTqxqyTcommunicationTlocalTresult2为简化研究的复杂程度可以将网络流量突增而导致的网络的数据传输速度下降等突发事故的干扰排除在外。根据HCMPR2tree索引结构的设计每个处理单元上的R树索引结构不会很庞大其可保存在每个处理单元的主存内进行操作。因此本文忽略了并行查询时处理单元的本地数据处理时间Tlocal图2给出了系统响应时间RTqxqy的三个组成部分的关系。从图中可以看出第一个处理节点接收到来自主控制节点的消息后开始本地的数据查询处理然后等待其他处理单元接收消息并进行查询处理。当所有的活动处理单元接收完消息并完成本地数据处理后每个活动处理单元向主控制节点反馈查询结果。图中的本地数据处理时间已经完全被网络通信时间所覆盖。因此RTqxqy只由Tcommunication和Tresult两部分组成其表达形式如下:TcommucationK×Ttransx3图2 系统响应时间的三个部分的关系源自Koudas??996其中K表示活动处理单元的个数x表示向活动处理单元发送消息所占用的字节数通常为定值Ttransx则表示发送这些消息所需要的时间开销。TresultTtransQ×Spage4综上当本地数据处理时间可以忽略时的系统响应时间如下表达:RTqxqyK×TtransxTtransQ×Spage5为确定活动处理单元个数K与叶节点大小C的关系给出Tlocal的表达式。TlocalQ×TpageK6下面给出通过网络传递x字节数据所需要的时间表达式Ttransx。TtransxxSheaderx/SmsgBxSmsgTcpu-msg72活动处理单元个数K与叶节点大小C的关系的确定当确定了空间查询时系统的响应时间的表达式后下一步需要建立活动处理单元个数K与并行R树叶节点大小C的关系的表达式。从图2中可以得到Tlocal与K的关系:K-1×Ttransx?Q×TpageK8通过公式8求解K的表达式其解的形式为:Kopt114×Q×TpageTtransx29从公式9可以看出K的最优值仅与Q值有关。在确定K与C关系之间做一个合理的假设即查询结果中的所有叶节点数据是随机和独立分布于所有处理单元之上的则有以下表达式成立:K1-1-1NpeQC×Npe10其中 Q/C表示查询结果返回的所有的叶节点的个数1/Npe表示在给定的处理单元上包含 指定的叶节点的概率1-1/NpeQ/C表示在给定的处理单元上不包含Q/C个叶节点的概 率。对公式10求解得到如下结论:Copt-QNpe×log1-Kopt/Npe11从公式11中可以得出 这样的结论即当Kopt的值接近于Npe时C的值趋向于0。此结果从理论上来讲是非常 理想的但是如果C的取值太小如小于1个Spage会显著增加系统的I/O开销从而造成查 询效率的降低。因此在表1所示的计算机硬件配置条件下C的最优取值为1个磁盘页 大小即1个Spage这一结果的确定同样是由公式9、10、11共同完成的。为验证 HCMPR2tree索引结构的叶节点大小的最优选择的有效性本文采用空间查询的系统 响应时间和叶节点大小两个变量作为参数。实验中空间数据集选用全国1?100 万县市级行政区域边界图大小为1716MByte。处理单元的个数分别为2、4、8而查询 范围则选择011015qxqy。其结果如图3所示。图3 系统响应时间与叶节点大小之间 的关系692012-05-182012-05-182012-05-182012-05-182012-05-182012-05-18 第4期 赵园春等 并行R树空间索引中叶节点大小的确定方法研究图3是三种处理单元配 置条件下空间数据查询系统响应时间与叶节点大小变化关系的对比图。其中每个子 图中的五条曲线从上至下分别为查询范围边界从015至011的五种状态。本文此处所 采用的验证方案参考了Koudas等人的相关测试方法本文的实验结果总体上来说与 Koudas等人的实验结果有相似之处即在最优叶节点大小1个Spage处任何一种范围的 空间数据查询在具有不同的处理单元个数的条件下均获得了最小的系统响应时间。5 结束语分布式并行计算技术势必成为解决传统GIS所面临的计算和数据处理能力不 足问题的关键。与C/S和B/S计算模式在GIS中得到广泛应用相类似分布式并行计算 模式必将在GIS中发挥更重要的作用。本文以高效率的并行空间数据划分策略 HCSDP算法为基础以IanFoster的并行算法设计方法论为依据构造了分布式并行计算 环境下的并行R树空间索引结构并给出了并行R树空间索引结构中叶节点大小的确 定方法和性能评估方法经过验证该索引结构合理、性能高效、并能有效地提高海量 空间数据的计算与处理能力。参考文献 1RGHealeySDowersBMGittingsMJMineterEds11ParallelProcessingAlgorithmsforGISM1London:TaylorandFrancis199812DavidTaniarJWennyRahayu1Globalparallelindexformulti2processorsdatabasesystemsJ1InformationSci2ences12004165122:103212713IbrahimKamelChristosFaloutsos1ParallelR2treesC//ACMSIGMODUSA199214MHALIAASAAD1ThePN2Tree:AParallelandDistributedMultidimensionalIndexJ1DistributedandParallelDatabases200517:111213315赵春宇孟令奎林志勇1一种面向并行空间数据库的数据 划分算法研究J1武汉大学学报 20063111:962296516WangBHorinokuchiHKanekoKMakinouchi1AparallelR2treesearchalgorithmonDSVMC//Pro2ceedingsoftheInternationalConferenceonDatabaseSys2temsforAdvancedApplications1999:237224417BradfordGNickersonFengGao1SpatialIndexingofLargeVolumeSwathDataSetsJ1InternationalJour2nalofGeographicalInformationScience11998126:537255918刘宇等1空间信息格网研究进度J1测绘科学 20073241ResearchonthemethodforevaluatingthesizeofleafnodeofparallelR2treespatialindexingAbstract:ThesizeofleafnodeofparallelR2treespatialindexingisoneoftheimportantfactorsfortheefficiencyofspatialinde2xingandtheevaluationmethodwilldeterminethestandorfalloftheperformanceofparallelR2treespatialindexing1Thepaperdis2cussesanddesignsamulti2tiersparallelR2treespatialindexingstructureunderthedistributedparallelcomputingenvironmentandu2singtheresponsetimeofsystemqueryastheperformanceevaluationfactorgivesthemet hodforevaluatingthesizeofleaf2nodeofpar2allelR2treespatialindexingandtheavailabilityandtheapplicabilityoftheevaluationmethodhasbeenvalidatedsufficientlybyexper2imenting1SimultaneouslytheexperimentprovesthatthestructureofparallelR2treespatialindexingisrationalandhigh2performance1Keywords:parallelspatialindexingparallelR2treespatialindexingparallelGISdistributedparallelcomputingenvironmentZHAOYuan2chun?? LICheng2ming?ZHAOChun2yu?? ShandongUniversityofScienceandTechnologyQingdao266510China? ChineseAcademyofSurveyingampMappingBeijing100039China? SchoolofRemoteSensingandInformationEngineer2ingWuhanUniversityWuhan430079China上接第78页 6PeishengZhaoetal1GridMetadataCatalogService2BasedOGCWebRegistryServiceC//Proceedingsofthe12thannualACMinternationalworkshoPonGeo2graphicinformationsystems200417EDeelmanGurmeetSinghMalcolmPAtkinsonAnnChervenakNeilP1ChueHongCarlKesselmanSonalPatilLauraPearlmanMei2iSu1Grid2BasedMetadataServicesC//presentedat16thInternationalConfer2enceonScientificandStatisticalDatabaseManagementJ.