（计算机应用技术专业论文）gms数据库管理系统中时空索引的研究与实现.pdf

重庆邮电大学硕士论文摘要 摘要 时空索引技术在地理信息系统、全球定位系统、无线通信技术、交通控制等 诸多领域均有十分重要的研究意义。传统的数据库能支持时空数据的存储，却无 法支持对其有效访问。这是因为传统索引无法处理多维坐标数据的排序问题，更 没有时间维的概念，由此时空索引应运而生。时空索引技术是当前空间数据库和 g i s 领域的一个重要研究课题，而且对如何建立更有效的时空索引结构一直是这 些领域最现实、最急迫，最前沿的研究方向。本文在这方面做了积极探索，提出 了有效的解决方案。 从介绍最早用于处理多维扩展的空间索引r 树出发，对当前国内外主流时空 索引方案进行了分类、比较。从确保空间位置的相邻关系、更新频繁、计算量等 角度考虑，在t p r * 和r l i n k 树的基础上，提出t p r * l i n k 树。文中给出t p r * l i n k 树的索引结构，能够包含时空数据的多维和时间特性；对结点添加右链可以将同 层结点相连，便于索引操作：对结点和结点项大小设计，考虑到存储机制，减少 了i o 次数。因此是一种有效的时空信息建模方式。根据索引结构中右链机制的 特点，设计的查找、插入算法，在查找时，即使有插入操作，也可以从右链中得 到所需结点。结点分裂时，可先通过右链连接原来结点，在合适时再插入父结点。 这样提高了索引操作的性能。对于范围查询，因移动物体和查询范围在查询时间 内都不断的运动，本文研究了各种相交情况，只根据它们的初始和结束位置进行 判断，保证了范围查询的精确性和简单性。最后，在韩国仁荷大学设计开发的空 间数据库管理系统g m s 中实现了t p r * l i n k 树，可对移动对象现在和将来位置 进行索引，实现了基本的查找、插入、删除操作。实践证明，t p r * l i n k 树在 g m s 中取得了较好的查询性能。 关键词：数据库，时空索引，移动对象，索引结构 重庆邮电大学硕士论文 摘要 a b s t r a c t s p a t i o - t e m p o r a la p p l i c a t i o n sh a v ed e v e l o p e dd r a m a t i c a l l yi nm a n yf i e l d s ，s u c h a sg e o g r a p h i ci n f o r m a t i o ns y s t e m ，g p s ，w i r e l e s sc o m m u n i c a t i o nt e c h n o l o g i e s ，t r a f f i c c o n t r o la n ds oo n t h o u g ht r a d i t i o n a ld a t a b a s ec a r l s t o r et h es p a t i o - t e m p o r a ld a t a ，i t c a n n o to p e r a t ei te f f i c i e n t l yd u et ot h eo r d e rp r o b l e mo f m u l t i d i m e n s i o n a ld a t aa n dt h e c o n c e p to ft i m ed i m e n s i o n s p a t i o t e m p o r a li n d e xt e c h n o l o g yi sa ni m p o r t a n tt o p i c b e t w e e ns p a t i a ld a t a b a s ea n dg i sf i e l d s f u r t h e r m o r e ，s p a t i o t e m p o r a li n d e xs t r u c t u r e i sa l w a y st h em o s tr e a l i s t i c ，m o s t 、u r g e n ta n dh o a e s tr e s e a r c hd i r e c t i o n t h i sp a p e rh a s m a d et h ep o s i t i v e e x p l o r a t i o ni n t h i sa s p e c ta n ds o m ee f f e c t i v es o l u t i o n s a r e p r e s e n t e d f i r s t l y , rt r e ew h i c hi st h ee a r l i e s ts p a t i a li n d e xt oh a n d l em u l t i d i m e n s i o n a l e x t e n s i o ni si n t r o d u c e d t h e nt h em a i ns p a t i o t e m p o r a li n d e x e sa r ec a t e g o r i z e da n d c o m p a r e d c o n s i d e r i n gt h eo r i g i n a ls p a t i a li n f o r m a t i o ni n t e g r a l i t y , u p d a t ei n t e n s i v e a n dc o m p u t a t i o nc o m p l e x i t y , an o v e li n d e xt p r - l i n kt r e eb a s e do nr - l i n ka n d t p r + t r e ei sp r o p o s e di n t h i sp a p e r t h ep a p e rp r e s e n t st h ei n d e xs t r u c t u r eo f t p r + l i n kt r e e w h i c hc o n t a l a ss p a t i a la n dt e m p o r a la t t r i b u t i o n s t h ec r u c i a la d d i t i o n i st h er i g h t l i n k ，ap o i n t e rg o i n gf r o me v e r yn o d et oi t sr i g h ts i b l i n go nt h es a m el e v e l ， w h i c hb e n e f i t st h ei n d e xo p e r a t i o n t h ed e s i g no f n o d ea n de n t r yw h i c hc a nr e d u c et h e n u m b e ro f i oi sp r o p e rt os t o r i n gm e c h a n i s m s ot h ei n d e xs t r u c t u r eo f t p r + - l i n ki s a ne f f i c i e n tm o d e l i n gm e t h o d a c c o r d i n gt oc h a r a c t e r i s t i co ff i g h t l i n k ，t h es e a r c h a l g o r i t h mm a k e st h en o d es e a r c he a s i l y e v e ni ft h e r ea r ei n d e xo p e r a t i o n sa tt h es a m e t i m e ，t h en e e d e dn o d ec a nb ef o u n df r o mr i g h l i n k w h e nan o d ei ss p l i t ，an e wr i g h t s i b i n gi sc r e a t e da n dd i r e c t l yi n s e r t e di n t ot h er i g h to f t h eo l do n e ，w h i c hi m p o v e s t h e p e r f o r m a n c eo fi n d e xo p e r a t i o n t ow i n d o wq u e r y , n o d e sa n dw i n d o wc h a n g e c o n t i n u o u s l y a l li n t e r s e c t a n tc o n d i t i o n sa r er e s e a r c h e da n do n l yt h es t a r ta n d t h ee n d p o s t i o n sa r ec a l c u l a t e di nt h ea l g o r i t h mw h i c hg u a r a n t e e sp r e c i s i o na n ds i m p l i c i t y g m si sas p a t i a ld m b sw h i c hi sd e s i g n e da n dd e v e l o p e db yi n h au n i v e r s i t yi n k o r e a f i n a l l y , t p r * l i n kt r e e i st oe f f i c i e n t l yf u l f i l ls e a r c h ，i n s e r ta n dd e l e t e o p e r a t i o n st oi n d e xt h ec u r r e n ta n df u t u r ep o s i t i o n so fm o v i n go b j e c t si ng m s t h e e x p e r i m e n t si n d i c a t et h ei n d e xo f t p r * - l i n k t r e eh a sg o o dq u e r yp e r f o r m a n c e k e yw o r d s ：d a t a b a s e ，s p a t i o - t e m p o r a li n d e x ，m o v i n go b j e c t ，i n d e xs t r u c t u r e i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得重庞监电太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：硅搔签字日期：励年g 月纱日 学位论文版权使用授权书 本学位论文作者完全了解 重庆塑壹太堂 有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权 重麽蛏电太堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 副隘轹尊乃牛 签字日期：2 栅厂年月，尸日一签字日期：弘年月1 7 日 重庆邮电大学硕士论文 第一章绪论 1 1 引言 第一章绪论 时空信息是指与位置( 特别是地理位置) 和时间有关的信息，它在信息中占 有相当大的比例( 统计可以达到8 5 ) 。随着i t 技术的迅速发展，以g i s 为代 表的时空信息技术在各领域得到了应用，同时遥感等时空信息获取技术不断进 步，使得现代社会对位置服务和分析决策的需求也日益迫切，位置和时间是鉴别 和刻划信息的强有力方法，因为很多数据集都具有空间和时间的“印记”。因此深 入研究和掌握时空数据处理的理论与方法的重要性日益突显出来。正是应用的 需求推动了处理空间数据的空间数据库管理系统的研究。由于空间数据具有可视 性和数据量庞大的性质，所以必须提供从空间数据库中获得数据的时空索引。 数据库是为了访问和修改而组织的、需长时间保留的数据集合。数据库的能 力是由于知识和技术的结合，这是数十年研究开发的结果，并且已经嵌入到专门 的软件中，这个软件称作数据库管理系统1 2 l 。数据库管理系统是一个强有力的工 具，由韩国仁荷大学设计开发的g e o m a n i am i l l e n n i u ms e r v e r ( 简称为g m s ) 是数 据库技术、客户端n 务器技术、地理信息技术相结合的开放型空间数据库管理 系统，是为了能有效地存储并管理空间数据和非空间数据而开发的空间数据库管 理系统( s p a t i a ld b m s ) 。 g m s 数据库管理系统( g e o m a n i am i l l e n n i u ms e r v e r ) 具有如下特点： 1 ) 压缩通信方法使用 使用压缩方法把通讯数据最多可压缩到5 0 ，这样处理之后再传输数据可缩 短传送时间。 2 1 用户查询的优化执行功能 根据用户查询的形态提供多种形态的连接数据的路径，克服了现有的查询处 理方式的限度。 3 ) 支援大容量空间数据 在保存大容量空间数据时，不限制获得一个空间数据的大小，根据用户查询 的类型支援多样的索引结构。包括在一般的选择查询和空间运算符复合查询的情 况下，使用不同的索引结构并有效的执行查询处理。 g m s 现在已经实现传统的h a s h 树，b + 树等索引结构处理不同情况的非空间 数据，- 以及处理空间数据的r 树，但是还没有实现对时空数据的索引。对于本 重庆邮电大学硕士论文第一章绪论 课题的研究，就是要在空间数据库管理系统g m s 中实现对移动物体现在和将来 位置的索引。 本文主要研究空间数据库管理系统的核心技术时空索引t p 对l i n k l 3 】 树。有效的数据访问方式对空间数据库管理系统是必需的。研究时空索引 t p r * l i i l k 树重要的目的是快速访问一条特定查询所请求的时空数据，加快对移 动物体现在和将来位置的查找速度，而无需遍历整个数据库。 1 2 空间数据库索引t p r * 树简史 随着空间信息技术的广泛应用，迫切需要能处理空间数据和空间查询的辅 助索引结构。一个典型空间信息的应用是通过定位设备( 如g p s ) 跟踪移动物体 的运动轨迹。在过去的二十年，设计出一些空间访问方式。当前时空访问集中在 两个方向，一种是索引移动物体过去的位置，另一种是索引移动物体现在和将来 的位置。从2 0 0 0 年s s a l t e r d s 和c s j e n s e n 在世界上首次提出t p r 树【4 】( t i m e p a r a m e t e r i z e d r t r e e ) 作为对移动物体现在和将来位置的索引结构后，t p r 树得到 越来越多的关注。在对移动物体现在和将来位置的查询上，t p r 树无论在理论上 和实践上都优于p r 树【5 】、n s i 树【6 】、s t a r 树【7 1 。现在，围绕t p r 树索引结构 的空间查询、空间存储的研究都在展开。 随着空间数据库索引地不断发展，新的索引结构不断地产生。以下是一些重 要的发展过程： 1 9 8 4 年，g u t t m a n 提出r 树1 3 】。r 树数据结构是最早的专用于处理多维扩展 的索引之一。r 树是一个高度平衡树，它是b 树在k 维上的自然扩展。r 树 用对象的最小外包矩形( m b r ) 来表示对象。r 树对空间数据进行索引。 1 9 9 0 年，n b e c k m a n n ，h e k r i e g e l ，r s c h n e i d e r , 和b s e e g e r 提出r + 树 9 1 ；r + 树是r 树的一种变种。它对r 树的插入算法进行了改进。本质上，这些改进 目标是优化：( 1 ) 结点重叠，( 2 ) 一个结点的覆盖范围，( 3 ) 一个结点m b r 周 长。 2 0 0 0 年，s s a l t e n i s 和c s j e n s e n 提出，用t p r 树索引时空数据。 2 0 0 3 年，y t a o 提出了t p r * 树 i o 】，采用和t p r 树相同的索引结构和假定。和 t p r 树不同的是：t p r * 树没有用和r 树相同的插入和删除算法，而是提供了 新的和插入、删除相关的一系列算法。 1 3 国内外研究现状和研究内容 传统的数据库主要关注商务和管理应用这样的领域，它将重点放在高效、安 重庆邮电大学硕士论文 第一章绪论 全地处理大量相对简单的事务上【“】。普遍认为大部分现有的数据库管理系统无法 处理空间数据，或者在管理空间数据的时候难以使用。传统的索引无法处理对移 动物体位置查询的问题i l ”。比如 1 ) 时刻查询：q = ( r ，t ) ，返回在时刻t 位于r 内的所有移动点。 2 ) 窗口查询：q = ( r ，t m i 。，t 。) ，返回在时间段 t m l 。，t 。 内运动轨迹在r 内的 所有移动点。 3 ) 移动查询：q = ( r l ，r 2 ，t m i 。，t 。) ，返回运动轨迹包含在由连接t m i 。时刻的r 1 与 t 。a x 时刻的r 2 而形成的d 维不规则四边形内的所有移动点。 根据传统的数据库管理系统的假设，存储在数据库中的数据，除非有一个明 确的改变，否则数据是保持不变的。对于一些数据不连续变化的应用，传统的数 据库管理系统的索引模式是十分有效的。但是它却不适合数据持续改变的应用。 一个这样的应用是存储移动物体的位置。因为物体持续的改变位置，这样必须在 每个时间点更新数据库。考虑到这种大量的更新，传统的索引模式显然是无效的， 也是无法实现的。 因此必须重新定义数据库管理系统的功能。不能再将d b m s 看成是一个完全 封闭的数据储藏库，而是多系统的计算环境中一个活跃的组成部分。而旧式数据 库结构也不足以处理空间数据。这样，持续运动对数据库技术提出了新的挑战。 与时俱进，适合于处理空间数据的数据库孕育而生。g m s 就是这样一个空 间数据库管理系统。s t o r m n t 是它的存储管理器。它现在已经实现了对移动 物体现在位置的索引。但是由于在索引结构中没有引入时间维概念，没有适合的 索引结构，因此不能实现动态的对移动物体现在和将来位置的查询。 t p r * 树就是有可能实现这个功能的索引结构。理论上通过这种索引结构可以 在s t o r m n t 中实现对移动物体现在和将来位置的索引。但是移动物体更新频 繁，可以提高索引操作性能的右链结构还没有被引入，目前学术界还没有相关的 文章发表，因此就要对t p r * 树的索引结构进行相应的修改。 目前，还有一些方法，虽然支持对移动物体现在和将来位置的查询，但是有 的在表示物体轨迹时最小外包矩形浪费空间太多。有的在初始空间转换成双空间 进行多边形范围查询时算法过于复杂。 因此，本文选择t p r * 树作为基本的索引结构，对其进行深入分析，针对上 面提到的问题，形成t p r * l i n k 树，在空间数据库管理系统g m s 中，实现对移 动物体现在和将来位置的查询。 本文研究的主要内容包括； 第一，研究g m s 中存储管理器s t o r m n t ，理解并会应用s t o r m n t 中和索 引相关的结构定义、接口函数、调用机制。 重庆邮电大学硕士论文第一章绪论 第二，通过阅读s t o i r m ，n t 中和空间索引r 树相关的源代码，详细分析和r 树 相关的其它模块的接口关系。因为要在s t o r m ，n t 中实现t p r * l i n k 树 必须首先了解索引如何在空间数据库管理系统中实现，以便了解要对索引 进行哪些相关操作。 第三，t p r * 树没有加入右链结构，要考虑引入这种结构后，对查找、插入、删 除算法的影响。 第四，在s 1 d r m ，n t 中设计并实现t p r * 一l i n k 树。使得在现有s 1 o r m 仆t 系 统的基础上，实现对移动物体现在和将来位置的查询。 1 4 论文组织结构 本文共分七章，各章的内容安排如下： 第一章主要介绍国内外研究现状和研究意义。 第二章主要介绍时空索引的基本概念和基础理论。 第三章分析和比较几种索引移动物体现在和将来位置的典型索引结构，分 析的目的是了解当前索引的现状、优势、缺陷，从中选取最佳方案。 第四章详细分析了t p r * 树的索引结构，索引操作。t p r 树在索日l 移动物 体时的主要优势以及存在的问题。 第五章给出t p r * l i n k 树的索引结构的设计，查找、插入算法以及相关证 明。 第六章实现t p r * l i n k 树的基本操作，包括添加的数据结构、s t o r m ，n t 接口函数、实验结果和性能分析。 第七章总结。 重庆邮电大学硕士论文第二章时空索引的基础理论 第二章时空索引的基础理论 从空间数据库中获得时空数据的有效方法，经常是通过使用时空索引完成 的。它可以用来快速访问一条特定的时空查询所请求的数据，而无需遍历整个数 据库。 2 1 时空索引的概念 索引文件是用来提高数据文件查询效率的辅助文件。时空索引是从空间数据 库中获得数据的有效方法。时空索引用一组桶( b u c k e t ) ( 通常对应二级存储的页 面) 来组织对象。每个桶有一个关联的桶区域，即包含了存储在桶中全部对象的 一部分空间。桶区域通常是矩形的。对于点数据结构来说，这些矩形数据结构是 不相交的，它们将空间分成每个点正好属于一个桶。对于一些矩形数据结构来说， 桶区域可能是交叠的。通过引入时间维表示每个对象的动态属性。 2 2 时空索引主要特点 时空索引要处理的数据具有：数据量大、多维和随时间变化的特点。 空间数据库管理系统就是为处理海量空间数据而设计的。时空索引也不例 外。空间数据的一个低分辨率的美国卫星图像就会消耗3 0 兆磁盘的空间。正是 因为空间数据量太大，它甚至都不能用一个中等规模的二级存储来装载，数据会 溢出到三级存储中。读取数据时花费在访问随机存储器和磁盘的时间是不可同日 而语的：前者大约是后者的十万分之一。这个比率还在逐年降低。时空索引的设 计必须能迅速找到需要查询的数据，尽量减少内存和磁盘问的访问速度。 空间数据一般都是二维或更高维的。传统索引的实现主要依赖于索引域排序 而存在。空间数据如果分类和排序，就会丢失空间的相邻性。如图2 1 所示：图 中有一个按行排序的网格。现在考虑4 的相邻数字，在这个网格里4 的相邻数据 是3 、7 和8 ，但是如果按照排序的顺序来存储，它的相邻数字就成了3 和5 。因 而，排序会破坏原有的相邻关系。值得一提的是，没有哪一种全排序可以安全保 持空间的相邻性。由于多维空间不存在自然排序，在关系数据库管理系统中用的 最广泛的索引b 树，也就无法直接用于创建空间对象的索引。为了避免空间对 象在自然排序方面的不足，必须从根本上修改b 树的思想，以适应扩展的空间 对象。r 树的数据结构是最早的专用于处理多维扩展对象的索引之一。 重庆邮电大学硕士论文第二章时空索引的基础理论 l2 3 4 5678 9l ol l1 2 1 31 1i s1 6 图2 i 对多维数据的行排列 时空数据是随着时间不断变化的，或者是速度的大小，或者是速度的方向。 2 3r 树的索引结构 基于数据分区的时空索引都是在r 树基础上发展的。索引r 树( 区域树) 是 一种利用b 树的某些本质特征来处理多维数据的数据结构。b 树的结点有一个键 的集合，这些键把线分成片断，沿着那条线的点仅属于一个片断。如图2 2 所示。 b 树因此很容易地找到点。如果把沿线各处的点表示成b 树结点，就能够确定点 所属的唯一子结点，在那里可以找到该点。 _ _ _ h 图2 2b 树结点沿线把键分成不相连片段 另一方面，r 树表示由二维或更高维区域组成的数据，称为数据区。一个r 树的内结点对应于某个内部区域，或称“区域”，它不是普通的数据区。原则上， 区域可以是任何形状，虽然实际中它经常为矩形或其他简单形状。r 树的结点用 子区域代替键，子区域表示结点的子区域的内容。如图2 3 显示了一个与大矩形 相关联的r 树的结点。虚线表示的矩形表示与它的子结点相关联的予区域。子 区域没有覆盖整个区域，只要把位于大区域内的所有数据区都完全包含在某个区 域中就合乎要求。进一步说，尽管希望部分重叠更小，子区域允许有部分重叠。 r 树中的最小外包矩形用来表示对象。r 树有以下几条特性： 1 ) 每个叶结点包含m 至m 条索引记录( 其中m t 。f 的任何时刻，移动物体的位置可以通过公式( 3 2 ) 来计算 x f = x 阿+ v ( f f 阿) ( 3 2 ) 为了简化起间，假设物体在一维空间中运动。物体的运动可以通过线性公式 ( 3 3 ) 表示 x ，= a t + b( 3 3 ) 其中a 和b 是常量，a 表示物体的速度，b 表示物体的起始位置。 3 1 初始的时空空间方式 将公式( 3 3 ) 表示成二维坐标，横坐标表示时间，纵坐标表示位置，这样在 时空域内得到一系列线段。索引将来的位置转换为索引一系列的二维线段【旧。 o 重庆邮电大学硕士论文 第三章现有方案的分析与比较 3 1 1p m r - - q u a d t r e ef o rm o v i n go b j e c t t a y e b e ta 1 ”1 的主要思想是当移动物体的更新发生时，整个索引结构被摧毁， 根据给定的信息再重建索引树。为了避免更新过度频繁，每过t 时间段，重建 一次索引。抽象地说，无限的时间维被分成相等的时间片，每个时间片的长度为 a t 。对于每个时间片，根据公式( 3 _ 3 ) 一个新的p m r - - - q u a d t r e e i l s 】树被建。然 而，由于存储限制，仅仅当前的p m r _ q u a d t r e e 树被存储。 一 3 1 2 该方案的不足 一般来说，这种索引方式有两个主要的缺陷： 1 1最小的m b r 表示轨迹会造成大量的死空间。 2 )因为所有的轨迹有相同的时间计算点，数据不够精确。 3 2 转换方式 为了避免时空索引在时空域上的缺陷，时空域被转换成另外的空间。这种新 的空间访问表示方法可以更简单的查询数据。 3 2 1d u a l i t y 转换 通过d u a t i t y 转换9 l ，时空域中的一条线段( 比如：轨迹) 被转换成二维空 间中的一个点。这种方式的主要思想是在双二维空间中，通过二维的坐标点( a ，b ) 表示公式( 3 3 ) 。其中这个速度a 是水平坐标轴，参考位置b 是垂直坐标轴。因 为在双空间中数据分配有很高的灵活性，基于空间索引( 比如，l s d 树【2 0 j ) k d 树取代了r 树；r 树在方形区域中聚簇数据，仅仅在速度维上进行分裂。而k d 树在二维上进行分裂。在时空空间中的范围查询被转换成为双速度位置空间中的 多边形查询。 3 2 2s v m o d e l s v m o d e l f 2 。1 是一种很特别的方法，并不通过轨迹表示移动物体。一个移动物 体通过四个参数来建模( s ，e ，t 。，v 。) ，他们分别表示起始位置、终止位置、开始 时间和初始速度。四个参数中只能两个参数改变它们的值，这样存在六种不同的 组合。在这些组合中，最好将初始位置s 和初始速度v 。作为常量。在这样的双 。： + 1 1 重庆邮电大学硕士论文 第三章现有方案的分析与比较 空间中，开始时间ts 作为水平轴，终止位置e 作为垂直轴。范围查询被转换成 在双空间中的多边形查询。这个双平面由s s 树 2 2 】来索引。假设所有的移动物体 有着相同的起始位置，这通过设置所有移动物体运动都从0 开始来实现的。对于 速度常量，这种假设运用于高速公路是比较现实的。如果速度发生变化，速度被 量化成离散的值。其中每一个值，用一个单独的索引结构。 3 2 3p s i p s i 方式是用r 树索引2 d + 1 维空间，2 d 维表示参考位置x 。f 和速度v ，1 维 表示时间t 。移动物体的运动通过2 d + l 维轨迹来建模。这种方式的主要思想是在 时间段 ts ，tc 】，移动物体的运动轨迹被存储在索引中，移动对象没有统一的参 考时间。 3 2 4 转换方式的不足 转换技术有三个主要的缺陷： 1 ) d u a l 空间不能得到p r i m a l 空间中的所有信息。 2 ) 不能确保在p r i m a l 空间中彼此接近的物体在d u a l 空间中仍然保持这种位 置关系。 3 ) 在p r i m a l 空间中的范围查询总是需要转换为d u a l 空间中的多边形查询，计 算量很大。 3 3 带参数的空间访问方式 空间访问方式的新的倾向是索引带有参数的m b r 的初始时空空间。 这种方式的主要思想是给m b r 时间参数，这样m b r 会随着它包括的移动 物体的运动而运动。在这种建模方式下，对于任何查询，可以通过这种索引结构 来计算和估算。 3 3 1t p r 树 这种方案的主要思想是在r 树的基础上，用带有时间参数的m b r ，也就是 保守的m b r 。它包含了移动物体。保守m b r 的下限是包含的移动点的最小速 度，而上限是移动点的最大速度。在这种限定下，保守m b r 永远不会缩小，这 样保证了总是包含所包括的移动物体。为了避免m b r 变得很大，当移动物体更 重庆邮电大学硕士论文 第三章现有方案的分析与比较 新时，在到达移动物体o 所在的叶子结点的路径上的所有m b r 需要重新计算。 3 3 2 口r + 树 t p r + 树采用和t p r 树相同的结构和假设。和t p r 树不同的是，它没有采用 r 树的插入和删除算法，而是采用了新的插入、删除算法，目标是优化查询性能。 3 4 本章小结 本章对当前的时空索引移动物体现在和将来位置的索引结构进行了分析和 比较，t p r + 树采用了带有时间参数化的m b r 。这样可以保持移动物体的初始空 间，减少了信息损失和复杂的转换。对于任何查询，可以通过这种索引结构来计 算和估算。相比t p r 树，在插入和删除时，有着更小的花费代价。 又因为在s t o r m n t 系统中，已经存在r 树，系统的一些数据结构和存储 方式也可以直接应用于t p r * 树。 所以目前，t p r * 树是一种比较好的建模方式，可以在此基础上进行进一步研 究和开发。 重庆邮电大学硕士论文第四章时空索引t p r * 树的分析 第四章时空索引t p r * 树的分析 由上一章的内容可知，r 树数据结构是最早的专用于处理多维扩展对象的索 引之一，t p r * 树就是在r 树的基础上发展而来的。对移动物体现在和将来位置 进行有效的查询，它是当前唯一的理论上可以用于实践的空间索引结构。这个技 术能索引一维、二维、多维的移动物体。 在索引移动点将来的轨迹时，在可能的方式当中，有以下几个不同之处： 按照索引的空间不同，可能有几种不同的方式。假设这个物体在d 维空间( d = 1 ，2 ，3 ) 运动，它们的轨迹可能在( d + 1 ) 维空间上被索引为线型。作为一种 可选的方式，可以在更高维空间中，绘制这些轨迹成点坐标，然后进行索引。 另一种可选的方式是在d 维空间中索引数据。可以通过速度矢量参数化索引 结构，这样能使索引在将来的任何时间被“看到”。t p r * 树选择了后者，缺乏 适合的转换技术限制了前一种方式。 索引对数据还是空间进行分区。如果是在运动空间中索引数据，基于数据分 区的索引看起来更适合一些。在另一方面，如果在d + 1 维空间中索引线型轨 迹，如果不对基于数据分区的索引进行处理，可能造成分区大量覆盖。 索引需要的数据复制的程度不同。复制可以改善查询性能，但影响更新性能。 索引移动物体现在和将来的位置时，数据最大的特点，就是更新频繁。t p r * 树并不使用复制特性。 索引是否需要周期性的重建。有些方式只是个别的索引在某个时间段发挥作 用。对于这种方式，当原来的索引不在发挥作用时，新的索引必须被提供。 另一些方式，原则上一个索引可以无限的使用，可以对它在某个时间点进行 优化，但随着时间继续，也许会发生恶化。t p r * 树属于后一种方式。 4 it p r * 树的索引结构 t p r * 树作为空间数据库的索引，用于跟踪移动物体现在和将来的位置。t p r + 树是分级的、高度平衡的索引结构，是对r 树的扩展。在t p r * 树中，一个移动 物体0 表示为最小外包矩形( 1 ) m b r ：o r _ ( x i - ，y l + ) ，( x 2 ，y 2 + ) ) ，也就是在参考时间t # 。f 的一个区域，( 2 ) 速度外包矩形v b r ：o v = o v l - , o ，1 + ，o v 2 ，o 。2 + ) ，o v i + ( o v i ) 表示物体 的速度在沿着第i 维方向的上界( 下界) ( 1 1 i s 2 ) 。 在一维空间中，一个移动点的位置可以通过一个参考位置和一个相应的速度 1 4 重庆邮电大学硕士论文 第四章时空索引t p r * 树的分析 矢量( x ，v ) 来表示。其中参考位置为x = x f ) 。随着时间的推移，位置表示为 x ( 0 - - - x ( t m 0 + v ( t - t o ( 4 1 ) 表示d 维空间的移动点，在d 维空间的外包矩形也是时间参数化的，比如， 它们在每一维上的坐标都是时间参数化的。一个时间参数化的最小外包矩形包含 了不早于当前时间的所有的点和矩形。 随着时间的推移，一个m b r 应该有多大才能跟踪它所包含的所有的点和子 结点矩形。这一直是人们研究的问题，希望能有一个折衷的方案。最理想的状态 是时间参数化的m b r 总是最小，但这样带来的存储代价太大。如图4 1 所示， 一个结点是由两个相向运动的点a 和b 组成的。a 和b 是一维的。其中，a 和 b 表示在某个时间点最小外包矩形的上界和下界坐标。 产o t 岛 a f ， 孔 一 b 图4 1 保守的( 虚线) 和总是最小化的( 实线) 时间段范围比较 替代总是用最小外包矩形，在t p r * 树中用保守的最小外包矩形。保守的最 小外包矩形在某个时间点是最小化的，但随着时间点的推移也许就不是最小化 的。对于一维空间，这个保守的最小外包矩形的下界是它所包含的所有点的最小 值，上界是它所包含的所有点的最大值( 速度可以是正的或负的，取决于物体运 动的方向) ，这意味着采用这种方式时，必须限定修改最小外包矩形的保守边界。 在时间点0 ，这个保守边界的左边在物体a 的位置，右边在物体b 的位置。 保守边界是不会缩小的。最好的情况是最小外包矩形里包含的所有点速度相同， 那么保守边界就是常值。 下面通过公式来表示移动点的保守边界。时间化的参数边界表示为 x - ( 0 ，x + ( t ) 】_ x ( t 1 ) + v - ( t - t 0 ，x + ( t 1 ) + v + ( t - t , ) 其中 x 一5 x ( t i ) 2 m i n i o i - x - ( t 0 ) x + = x + ( t i ) 2 m a x i o i x + ( t 1 ) ) v 一2 m i n i o i v v + = m a x i o i v + 公式中，移动点o j 选取的范围就是保守边界的范围。实际应用中，用适合的 移动点o i 来表示保守边界。用o i x ( t 1 ) 和o i x 十( t i ) 替代o i x ( t 0 ，用o i v 和o i v + 替代 o ；v 。 卜 卜 - 内妒 a 重庆邮电大学硕士论文 第四章时空索引t p r * 树的分析 保守边界是时间参数化的，包括不在t 。之前的所有时间。虽然保守边界是不 会缩，j 、的，但实际上它有可能增长很快。适当的调整保守边界是必要的。因为 t p r + 树是对移动物体现在和将来位置的查询，所以选择任何移动点和矩形更新 时，调整保守边界是可能的。 x 一2m i n i o i x - ( t u n ) ) 一v ( t u p d t 1 ) ) ( 4 2 ) x + = m a x l o i x + ( t u p d ) ) 一v + ( t u p d t j ) ) ( 4 3 ) t 。d 是更新时间，这种界定边界的方法被称为更新保守边界。如图所示：粗 的实体黑线是参考点的保守边界，细的实体黑线四个移动物体的运动轨迹，在时 间点t u p d ，一个更加短的又可以包含所有移动物体的保守边界被确定( 在t i l d d 点 垂直与时间轴的粗的虚线) 。 o k 口d 图4 2 移动点载入时间( 粗线) 和更新时间的时间段范围 移动物体的结构为( i d ，x i ( t 。0 ，v i ) 图4 3 ( a ) 举出a , b ，c ，d 四个移动物体的m b r s 和v b r s ，箭头和数字表示它们 速度的方向和大小，其中负值表示速度朝着坐标轴的负方向。移动物体a 的v b r 是a v = 1 ，l ，l ，l ( 前面两个值是沿着x 轴方向的，后面两个值是沿着y 轴方向的) 。 移动物体b , e ，d 分别是b y = 2 ，2 ，2 ，2 ) ，c ，= 2 ，0 ，0 ，2 ) 和d v = l ，1 ，l ，1 ) 。这些移动物体组 成两个叶子结点n bn 2 。n 1 ，n 2 的v b r s 分别是n l v _ 2 ，l ，2 ，1 ) 和n 2 v = 2 ，0 ，1 ，2 ) 。 图4 3 ( b ) 表示这些m b r s 在时间戳l ( 注意每一边按照它们的速度矢量移动) 。 在t p r * 树中，中间结点总是包含它的子树中的所有对象，但不一定是紧紧外包。 比如：在时间戳1 ，n l ( n 2 ) 比a , b ( c ，d ) 的最j , # b 包矩形要大。 一个预期的w i n d o w 查询按照对树的方式进行，除了在查询时间里动态的计 算m b r s 。比如：如果查询q r 在时间戳1 的位置，n l 和n 2 都将被访问( 虽然在 时间戳0 时，q r 并没有和n l 、n 2 相交。 蔓壅坚皇奎兰璺圭笙奎星婴彳_彳 ( a ) m b r 5 v b r s a t 沁o 4 2 t p 对树的操作 ( b ) m b r s a t t i m el 图4 3t p r + 树的结点 不等边的保 对于一维空 查 一l 、 检 k ， 艄 h一 黔冰一澌 篆一 出。黼m 耋l 吣剐+ + 州 鬈黧 对蹈 睬 2 跨 薛 磊a 一一 重庆邮电大学硕士论文第四章时空索引t p r * 树的分析 间，查询是相对简单的。对于更高维的空间，一个更简单而有效的算法被设计。 这个算法建立在移动矩形相交的基础上。随着它们的运动，在某个时间点， 在每个维它们都相交。这样，任意维j ( j = 1 ，2 ，d ) ，这个算法计算这个时间段i i = 【t j - ，q + 】c t _ ：q 。如果i = n d j _ l ，b = o ，这两个移动矩形并没有相交，并且返 回空值，否则，这个算法提供了当它们相交时的时间段i 。在每一维上的时间段 按照如下公式计算。 。 l i - 矿 。j 一 。+ ( f 一，n 口，一( f + ) 。+ ( + ) u 口一 x ，一( 一) n 口p ( + ) 。，一( f + ) ( 4 5 ) f ，一，t j + 】 o t h e r w i z e 在条件表达式中并的左半部分表示q 在r 的上面，右半部分表示q 在r 的 下面。下面是t j ，0 的公式。 ，+ ：! ：! 二! ： 。 ”i 一一、i ，+ ! 二! ：! 二! 一 wi + 一vi f i f 。j + ( t 一) 。，一( t 一) 0 t h e r w i z e ( 4 6 ) 这里，第个条件是在时刻l ，q 在r 上面。第二个条件，q 在r 下面。 ，一+ 三! ：二竺：1 1 9 ，一一”+ ，+ ：! ：! 二! ! w ，+ 一一 t + i f 。j + ( t + ) n 的右兄弟n 的l s n ( i ) 。子结点n 可以通过n 的 右链到达。如图5 3 所示，n o d e 2 的项e n t r y z 的l s n ( z ) l s n o d e 4 ) 且与 l s n ( n o d e 5 ) 相等。n o d e 5 可以通过n o d e 4 的右链到达。n o d e 5 在父层中还 没有项。这种情况是由于n o d e 4 结点分裂产生的，它将通过完成这次分裂 反映到父层上。 n o d e3 图5 3 个t p r * - l i n k 树的一部分 7 通过引入这种右链机制： 1 ) 在查找操作时，即使这时有插入操作，可以从右链中得到所需结点，因此可 继续查找，不会改变树的结构。 2 ) 在插入操作时，遍历过程不用加锁，结点分裂时，先和原来结点通过右链相 连，在合适的