（计算机应用技术专业论文）rtree代价模型与查询优化研究与实现.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 无论是在研究领域还是在商业化的系统中，r - t r e e 都是应用最为广泛的 空间索引之一，它是地理信息系统中相当核心的一个研究方向。自1 9 8 4 年 g u m n a n 提出r - t r e e 以来，有大量针对其不足的改进和优化方案被提出。研究 的热点包括了对树结构的改善以提高查询效率和提出代价模型以评价和预测 r - t r e e 的行为。随着研究的深入，发现仅从r t r e e 本身来优化变得非常困 难。面对海量的数据集和日益复杂的g i s 软件运行环境，要找到适用于所有 情况的优化方案是几乎不可能的，因此研究的目标应该是既要研究效率更高 并且应用范围广的算法，同时还要针对真实的数据集进行分析和预处理，并 将其与r - t r e e 结构的优化联系起来。本文的研究基于一个真实的r - t r e e 空间 索引系统和真实的数据集，结合代价模型，从三个方面提出了r - t r e e 的优化 方案，即页面尺寸的设定、缓冲调度和缓冲区组织的改进以及通过数据采样 和迭代生成r - t r e e 这三个方面，具有较强的理论和实践意义。 主要工作包括： 1 研究r - t r e e 的主要算法、已有的代价模型和优化方案； 2 从三个方面给出了r - t r e e 的优化改进：1 ) 认为页面尺寸应该由数据集 的特性决定，并通过实验分析得出了优化页面尺寸的方法和结论；2 ) 认为已有的缓冲区理论在缓冲调度和缓冲区组织上存在不足，并给出 了相应的改进：3 ) 对于数据集变化较小的应用，通过数据采样和迭代 生成的方案能有效改进r - t r e e 的结构并提高查询效率； 3 实现了一个基于r - t r e e 的空间索引系统，在理论上应用了部分的研究 成果，同时在实现中力求做到高度优化。 关键词：g i s ；r - t r e e ：代价模型；查询优化 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t r t r e ei so n eo ft h em o s tw i d e l y - u s e ds d a 虹a li n d e x e sf o rr e s e a r c ha n d o o n a n e r c i a l , i ti so n eo ft h ek e y 五e l d si nt h er e s e a r c ho fg 【s t h e r ea r ep l e n t y i m p r o v e m e n t sf o rr - t r e es i n c ei tw a sp r e s e n t e db yg u t t m a ni n1 9 8 4 r e s e a r c h f o c a s e do nt h et r e es l a - u c t u r ei m p r o v e m e n t sf o re n h a n c i n gq u e r ye f f e c ta n dc o s t m o d ep r e s e n t a t i o nf o re v a l u a t i n ga n dp r e d i c t i n gi t sb e h a v i o r i t sv e r yd i 伍c u l tt o g e tm o r ee f f e c t i v eo p t i m i z a t i o nb yi m p r o v i n gr - t r e ei t s e i f i t sa l m o s ti m p o s s i b l e t of i n de f f e c t i v em e t h o d st oc o m p l ya l lc i r c u m s t a n c e sa sn l a s $ d a t as e t sg r o wa n d g i sr u n t i m ee n v i r o n m e n t sb e c o m em o r ec o m p l i c a t e d s ot h eg o a lh a st ob ef o c u s e d m o r ee f f e c t i v ea n dw i d e l y - u s e da l g o r i t h ma n di m p r o v i n gs t r u c t u r eo fr - t r e eb y a n a l y z i n ga n dp r e - p r o c e s s i n go r i g i n a ld a t as e t s t l l i sp a p e l p r e s e n t st h r e ed i f f e r e n t o p t i m i z a t i o nm e t h o d sw h i c ha r ep a g es i z es e t t i n ga n di m p r o v e m e n t sf o rb u f f e r a l g o r i t h ma n do r g a n i z a t i o na n dc r o a t i n gr t r e ew i t hd a t as a m p l i n ga n di t e r a t i o n b a s e do nar o a l a t i a li n d e x e ss y s t e mo fr t r a n dr e a ld a t as e t sa n dk n o w nc o s t m o d e s t h e o r yr e s e a r c ha n da p p l i c a t i o nb o t h 黜p r e s e n l e c l 1 1 l em a i nj o b so f t h et h e s i sa r e 硒f o l l o w e d ： f i r s t l y , r e s e a r c h o nt h em a i n a l g o r i t h m s o p t i m i z a t i o n so f r - t r e ei sp r e s e n t e d s e c o n d l y , t h r e ed i f f e r e n ti m p r o v e m e n t so i lr - t r e ea r ep r e s e n t e d ：t h ep a g es i z e s h o u l dn o tb ef i x e db u tb ed e t e r m i n e db yp r o p e r t i e so fd a t as e t ss ot h em e t h o d sa n d c o n c l u s i o no np a g es i z ea l ep r e s e n t e db ye x p e r i e n c e s t h ei m p r o v e m e n tf o rb u f f e r m a n a g e m e n ta n do r g a n i z a t i o ni sp r e s e n t e d t h er - t r e ec r e a t i n gl y r o c e s $ b yd a t a s a m p l i n ga n di t e r a t i o ni sp r e s e n t e df o ri m p r o v i n gt h es t r u c t u r eo f r - t r e e a tl a s tt h ei m p l e m e n t a t i o no fs p a t i a li n d e x e ss y s t e mb a s e d0 1 1r - t r e ew h i c h a p p l i e sl a t e s to p t i m i z a t i o nr o s u l t si sp r e s e n t e da n di t si m p l e m e n t a t i o nd e t a i li s h i g h l yo p t i m i z e d k e yw o r d s ：g i s ；r - t r e e ；c o s tm o d e ；q u e r yo p t i m i z a t i o n 西南交通大学硕士研究生学位论文第1 页 1 1 课题背景和来源 1 1 1 地理信息系统 第1 章绪论 地理信息系统，简称g 耐l 】( c - e o g r a p h i cl , f f o m l a t i o ns y s t e m ) 顾名 思义，地理信息系统是处理地理信息的系统。地理信息是指直接或间接与地 球上的空间位置有关的信息，又常称为空间信息。一般来说，g i s 可定义 为：“用于采集、存储、管理、处理、检索、分析和表达地理空间数据的计 算机系统，是分析和处理海量地理数据的通用技术” g i s 是一个用于管理、分析和显示地理的系统。我们可以从多个角度来 理解地理信息系统是如何工作于地理信息的： 从空间数据库的角度看：g i s 是一个包含了用于表达通用g i s 数据模型 ( 要素、栅格、拓扑、网络等) 的数据集的空间数据库。 从空间可视化的角度看：g l s 是一套智能地图，同时也是显示地表上的 要素和要素间关系的视图。 从空间处理的角度看：它是一套用来从现有的数据集获取新数据集的信 息转化工具。 从根本上说，g i s 是一种使用地理术语来描述世界的结构化数据库。在 近2 0 年间，随着e 璐在公共管理、科学研究以及商业中的广泛应用，对空 间数据的管理、表达和评估变得越来越重要。空间数据管理已经成为非常活 跃的研究领域。 1 1 2 空间索引及r - t r e e 空间索引是对存储在介质上的数据位置信息的描述，用来提高系统对数 据获取的效率。空间索引的提出是由两方面决定的：其一是由于计算机的体 西南交通大学硕士研究生学位论文第2 页 系结构将存贮器分为内存、外存两种，访问这两种存储器一次所花费的时 问一般为3 0 - - 4 0 n s ，8 1 0 m s ，可以看出两者相差十万倍以上，尽管现在有 “内存数据库”的说法，但绝大多数数据是存储在外存磁盘上的，如果对磁 盘上数据的位置不加以记录和组织，每查询一个数据项就要扫描整个数据文 件，这种访问磁盘的代价就会严重影响系统的效率，因此系统的设计者必 须将数据在磁盘上的位置加以记录和组织，通过在内存中的一些计算来取 代对磁盘漫无目的的访问，才能提高系统的效率，尤其是g i s 涉及的是各 种海量的复杂数据，索引对于处理的效率是至关重要的。其二是g i s 所表 现的地理数据多维性使得传统的b = t r 2 1 索引并不适用，因为b t r e e 所针 对的字符、数字等传统数据类型是在一个良序集之中，即都是在一个维度 上，集合中任给两个元素，都可以在这个维度上确定其关系只可能是大 子、小于、等于三种，若对多个字段进行索引，必须指定各个字段的优先 级形成一个组合字段，而地理数据的多维性，在任何方向上并不存在优先级 问题，因此b - t r e e 并不能对地理数据进行有效的索引，所以需要研究特殊 的能适应多维特性的空间索引方式。 研究人员提出了大量的索引结构用于处理多维空间数据，从空间数据库 的观点看，空间索引结构可以分为处理点对象的点存取方法和处理空间扩展 对象的空间存取方法【3 1 。其中，c e u 【4 】方法不适用于动态结构，因为其边界必 须是确定的；q u a d 豫【习没有考虑二级存储的分页机制；k - d - bt r e e s 6 】设计 为分页存储，但仅对点数据有效；网格文件川通过将每个物体映射到多维空 间中的一个点来处理非点数据。 为克服以上方法的缺点，1 9 8 4 年，加州大学教授a n t o n i ng u t t m a n 提出了 r o t r c c 8 】结构，它是一种有效的索引矩形物体的结构，最初用于v l s i ( 超大 规模集成电路) 设计程序中。从那以后，针对原始结构的不同变体被提出： 它们提供了更有效的存取方法，支持并发f o 和c p u 访问以及有效的批量载 入。 r o t r c c 在多方面得到了广泛应用，包括g i s ，图像和视频音频系统，时 序数据库等等。 西南交通大学硕士研究生学位论文第3 页 1 1 3 课题来源 本课题来源于作者在美国t h i n k g o o t m 公司工作时完成的一个项目。 t h i n k c 把o t m 公司致力于开发n e t 平台上的g 鹅引擎和相关应用。对于g i s 引擎中的空间索引模块，最初采用了加州大学伯克利分校的开源的空间索引 实现i i b g i s t 。l i b g i s t 是用c + + 语言实现的，为了使其工作在n e t 的托管 环境下需要对其进行封装。由于l i b g i s t 己停止更新，对其进行维护非常困 难，因此，公司决定自行开发r - t r e e 在n e t 下的实现。本文作者独立完成 了r - t i n ：的实现并将其运用到公司的g i s 组件m a p s u i t e 中。刚开始系统运 行良好，随着应用的增加，开始发现其在海量数据查询的不足，客户对查询 速度提出了更多的要求。这促使作者开始研究已有代价模型和查询优化方 法。 1 2 研究内容和意义 经过2 0 多年的发展，不断产生的r - t r e e 变体形成了一个枝繁叶茂的 r - t r e e 族。同时g i s 、空间数据库厂商也在多种平台和环境下实现了r 树， 并将其应用到g i s 或空间数据库软件中。 由于r - t r e e 变体众多，并且依据论文可以有多种实现方式，其性能表 现各异，并直接影响到空间检索的性能，因此，如何评价和预测其性能就显 得至关重要。除了通过实验来比较r - t r e e 的性能外，还需要从理论上研究 其代价模型，包括插入，删除，查询等代价模型。 研究代价模型并不是最终目的，而是通过代价模型来预测r - t r e e 的行 为，并找出更好的优化方案。作者致力于把代价模型和对r - t r e e 的优化结 合起来，提出一些较新的研究方法并得出一些典型结论。 综上所述，本论文的研究内容及意义如下； 1 ) 详细分析r - t r e e 的结构，构造和查询过程，重点研究插入算法和区 域查询，并研究现有的针对r t r e e 的改进； 2 ) 从新的角度研究代价模型； 3 ) 根据已有代价模型的优缺点，提出了查询优化改进； 西南交通大学硕士研究生学位论文第4 页 4 ) 在n e t 平台下独立实现基于r - t r e e 的空间索引系统，根据代价模型 的研究成果对传统算法进行了部分改进，并给出实验数据和分析。 1 3 论文组织方式 论文主要分为四章，其中第三章和第四章为作者的研究成果。各章的内 容简要介绍如下： 第一章为绪论，简要介绍论文的整体情况，包括课题的来源和背景、课 题的研究现状和意义、课题研究的主要成果和论文的组织。 第二章为理论基础，介绍了r - t r e e 的定义和常见算法，回顾了r - t r e e 发展的历程，分析了带有缓冲和不带缓冲的代价模型，为深入探讨r - t r e e 的代价及查询优化打下基础。 第三章为r - t r e e 查询优化改进。首先分析了研究现状和本文的研究重 点，然后从三个方面给出了优化改进方案，最后给出了实验及分析 第四章为基于r - t r e e 的空间索引系统的实现。该章给出了一个完整的基 于r - t r e e 的空间索引系统的实现，力求从理论到具体实现做到高度优化。 西南交通大学硕士研究生学位论文第5 页 第2 章r - t r o o 及其优化概述 2 1r - t r e e 定义 r - t r e e 作为b - t r e e 上的直接扩展，由g u t t m a n 于1 9 8 4 年提出，它 是一颗包含中间节点和页节点的高度平衡树。页节点的格式为( o i d ，r ) ， o i d 是节点元素的编号，r 是数据对象的最小边界矩形，格式为( p 。一bp - 。，p 。，p 。p 。，p 。，) ，p 为二维矩形的左下角和右上角坐标。中间节点 的格式为( p t r ，r ) ，p t r 为指向下层节点的指针，r 为下层节点的最小边界矩 形。 设m 为节点中的元素的最大数目，设m 剑2 ，则节点中元素数目必须 在( m m ) 之间。r - t r e e 必须符合如下特征： ( 1 ) 每个页节点必须包含( m ，m ) 个节点，根节点除外； ( 2 ) 对每个页节点中的元素( o l d , r ) ，r 是o i d 所指向的空间对象的最小 边界矩形； ( 3 ) 每个中间节点包含( 1 n j 哪个子节点，根节点除外： ( 4 ) 对于中间节点中的元素q 缸皿) ，r 为包含子节点所有矩形的最小 边界矩形； ( 5 ) 根节点至少包含两个子节点，除非它是页节点； ( 6 ) 所有的页节点出现在树中的同一层次。 2 2f 0 t r e e 的经典算法概述 r - t r e e 的经典算法主要包括插入算法、节点分裂算法和删除算法，后来 又提出了空间连接算法和最近邻算法。 插入算法的主要步骤有三步，第一步是找到合适的页节点以供插入；第 二步是在指定节点直接插入记录或者调用分裂算法分裂节点后再插入纪录； 第三步是向上调整树。 西南交通大学硕士研究生学位论文第6 页 分裂算法主要目的是将m + i ( m 是r 树每节点允许的最多纪录) 条索引 纪录分成两组。分裂算法有线性分裂算法和平方分裂算法两种，在具体实现 中常使用平方分裂法。平方分裂法的要点在于使分裂后产生的节点的m b r 的 面积最小，因此它会以组合的方式遍历每两条纪录，计算其m b r ，在r - t r e e 的生成过程中。它是时间占用最多的部分 由于空间对象和空间操作的复杂性，使得空间数据库中的操作既是i o 密集型的也是c p u 密集型的。因此在空间数据库中，充分利用空间索引进行 检索是一项关键技术 9 1 ，而大部分空间查询研究集中在空间连接和最近邻查 询。空间连接f l o 】是非常重要的运算符。当两个关系r 和s 基于一个空间谓 词e 进行连接时，称之为空间连接。空间连接主要用来合并多个数据集的 空间对象。空间谓词主要有i n t e r s e c t ( 相交1 、c o n t a i n ( 包含) 、c o n t a i n e d ( 被包含) 、o v e r l a p ( 交叠) 等。 1 9 9 3 年，b r i n k h o f f 提出了基于r - t r e e 的空间连接算法【1 1 】该算法是一 种深度优先遍历过程。其出发点是非叶节点的矩形能够容纳所有子节点中矩 形的m b r 。因此，若两个目录矩形不相交，则其子树中所有数据矩形也比 不相交，反之，则其子树中某些数据矩形可能相交。 针对深度优先遍历算法只能进行局部优化的缺陷，h u a n g 等在1 9 9 7 年提 出了一种基于全局优化的广度优先遍历算法【1 2 1 。该算法以广度优先的方式 同时遍历两颗r - t r e e ，同时逐层处理连接计算。 基于r - t r e e 的最近邻查询算法【1 3 】最早r h r o u s s o p o u l o s 于1 9 9 5 年提出。作者 使用分枝界定的r 树遍历算法，提出了两个度量标准用于r 树的排序和剪枝， 一个是m n d i s t ，称为乐观距离；另一个是h 皿弧i a x d i s t ，称为悲观距离： 分别作为查询点到树节点m b r ( 最小边界矩形) 中最近邻对象的距离下界和 上界。基于这两个度量标准，作者提出了三个启发式规则来过滤不包含最近 邻居的节点，从而减少节点访问个数，减少磁盘i ，o ，进而有效地提高查询 性能。1 9 9 8 年，c h 伽窖h 等进一步改进该算法，移除前两个既不能增强剪枝 效果又具有高计算复杂度的剪枝规则，减少了c p u 计算代价其它基于r t r e e 树的最近邻算法有增量最近邻查询( k 二d 1 5 , 1 6 1 、逆最近邻查询”7 】、条 件最近邻查询i lg 】等。 西南交通大学硕士研究生学位论文第7 页 删除算法同插入算法类似，可看作是插入算法的逆过寝，也分为三 步：第一步是定位到待删除记录的节点；第二步是删除记录；第三步是向上 递归调整树。 2 3 现有的优化成果 r - t r e e 是b t r e e 在多维空间下的自然扩展，它具有b - t r e e 的优点，如 自动平衡、空间利用率较高、适合于外部存储等。r - t r e e 的主要问题在 于，由于中间节点目标矩形允许且可能重叠，因此往往存在多条查找路径， 而其中的某些查找路径往往不包含查找结果，这就影响了查找性能。研究显 示，随着索引维数的增加，中间节点目标矩形的重叠迅速增加，这无疑会严 重影响查询性能；而减少磁盘读取次数则是优化的关键所在。 r - t r e e 的优化可以分为局部优化和全局优化，所谓局部优化就是仅仅考 虑待分裂节点的局部的数据组织来优化索引；而整体优化则是从总体的数据 组织考虑，使总体的数据空间的组织达到最优。显然局部最优只能反映局部 的数据组织情况，不一定能保证全局最优，而一般的节点分裂算法都是局部 的优化，所以若想进行全局优化，则必须扩大节点分裂时优化的范围，从而 接近全局优化的目标。 从局部优化的角度看，在r - t r e e 中插入新的数据对象时，关键在于合适 叶节点的选择和溢出节点的恰当分裂。这两个局部的因素都直接影响r - t r e e 的整体结构。g u t t m a n 在其论文中给出了一定分析，此后其它的研究人 员对此进行了发展，给出了一些不同的衡量最优的方法。但局部的最优并不 意味着全局的最优，r - t r e e 结构是否合理，更要着眼于整体的优化。此 外，在构建r - t r e e 时，空间对象插入的顺序不同，相应的树结构也不相 同。针对不同的优化策略，出现了相应的变体，以下将介绍最典型的变体， 包括p a c k e dr - t r e e 、r - t r e e 和r - t r e e 首先介绍p a c k e dr - t r e e ”，p a c k e dr - t r e e 是由r o u s s o p o u l o s 和 l e i f k e r 最早提出的。它的出现主要是为了解决r - t r e e 生成时的效率问 题。在g i s 应用中，由于空间对象相对稳定，所以在生成r - t r e e 过程中 可以采用批量生成的方法。其主要思想归纳如下： 西南交通大学硕士研究生学位论文第8 页 1 将n 个数据集按照某种一维顺序排序，使它们可以被分成n 个连续 的组，每组中包含m 个矩形，在下一步中，同组的这m 个矩形联通它们所 指向实际对象的指针可以被装到同一个叶节点中。 2 将这n 个矩形连同对象指针按顺序分别装到n 个节点中，同时计算 它们的m b r 并和节点的i d 一起输出到临时文件中 3 以临时文件中的m b r 级节点i d 作为输入，递归执行1 、2 步，生成 更高一层节点，直到生成根节点。 它的缺点在于由于只是在单一的方向上对数据进行排序，导致最终生 成的节点的m b r 都偏向于长条形。另外它的填充度是满的，适用于数据比 较稳定的应用。 要介绍的第二种变体是r + - t r e e ，r + 一r e e 【捌的主要思想是：如果裁减数 据矩形，那么中间节点目标矩形的零重叠可以获得，因此对于点查询，查找 路径可以只有一条：对于区域查询，查找性能也可以得到提高。 r + - t r e e 具有如下特点： 1 对于中间节点的任一索引项( c p ，船r ) ，c p 指向的子树包含目录矩 形r ，r 被m b r 覆盖；c p 指向的子树包含数据矩形t ，t 与m b r 重叠； 2 中间节点的任意两个索引项不重叠； 3 叶节点中的数据矩形允许并可能重叠； 4 根节点如果不是叶节点，则至少有两个孩子： 5 所有的叶节点在同一层次。 r * - t r e e 与r - t r e e 的区别主要有三点： 1 r * - t r e e 的节点中对数据项和索引项的填充个数没有严格限制： 2 r * - t r e e 中间节点的目标矩形不允许重叠； 3 甜一t r e e 中空间对象的标识重复存储在多个叶节点。 r 一t r e e 存在的主要问题是：节点分裂操作复杂，且可能向上层节点及下 层节点延伸，这会导致节点分裂的增加及空间对象的多次重复存储，除了存 储空间开销大以外，树的深度也会增加，这又会影响查询性能。 第三种典型的变体是r - t r e e ，r - t r e e 【2 l 】是r - t r e e 家族中综合性能最出 色的一个种类。为了选择一个合适的插入路径，r - t r e e 只考虑了目标矩形 的面积这一因素，r - t r e e 除了考虑面积以外，还考虑了目标矩形的重叠。 西南交通大学硕士研究生学位论文第9 页 为了改进树的结构，在r l t r e e 的删除过程中，对于下溢节点的处理是 重新插入节点所有剩余的数据项于该节点所在层，从而使它们有可能分布于 不同的节点。实验证明，删除部分数据项然后再将其插入到r _ t r e e 中，可 以优化r * - t r e e 的结构，提高2 0 - 5 0 的性能。 如果r 一t r e e 的节点是第一次分裂，对分裂节点n 的m + i 项，计算它们 的矩形中心点到n 的船r 矩形中心点的距离，按距离降序排列n 的m + i 项， 从n 中删除排序的前t 项并调整n 的约束矩形，从最大或最小距离开始，调 用插入算法重新插入这t 项。如果重新插入后该分裂节点第二次分裂，则直 接进行分裂算法调用。 尽管矿一t r e e 的构造过程时间开销有所增加，但经实验表明，r - t r e e 的 检索性能和空间利用率都得到了较大的提高，也就是说，r * - t r e e 以少量的 构造时间开销换取了更高的查询性能。不过，r - t r e e 中存在的多路径查找 依然是制约查询性能的瓶颈。 r - t r e e 的优化研究过程其实也是r - t r e e 发展的过程，经过2 0 多年的发 展，r - t r e e 己发展成为拥有广泛交种的r - t r e e 族，上述三种变种是其中最典 型的。除了上述提到的变体外还有很多，如在空间对象的近似表达方面，有 利用最小边界球的球树( s p h e r et r e e s ) 吲，最小边界凸多边形的c p 树吲，最 小边界多边形的c e l l 树 2 4 1 ，p 树口5 】；在节点分裂方面，文献【2 6 2 8 】提出了不 同的分裂算法；d r 树1 2 9 是适合主存索引的变体；位i 羽r t r e e 3 0 ) 借鉴了位图索 引的思想。通过分析现有的变体，可以得出以下结论： 1 分裂过程是影响r - t r e e 性能的重要因素，r + - t r e e 认为应避免中间节点 的区域重叠，而r l t r e e 则认为不能完全避免重叠，只是分裂结果应减少区域 重叠度而不是减少面积； 2 对r - t r e e 的优化研究从集中于对树结构本身的优化到结合数据集的特 性提出有针对性的优化。 从整体上看，r - t r e e 的变体解决了r - t r e e 的部分不足之处，扩大了其应 用范围，同时引入了相关的研究成果如数据挖掘和聚类分析，算法也日趋成 熟化。 西南交通大学硕士研究生学位论文第1 0 页 2 4r - t r e e 代价模型研究 在r - t r e e 的发展过程中，出现了众多的变体，因此如何评价和预测它们 的性能就显得至关重要。除了通过实验来比较它们的性能外，还需要从理论 上研究其代价模型，包括插入、查询和删除的代价模型。代价模型的重要性 体现在：( 1 ) 能够更好地理解在不同类型和大小的数据集下的空间索引行 为；c 2 ) 能够对各种空间索引的性能进行客观比较；( 3 ) 在空间数据库 中，基于代价的查询优化需要利用代价模型来评估复杂空间查询的代价，以 选择最优查询计划1 3 1 1 。 f a l o u t s o s 等最先尝试分析r - t r e e 的域查询性能【3 2 】，他们提出的模型假设树 是均匀分布的，并且树的每个节点都被填满。虽然该模型有其局限性，但以 后几乎所有的代价模型都是以此为基础发展起来的，式( 2 1 ) 是计算r - t r e 圯高 度的公式。 = l o g ，苦( 2 - 1 ) k a m e l 和p a g e l 分别独立地对式( 2 1 ) 进行了扩展【3 3 矧，假设n 维空间中 有一n 维的r 树，该r 树有k 个结点，结点勺的边已知，则对于任一查询 窗口q - ( q ，g ：，“) ，可以得到平均访问次数即式( 2 2 ) ， d a ( q ) = 兀o “+ 吼) ( 2 2 ) 1 1 其贡献是揭示了除面积之外r 树节点周长最小化的重要性。但该模型要 求r 树必须事先建立，且假定数据和查询窗口均匀分布。 f a l o u t s o s 和k a m e l 对文献口3 】进行了扩展【3 习，利用点数据集的分形维属 性d ，使代价模型能预测磁盘访f 司次数，该模型是第一个能处理非均匀分布 的代价模型，但仅针对点数据集。同时，b l e u s s i 和f a l o u t s o s 也利用了分 形维作出了选择性评估 同年，p a g e l 提出了一个优化算法1 3 7 】来计算静态r 树的性能下界，从而 能在不同空间索引结构之间进行性能比较。利用该算法，作者计算出当时最 西南交通大学硕士研究生学位论文第11 页 好的静态r 树和动态r 树分别是h i l b e r tp a c k e dr 树1 3 3 】和r 树【2 1 1 。之 后，他又对节点矩形的面积，周长，数量三要素进行进一步研究，推导出各 种域查询的代价模型，并得出一个重要结论，窗口查询性能在一般情况下可 以代表其它各种域查询的性能例。 到目前为止比较全面的代价模型是s e l l i s 等提出来的嗍，分别针对没 有缓冲区和有缓冲区的情况做了讨论，提出了空间选择查询和空间连接查询 对空间选择查询而言，基于r - t r e e 的空间选择查询的问题可定义如下： 设d 为数据空间的维数，w s = 0 ，1 4 为d 维归一化数据空间。假定r - t r e er t 中包含。个数据矩形，查询结果为与查询窗口q = ( q 。，q ：， q d ) 相交叠的所有矩形。不考虑r - t r e e 结构，只利用数据集的特性得到节点 访问次数如( 2 1 2 ) 。 删一删c 舶) = 1 节l 悟垂陋，割；硝1 对空间连接而言，空间连接操作通常由以下两个步骤进行【柏】： 1 ) 过滤操作：产生满足空间谓词的最小边界矩形( m b r ) 对，这些m b r 对是下一步操作的候选者，其中可能包含一些不满足空间谓词的结 2 ) 精炼操作：检查每一对候选者，根据其空间对象的确切范围选出满足 图2 - 1 m b r 相交但实际并不相交的空间对象 西南交通大学硕士研究生学位论文第12 页 至今为止，已有多种针对精炼操作进行优化的连接算法【4 牌】，这些算法 大致可分为三类：( 1 ) 基于两个数据集都有索引的连接；( 2 ) 基于仅有一个 数据集都有索弓l 的连接；( 3 ) 基于无索引数据集的连接。在多个数据集在进 行连接时，即使它们自身都带有索引，它们连接后所得的中间结果也不存在 索引，所以第三种算法在应用中更有普遍性。 假设两个空间数据集，其基数分别为。和矗，相应的m b r 存储在 r 1 和r 2 这两颗r - t r e 中。代价模型的目标就是要推导出一个估计两个数据 集在空间连接时所需要的节点访问次数n a 的函数。这个函数的参数必须是 数据集本身的属性，而与r - t r e e 的结构无关。该函数如下： n at o t a l ( r 1 , r 2 户 m ( 蜀，r 2 ，1 0 + n a 俾2 ，蜀，乞) ( 2 - 1 4 ) t h e o d r i d i s 和s e l l i s 研究出来的代价模型是比较成功的。 理论方面，首先，该模型没有利用r - t r e e 结构的属性，只是利用数据集 本身的属性；其次，该模型考虑了缓冲区对代价评估的影响：再次，该模型 适用于均匀分布和非均匀分布的数据集。另外，该模型虽不能十分准确的计 算出查询代价，但是在误差允许的范围内，对空间查询优化的研究仍有重要 意义。空间连接代价模型的评估是空间数据库系统的查询优化中很重要的一 个方面。对于空间连接查询，其对磁盘的读取次数直接影响系统性能的优 劣。所以，面对各种各样的查询方案，只有事先估计出一个大致的代价，空 间查询优化器才能确定最终执行的计划。但空间查询优化器找到的是较优的 执行策略而不是最优的执行策略。 在应用方面，该模型所依据的算法比较简单，易于理解和实现，同时也 是研究其他代价模型的一个重要的理论基础。 已有的模型虽然取得了一定的成就，但也存在一定的缺点。由前述章节 的s j 算法可知，该模型的时间复杂度很高。实际应用中会涉及两颗或更多 的r t r e e ，相应的数据量会很庞大。另外，该模型对缓冲区的处理不够深 入。该模型有比较理想化的限制条件假设数据集均匀分布，实际上数据的 分布在各个领域有很大的差异，所以其在选择查询的估计上受到很大限制 【柏】。 对于一个空间连接模型，估计准确固然是一个衡量其评估性能的重要标 准。但实际上到目前为止，还没有哪位专家所提出的模型能精确的计算出相 西南交通大学硕士研究生学位论文第1 3 页 应的磁盘访问次数。对于一个易于实现的代价模型，仅凭算法本身来实现有 一定难度，所以需要借助缓冲区和辅助文件等的帮助。由于空间数据集合可 能遵循各种各样的数据分布，所以在计算数据密度的时候采用抽样算法。 西南交通大学硕士研究生学位论文 第1 4 页 第3 章基于代价的r - tr e e 查询优化改进 上一章介绍了r - t r e e 的定义和经典算法，同时介绍了r t r 臂优化的发 展，然后分析了无缓冲区的代价模型和带有缓冲区的代价模型。针对r - t r 的研究从单纯的算法改进发展到分析代价模型预测其行为。通过回顾 已有的研究成果，可以发现它们具有如下特征： 1 r - t r e e 优化的研究集中在理论研究，各种变体虽然取得了一定的成 果，但是由于算法实现较为复杂，同时也没有出现能全面替代r - t r e e 的变 体，因此在实际中应用并不广泛。在商业和开源的( 嬲系统中，应用最广 泛的仍然是经典的r - t r e e 。 2 对于代价模型的研究仍然侧重于理论建模，将代价模型与具体实现结 合起来的研究较少；另一方面，评价指标单一化，几乎都基于磁盘访问代 价。随着硬件的飞速发展，大容量缓冲区甚至是全内存的r t r e e 【4 q 成为可 能，因此需要增加评价指标和更新评价体系。 3 对r - t r 的分析和溅试方法和工具的研究不足。如何在海量数据中快 速检索信息，除了理论分析以外，还需要分析和测试工具的辅助 基于上述研究现状，本文尝试从不同的角度进行研究，体现在以下几个 方面： 1 实现了一个基于r t r e e 的空间索引系统并且应用于商业化的产品中， 获得了用户的高度评价。 2 从这个真实的空间索引系统出发，结合代价模型和已有的优化手段， 在真实数据的测试基础上找到新的优化方案，并力求使优化方案易于理解和 实现。 3 将部分研究成果应用于系统中，一方面可以检验优化方案的有效性， 另一方面为下一步研究做准备。 本章首先分析了现有研究的不足之处，然后在已有研究的基础上，结合 实际应用，提出改进的优化方法，主要从三方面加以改进：首先是针对页面 尺寸大小的改进；其次是引入新的缓冲算法；最后对于真实世界的数据集， 采用了抽样和迭代生成来改进树的结构以提高查询效率。 西南交通大学硕士研究生学位论文第1 5 页 3 1r - t r e e 页面尺寸属性改进 已有的代价模型没有利用r - t r e e 结构的属性，但我们在实践中发现，对 于同一种查询算法而言，r - t r 结构本身对查询效率有相当大的影响。同 时，用户希望通过简单的处理就能对不同的数据集提高查询效率这促使我 们把数据集的特性和r - t r e e 结构中的属性联系起来。为简化问题，我们暂 且不考虑数据集的密度，首先开始研究页面尺寸。 3 1 1r - t r e e 页面尺寸属性回顾 r - t r 是作为一种分页的索引结构提出的。页面尺寸和填充因子m 值是 在构造r - t r 时可以设定的两个值，这两个值的设定会影响到树的形状和 查询效率。对于某个具体的数据集而言，页面尺寸的值越大，总的页数则越 小但如何设定一个合适的页面尺寸呢? 在g u t t m a n 的论文中，并没有深入 探讨页面尺寸，仅仅给出了五种页面尺寸下的对比测试，现引述如下： 选择五种页面尺寸及相应的m 值进行测试： 表扣1 页面尺寸及相应的m 值【8 】 页面尺寸( 单位：字节)每页容纳的最大纪录数 1 2 86 2 5 61 2 5 1 22 5 1 0 2 45 0 2 0 4 81 0 2 西南交通大学硕士研究生学位论文第16 页 e y t e , p e a p e t e 图3 - 1 页面访问的查询效率嘲 图3 - 2 显示了不同页面尺寸下的c p u 占用的查询效率。 董b 乜既髓r 髓抛 图3 - 2c p u 占用的查询效率8 】 3 1 2 对于不同数据集设定可变页面尺寸之探讨 在已有的r - t r e e 实现系统中，无论是商业的还是开源的，都几乎将页面 尺寸设为固定的值，一般设为8 1 9 2 字节。但对于不同的数据集，该值未必 西南交通大学硕士研究生学位论文第1 7 页 为最佳的取值，而数据集中最容易的获取就是其纪录数，故我们选择了一组 s h a p e 3 c 件0 4 3 1 ，将它们按照不同的纪录数范围进行分组，选择的s h a p e 文件 列表如下： 类别文件名纪录数 纪录数 = 1 0 k t e x a s c o u n t i e s s h p 2 5 4 t e x a s r o a d s s h p 3 7 0 1 d e p t h l i n e s 1 甲 8 5 2 6 1 0 k = 纪录数 = l o o k m a i n m a d s h p 3 0 1 5 8 e v c r g r e e n s h p 6 6 5 6 7 u r b a n a r e 乱s h p 3 6 4 3 2 l o o k = 纪录数 = 1 m r e s u l t 2 0 0 m s h p 1 8 8 8 7 7 4 r c s u l t 3 0 0 m s h p 2 5 1 8 5 9 8 。 注：r e s u l t 2 0 0 m s h p 和r e s u l t 3 0 0 m s h p 为多个s h a p e 文件合并而成。 以下是取不同的页面尺寸时作o v e r l a p 查询的c p u 时间占用，查询窗口 分别为全区域查询、左上四分之一窗口查询、右下四分之一窗口查询、中间 四分之一窗口查询，时间单位为秒： i 记录数小于l o k 图3 - 3t e x a s c o u n t i e s s h p 在不同页面尺寸下的效率 西南交通大学硕士研究生学位论文第1 8 页 图3 _ 4t e x a s r o a d s s h p 在不同页面尺寸下的效率 图3 5 d e p t h l i n e s h p 在不同页面尺寸下的效率 2 记录数在l o k 到1 0 0 k 之间 图3 - 6m a i n r o a d s h p 在不同页面尺寸下的效率 西南交通大学硕士研究生学位论文第1 9 页 图3 - 7 e r e r g r e c n s h p 在不同页面尺寸下的效率 m 3 8u r b a n a r e a s h p 在不同页面尺寸下的效率 3 记录数在1 0 0 k 到i m 图3 9c r o p s h p 在不同页面尺寸下的效率 西南交通大学硕士研究生学位论文第2 0 页 图3 - 1 0i n l a n d w a t c r s h p 在不同页面尺寸下的效率 m 3 - 1 1 r o a d s h p 在不同页面尺寸下的效率 4 记录总数大于1 m 图3 - 1 2r e s u l t 2 0 0 m s h p 在不同页面尺寸下的效率 西南交通大学硕士研究生学位论文第2 1 页 图3 1 3r e s u l t 3 0 0 m s h p 在不同页面尺寸下的效率 从以上的测试可得出如下结论： 1 在不考虑数据密度的情况下，对于典型的查询窗口，页面尺寸设置过 大或过小都会降低查询效率，只有取适当的尺寸才能取得较好的效 率； 2 随着数据集纪录数的增加，页面的最佳尺寸也呈线性增长。但在实际 中，不可能无限增长，因为：页面尺寸过大导致r - t r e e 索引文件生 成时间急剧增长：页面尺寸增加也加大了内存占用。 3 无法得到最佳的页面尺寸，只能凭实验值作出大致的估计 根据以上实验，我们改进了r - t