（计算机应用技术专业论文）时空数据库中移动对象索引技术研究.pdf

重庆邮电大学硕七论文摘要 摘要 时空数据库是存储、管理随时问变化，其空间位置或范围也发生变化 的时空对象的数据库系统，时空索引技术是时空数据库管理系统的关键技 术之一。时空索引技术是空间索引技术和时间索引技术的结合，它必须兼 顾时空对象的空间特性和时间特性，才能有效地提高时空数据库的存取效 率。随着应用领域的不断扩展和新技术的出现，尤其是随着移动计算、无 线通信及定位技术的发展，如何有效地对移动对象进行查询、管理以及提 供准确的基于位置服务等应用需求使得时空数据库研究面临着新的挑战， 对移动对象索引技术的研究具有重要的意义。 在分析目前主要的空间和时间索引技术的基础上，研究了时空数据的 存取方法，对已提出的时空索引技术进行了分类、比较。目前移动对象索 引技术要么只能支持历史查询，要么只能支持当前和未来查询，支持的查 询类型十分有限。根据位置服务中移动对象不断变化的特点，提出历史 t p r t r e e ( h t p r * t r e e ) 作为位置服务中对移动对象的时空索引结构，该 索引结构采用两级索引机制：首先采用t p r * t r e e 索引结构对不同时间片 的时空对象建立索引，然后用有序表按时间递增顺序存储不同的时间片信 息。从而可以实现整个历史空间( 过去、当前和未来) 上的窗口查询和移 动窗口查询。由于引入了双时间( 事务时间和有效时间) ，对暂态t p r * t r e e 的插入、删除、更新和查询算法进行了相应的改进。通过理论分析和实验 测试，h t p r * t r e e 可以在减少更新代价和磁盘开销的同时，保持高效查询 效率，支持整个历史空间上的窗口查询和移动窗口查询，查询性能只与时 间片上移动对象的数目有关，而不随时间的递增而增加。 关键词：时空数据库，移动对象索引，时空索引，时空存取方法 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t s p a t i o t e m p o r a ld a t a b a s e i st h ed a t a b a s em a n a g e m e n ts y s t e mt h a t m a n a g e ss p a t i o t e m p o r a lo b j e c t s ，w h o s es p a t i a lp o s i t i o no rr a n g ei sc h a n g e d a l o n gw i t ht i m eg r o w i n g ，s p a t i o t e m p o r a li n d e x i n gt e c h n o l o g yi st h ek e y t e c h n o l o g yi ns p a t i o - t e m p o r a ld 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 i n gt e c h n o l o g y c o m b i n e st h es p a t i a li n d e x i n ga n dt i m ei n d e x i n gt e c h n o l o g y i tm u s tc o n t a i n t h es p a t i a lt r a i ta n dt i m et r a i to fs p a t i o t e m p o r a lo b j e c t s w i t ht h ee x t e n s i o n o ft h ea p p l i c a t i o nd o m a i n sa n dt h ea d v a n c i n go fw i r e l e s sc o m m u n i c a t i o n sa n d g e o p o s i t i o n i n g ，l o c a t i o nb a s e ds e r v i c e sw e r ee m e r g i n g h o wt om a n a g ea n d q u e r yt h em o v i n go b j e c t si s ac h a l l e n g ei ns p a t i o t e m p o r a ld a t a b a s e h e n c e i n d e x i n gt e c h n o l o g yo fm o v i n go b je c t si st h ek e yt e c h n o l o g yt os o l v et h e s e p r o b l e m s o nt h eb a s i so fs p a t i a li n d e xa n dt i m ei n d e xt e c h n o l o g i e s ，i nt h i st h e s i s ， s p a t i o t e m p o r a la c c e s sm e t h o dw a sr e s e a r c h e d ，t h ea l r e a d yp r o p o s e di n d e x t e c h n o l o g i e s w e r ec l a s s i f i e da n d c o m p a r e d b yf a r ，t h ee x i s t i n g s p a t i o t e m p o r a li n d e x i n gt e c h n o l o g i e se i t h e rs u p p o r th i s t o r yq u e r y , o rs u p p o r t t h ep r e s e n ta n df u t u r eq u e r y , t h eq u e r yt y p e sw h i c ht h e s em e t h o d ss u p p o r ta r e l i m i t e d a c c o r d i n gt ot h et r a i to fm o v i n go b j c o t si nl o c a t i o nb a s e ds e r v i c e s ，a n e wi n d e xs t r u c t u r ec a l l e dh t p r 。- t r e e ( i e h i s t o r yt p r 。t r e e ) w a sp r o p o s e d i tu s e st w o - l e v e li n d e x i n gm e c h a n i s m ：f i r s t ，t h et p r + 一t r e ei n d e xs t r u c t u r e w a su s e dt oi n d e xt h em o b i l eo b j e c t so fd i f f e r e n tt i m ei n t e r v a l ，t h e nl i n e a r l i s t w a su s e dt or e c o r dt h et i m ei n t e r v a li n f o r m a t i o no r d e r l y i ts u p p o r t st h e w i n d o wq u e r ya n dm o b i l ew i n d o wq u e r yi nt h ew h o l et i m er a n g e ( p a s t ， p r e s e n ta n df u t u r e ) b e c a u s eo fd o u b l e t i m e ( t r a n s a c t i o nt i m ea n dv a l i dt i m e ) w a si n t r o d u c e di n ，t h ea l g o r i t h m so fo p e r a t i o n si nt h i ss t r u c t u r ew e r ed e s i g n e d t oa d a p tt h i s ，s u c ha si n s e r t ，d e l e t e ，u p d a t ea n dq u e r y a c c o r d i n gt oo u r t h e o r e t i ca n a l y s i sa n de x p e r i m e n t s ，h t p r + t r e ei n d e x i n gs t r u c t u r ec a nr e d u c e t h eu p d a t ec o s ta n ds t o r a g ec o s t ，w h i l ek e e p i n gt h eh i g hq u e r yp e r f o r m a n c e ， a n ds u p p o r t i n gw i n d o wq u e r ya n dm o v i n gw i n d o wq u e r yi nt h ew h o l eh i s t o r y r a n g e t h eq u e r yc o s ti sr e l a t e dw i t ht h en u m b e ro fm o v i n go b j e c t si nt h et i m e i n t e r v a l ，b u tn o tw i t ht h eg r o w t ho ft i m e i i 重庆邮电大学硕士论文a b s t r a c t k e yw o r d s ：s p a t i o - t e m p o r a ld a t a b a s e ，m o v i n go b j e c t si n d e x i n gt e c h n o l o g y , s p a t i a l t e m p o r a li n d e x i n g ，s p a t i o t e m p o r a la c c e s sm e t h o d i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆 邮电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者龇私l 签字日期：弘一 年6 月易日 学位论文版权使用授权书 本学位论文作者完全了解重麽整电太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权 重庞邮电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：每击l 4 i 导师签名： 签字只期： w 7 年6 月凸日签字日期：z 呷年6 月占日 重庆邮电大学硕士论文第一章绪论 第一章绪论 1 1 研究背景及研究内容 随着计算机技术和信息技术的飞速发展，越来越多的数据库系统需要 存储和管理大量现实世界中带有时空信息的物理对象，这些对象占有一定 的空间位置和范围，并且它们的空间位置或范围的大小会随着时间的变化 而发生变化。但长期以来，空间数据库与时间数据库一直是两个相互独立 且都很重要的数据库研究领域：空间数据库主要研究空间对象的表示、存 储、处理与查询；时间数据库重点研究如何表示和处理数据库中随时间变 化的数据，且通常是传统数据。目前数据库领域的研究人员逐渐认识到应 集成物理对象的时间、空间属性，研究包括时白j 和空间要素在内的数据库 系统，即时空数据库( s p a t i o t e m p o r a l d a t a b a s e ) 。时空数据库的目的是存 储和管理随时间而变化的空间数据。时空数据库技术是t g i s ( t e m p o r a l g e o g r a p h i ci n f o r m a t i o ns y s t e m 时间地理信息系统) 的核心支持软件，对时 空数据库的研究将大大推动t g i s 的进一步发展，其研究成果也可应用于 c a d 、v l s i 和多媒体数据库等多个领域。 随着应用领域的不断扩展和新技术的出现，尤其是随着移动计算，无 线通信及定位技术的发展，如何有效地对移动对象进行查询、管理以及提 供准确的基于位置服务等应用需求使得时空数据库研究面临着新的挑战， 移动对象数据库成为一个研究热点。 移动对象管理技术在许多领域展现了广阔的应用前景。在军事上，移 动对象数据库可以回答常规数据库所无法回答的查询；在民用领域，利用 移动对象数据库技术可以实现智能运输系统、出租车警员自动派遣系统、 智能社会保障系统以及高智能的物流配送系统。此外，移动对象管理技术 还在电子商务领域有着广泛的应用前景。值得一提的是，随着3 g 商用的 推进，位置服务将成为各运营商新的业务增长点，移动对象数据库技术 的应用前景将会越来越明显。 目前，移动对象管理主要研究问题包括： 1 ) 位置的表示与建模：为了对移动对象的位置进行行之有效的管理， 移动对象数据库系统必须能够准确地获取移动对象的当前位置信息( 位置 重庆邮电大学硕士论文 第一章绪论 信息的获取) ，并建立有效的位置管理模型( 位置信息的表示) 。 2 ) 移动对象索引技术：在移动对象数据库中，通常管理着数量非常 庞大的移动对象。在查询处理时如果逐个扫描所有的移动对象显然将会极 大地影响系统的性能。为了减小搜索空间，就必须对移动对象建立有效的 索引。 3 ) 移动对象及静态空间对象的查询处理：移动对象数据库中的查询 目标分为两种：一种是移动对象( 如汽车、移动用户等) ，另一种是静态 空间对象( 如旅馆、医院等) ，对这两类数据的查询各自需要相应的索引 结构的支持。移动对象数据库中的查询具有位置相关的特性，即查询结果 依赖于移动对象当前位置，同一个查询请求，其提交的时间、地点不同， 返回的结果也将不同。典型的查询包括区域查询( 查询某个时问段处于某 个地理区域的移动对象) 、k n n 查询( 查询离某一点最近的k 个移动对象) 以及连接查询( 查询满足条件的移动对象组合) 等。 4 ) 位置相关的持续查询及环境感知的查询处理：在移动对象数据库 中，另一类重要的查询是位置相关的持续查询( 1 0 c a t i o n d e p e n d e n t c o n t i n u o u sq u e r y ，简称l d c q ) 。位置相关的持续查询是指在某个时间区 间内持续有效的查询，在该时间区间内，由于移动对象位置的改变，查询 的结果也在不断变化，系统需要随时将查询结果的变化信息传递给查询用 户，使得用户能够实时监控最新的查询结果。例如，在高速公路上行进的 救护车可以提交一个持续查询：“请在未来2 0 分钟之内随时告诉我离我最 近的医院”，用户将在未来2 0 分钟的行程中不断地收到离救护车最近的医 院的查询结果。 本文主要总结了以往移动对象索引技术研究的成果，分析了它们的各 种特点及其需要改进的地方，提出了一种能够支持移动对象过去、现在和 未来位置查询的时空索引结构。 1 2 国内外研究现状 如何设计并建立一个有效的时空数据库系统来存储时空数据和建立 一个高效率的时空数据索引已经成为一个热点与难点。 近年来，时空数据库一直是数据库领域的一个研究热点。在国外，有 众多的研究机构、大学和公司进行时空数据库技术的研究：基于欧盟的 c h o r o c h r o n o s 项目是一个着力解决时空数据库管理系统设计、实现和 应用的研究网，其成员来自欧盟各著名高校和计算机研究机构，他们组建 2 重庆邮电人学硕士论文第一章绪论 了许多研究小组，这些小组大部分至今仍在专门从事时间、空间以及时空 数据库的研究，它自1 9 9 6 年启动以来，在时空数据库方面的研究成果令 人瞩目；市场中已有m a p i n f o 、a r c ，i n f 0 等实用g i s t g i s 系统；很多 新的技术都已应用在像g e o + + 、q l g 等一大批实验系统中；当前一些主 流关系型数据库系统供应商( 如o r a c l e 、i n f o r m i x 、s y b a s e 等 都开始提 供具有空间、时空数据处理功能的数据库管理系统：数据库领域的国际著 名学术会议如a c ms i g m o d 、a c mp o d s 、v l d b 、i c d e 和c i k m 等都 将时空数据库的研究作为一个重要主题，同时国际上还有专门的时空数据 库学术会议如s s t d ，m m d 和a c mg 1 s 等。 从8 0 年代开始，我国在一些行业和领域着手建设g i s 及t g i s ，经过 1 0 多年的努力，建立了一批全国、省市和区域一级的数据库及大型应用系 统，如全国l ：1 0 0 万基础地理信息库、重大自然灾害监测与评估系统、三 北防护林系统、重点产粮区主要农作物估产系统、中国历史地理信息系统 ( c h g i s ，c h i n e s eh i s t o r i e a lg 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 i s 基础软件的整体设计水平己经接近国外水平，如中国地质大学研制的 m a p g i s 系统、武汉测绘科技大学研制的g e o s t a r 系统等。目前国内开展 空间数据库、时空数据库研究的机构还不多，主要集中在几所大学和中科 院部分研究所：北京大学将空间数据库作为一个重点研究课题；上海复旦 大学进行了g i s 中数据库技术的研究；武汉测绘科技大学也在进行空闻数 据库和时空数据库的研究工作。 i 3 论文的预期目标和工作内容 时空数据索引机制是保证时空数据库快速访问及有效处理时空数据 的关键技术。传统的基于b t r e e 的索引结构由于只能处理一维的传统数据 在此已不再适用，必须要研究出一种支持多维数据存取、高性能的索引机 制，以高效管理空间、时间以及时空数据，实现时空数据库对时空对象的 存储、管理并且满足各种时问、空间操作复杂度的要求。 本课题作为实验室合作项目一基于t d s c d m a 的定位服务器的研究 与开发中的一个重要部分，其目标是在跟踪目前时空索引结构的基础上， 设计与实现对移动对象进行有效管理的时空索引机制，即研究与实现多维 数的、高性能的时空索引结构，并实现在该数据结构基础上各种常用操作 算法，以满足支持时空对象高效存取、查询的需要。该索引机制应从时间、 空间复杂性方面尽量提高各种常用操作算法性能，减少系统丌销。 重庆邮电大学硕士论文 第一章绪论 本课题的具体研究内容包括： 1 ) 在收集、整理和消化国内外最新数据库尤其是时空数据库索引技 术的基础上，设计满足时空索引机制要求的时空索引结构h t p r * t r e e 以及 在此结构基础之上的各种操作算法； 2 )在w i n d o w s9 8 2 0 0 0 操作系统开发环境下用v i s u a lc + + 6 0 作为 开发语言实现该索引机制，即完成以下应用程序的设计与编程工作： h t p r * t r e e 时空索引结构的建立、时空对象的有效存取和查询( 包括历史 的，当前的和未来的信息) 、插入、删除、更新等基本操作并进行性能分 析。 1 4 论文结构 本文共分六章，各章的内容安排如下： 第一章为绪论，介绍了论文的研究背景，包括时空数据库国内外研究 发展现状、研究内容，对课题的研究目标和内容也作了阐述。 第二章介绍了时空数据库索引技术的基础一空间索引和时间索引，分 别讨论了空间和时间数据的特点以及主要的空间、时间索引方法。 第三章是对时空索引机制的研究综述，系统地分析和研究时空对象的 特点及其表示、时空索引支持的查询类型、时空索引的分类以及在离散和 连续情况下的时空存取方法。 第四、五两章是本论文的核心部分，详细论述了h t p r * t r e e 时空索引 机制的设计思想和主要实现技术，尤其对基于外存的时空索引结构 h t p r * t r e e 的数据结构和相关算法作了较为完整的介绍，并进行了实现和 性能分析。 第六章总结本文所傲工作，并探讨了进一步的研究方向。 4 重庆邮电大学硕士论文 第二章空间索引和时间索引技术 第二章空间索引和时间索引技术 在过去的- - = 十年里，数据库工作者分别在空间数据库和时间数据库 领域做了大量的研究工作，提出了许多有效的空间存取方法和时间存取方 法，时空索引技术是建立在空间和时间索引技术基础之上的，本章分析了 空间和时间数据的特点，对主要的空间和时间索引技术进行了回顾。 2 1 空间存取方法 2 1 1 空间数据及其特点 空间数据是指带有空间坐标信息的数据，它不仅能表示实体本身的空 间位置及形态，而且还包含实体属性和空间关系的信息。空间数据具有以 下特点： 1 ) 不可排序性：空间数据主要依赖于对象的空间位置进行存取，因 此空间索引是根据空间数据间的邻近性来建立的。对于多维的空间数据则 无法建立一个可以反映其邻近性的排序，即无法找到一个从多维空问到一 维空间的映射f ，使得多维空间的任意两点v l 、v 2 ，f ( v i ) 、f ( v 2 ) 相 邻当且仅当v 1 和v 2 在空问相邻。 2 )相关性：一个空间对象可能是点( 集) 、线( 集) 或区域。除了 单独的一个点以外，一个n 维空间对象至少在其中的一维上覆盖一个区间， 而且一个空间数据库的数据量通常是很庞大的，这使得空间对象间极有可 能相互重叠，即空间数据问的相关性很大，建立在空间位置关系上的空间 索引的效率也随之降低。 3 ) 数据复杂性：在现实世界中，空间对象的大小、边界的几何构造 可以是多种多样的，空间对象的分布也是不均匀的。所以空间对象在计算 机中的表示也很复杂，相应的空| 日j 位置的判断也较复杂。 2 1 2 主要的空间索引方法 鉴于空间数据的特性，传统的数据库索引方法已不能适用于对空间数 据的存取要求，需要根据空间数据的特点重新设计存取机制，已经提出的 重庆邮电大学硕士论文第二章空间索引和时间索引技术 空间存取方法可按其特性分为以下两类； 空间驱动结构( s p a c e d r i v e ns t r u c t u r e s ) ：这类存取方法在不依赖于空 间对象分布的情况下，将二维空间划分为许多矩形单元，再根据空间对象 的某种几何特性将它们映射到矩形单元中。属于空间驱动的索引方法包括 网格文件、k d t r e e 、四叉树、空间填充曲线等以及它们各自的扩展。 数据驱动结构( d a t a d r i v e ns t r u c t u r e s ) ：这类存取方法按照对象的空 间分布划分空间对象集合单元，每个空间对象被分配到唯一的集合单元 中，但允许集合单元的重叠。属于数据驱动的空间存取方法主要是r t r e e 【2 】 系列空间索引。 1 ) 空间驱动索引结构 网格文件( g r i df i l e ) 网格文件【3 1 是一种典型的基于散列的存取方式，它是由包含着很多与 数据桶相联系的单元网格目录来实现的。一般一个数据桶为外存上一个磁 盘页，每个单元只对应着一个数据桶，而一个数据桶通常可以包含着几个 相邻的单元。随着数据的增多，网格目录可能会慢慢变大，所以通常将其 保存在外存( 磁盘) 上，但为了保证在进行精确查询时能仅两次i o 操作 就可找到相应的记录，一般将网格文件本身保存在内存中。网格是用d ( 数 据的维数) 个一维的数组来表示的，这些数组称为刻度。当我们进行精确 查询时，首先用这些刻度来定位包含要查找记录的单元，假如这个单元不 在内存，那么将进行一次u o 操作，将这个单元从磁盘调入内存，在这个 单元中包含着一个指向可能找到记录的页的指针，取这个指针所指的页时 还需要一次i o 操作。对于范围查询，需要检查所有与要查询的区域相交 的单元。图2 i 是一个网格文件的例子。 y b k a i x t h ed i c t i o n a r y 图2 1 网格文件 6 重庆邮电大学硕士论文第二章空间索引和时间索引技术 k d t r e e k d t r e e 【4 1 是一种在k 维空间中的二叉查找树，它主要存储的是点数 据，在每一个内部结点中，用一个k 1 维的超平面将结点所表示的k 维空 间分成两个部分，这些超平面在k 个可能的方向上交替出现，而且在每一 个超平面中至少要包括一个点数据。图2 2 是一个k d t r e e 的例子。 g _ bf i - c al e l d a 图2 2 点对象的平面分布及相应的2 - d 树 四叉树( q u a d t r e e ) 与k d t r e e 类似，四叉树【5 l 也是用超平面的方法来划分整个空间的， 不同的是，四叉树中每个内结点对应于二维空间中的一个正方形区域或是 k 维立方体。以二维空间为例，如果一个正方形的点数不比一个块中能存 放的数多，那么就将这个正方形看作树的叶结点，并且由存放它的点的块 表示；如果正方形中有太多的点以至于一个块存放不，就把这个正方形看 作内结点，它的子结点对应于它的四个象限。一个四叉树的实例如图2 3 所示。 r i 璺i2 3 四叉树实例 重庆邮电大学硕十论文 第二章空间索引和时间索引技术 空间填充曲线 这类索引结构的设计思想是希望找到某种方法对多维空问中的数据 进行近似的排序，使得原来在空间中较为接近的数据能在排序后以比较高 的概率靠在一起，再使用一维数据索引方法进行存取。根据这样的思路， 人们提出了几种将多维空间中的点数据映射到一维空间并进行捧序的方 法，如z 排序、h i l b e r t 码排序等1 6 1 。 所有的空间填充曲线都有一个共同的优点，就是对任何维数的数据都 可以处理，但前提是映射到一维空间的键值可以任意大。这种方法也有一 个明显的缺点，当将两个不同区域的索引组合到一起的时候，至少要对其 中的一个进行重新编码。图2 4 为两种空间填充曲线的实例。 o 一7 1 ：么一3 弘刃1 尹 “ o 名嚣 么 一 ， 7厂7 么么 ( a ) z 一排序 厂 ii 厂厂 l- j 厂 _ j - jl 厂1广厂1n l l j j l j l ljl 广j 广 厂 j l - 7 i广1广 i l jjl u j 厂1 厂1 lj 厂厂h i ljl ji 图2 4 空间填充曲线 ( b ) h i l b e r t 曲线 2 ) 数据驱动索引结构 r t r e e r t r e e l 2 1 系列的空间存取方法都是数据驱动的，即索引结构依懒于空间 对象最小边界矩形( m b r ) 的分布。最小边界矩形是对空间对象的一种近 似表示，在二维空间中，它是一个矩形，在三维空间中，它是一个长方体。 r t r e e 最早是由a g u t t m a n 在1 9 8 4 年提出来的 2 1 ，其后又有了许多变种， 形成了由r t r e e 、r 。t r e e 、r + t r e e 、h i l b e r tr t r e e 、s r t r e e 等组成的r t r e e 系列空间索引。r t r e e 及其众多变体都是一种平衡树，结构非常类似于 b t r e e ，具有类似于b t r e e 的一些性质。 重庆邮电大学硕士论文 第二章空间索b l 和时间索引技术 r t r e e 的索引结构是这样的：被索引的空间对象按照m b r 的位置关 系聚集在一起构成r t r e e 的第一层，即叶结点层，每个叶结点对应于一个 目录矩形，目录矩形是指结点中所有对象( 即数据项) 空间位置的最小包 围矩形；这些叶结点按目录矩形的位置关系聚集构成了r t r e e 的第二层结 点，第二层结点再按该层结点目录矩形的位置关系又聚集构成了再上一层 的结点，如此这样从底向上构造r t r e e ，直至r t r e e 最顶层的根结点。图 2 5 给出了一个r t r e e 的实例。 r a r 1 1 , 2 5 6 1【3 4 ，7 1 0 1 8 ，9 1 4 1 【1 1 1 2 1 3 1 图2 5r t r e e 实例 r + 一t r e e r + 一t r e e l 7 】是r t r e e 的一种变体，它对r t r e e 的插入算法和分裂算法进 行了一些改进，主要体现在以下两点：第一，提出了强制重新插入的概念， 即当一个结点在插入过程中发生了溢出，并不急于进行分裂，而是首先看 一下该层结点在这次插入过程中有没有进行过重新插入，如果没有的话， 则选择一定比例的项从该结点中删除并重新插入到树中，而如果该层己经 有结点进行过重新插入，彳对该结点进行分裂；第二，当结点进行分裂的 时候，不仅要考虑分裂后两个新结点的面积，还要考虑分裂后结点周长以 及该层结点的重叠面积等因素。 图2 6 给出了当树中某个结点溢出时按r t r e e 和r t r e e 的不同分裂策 略分裂后的结果。 9 重庆邮电大学硕士论文第二章空间索引和时间索引技术 ! 卫 目圈d 鍪爹：! ：；：鬈货 ( b ) r 树分裂( c ) r 树分裂 图2 6 分裂策略 r + - t r e e r + - t r e e 8 1 也是r t r e e 的一种变体，它对r t r e e 的改进是每一层结点的 目录矩形不允许重叠。这意味着在r + - t r e e 中进行点查询只需要走一条直接 从根结点到叶结点的路径，操作的时间复杂度即为树的深度。图2 7 是与 图2 4 对应的r + - t r e e 的实例。 x 1 1 t 2 , 5 ，6 】【3 , 4 ，7 1【1 4 1 【8 1 1 ，1 2 1 2 ，1 3 】【8 9 ，1 0 】 图2 7 r + t r e e 实例 目前国内外研制的空间数据库管理系统处理空间数据主要采用r t r e e 或四叉树索引：e s r i 的a r c v i e w 、m a p i n f o 公司的m a p i n f o 和i n f o r m i x 的 g e o s p a t i a ld a t a b l a d e 采用的是r t r e e 系列作为空间索引方法：中国地质大 学的m a p g i s 和中科院的s u p e r m a p 则采用的是四叉树，而著名的o r a c l e 公司的s p a t i a l w a r e 则同时采用这两类存取方法。 2 2 时间存取方法 随着数据库应用范围的扩大，有许多数据库需要管理随着时间的变化 而发生变化的数据，由于时间数掘自身的特点，在许多文献中提出了对随 o 重庆邮电大学硕士论文 第二章空间索引和时间索引技术 时间变化而变化的数据进行索引的方法。 2 2 1 时间维度及其特点 时间信息分为事务时间( t r a n s a c t i o nt i m e ) 和有效时间( v a l i dt i m e ) 两个维度。有效时间是指一个对象( 事件) 在现实世界中发生并保持的那 段时间，或者该对象在现实世界中为真的时间；事务时间是指一个数据库 对象进行操作的时间，是一个事实存储在数据库中的时间，它记录着对数 据库修改或更新的各种历史操作，对应于现有事务或现有数据库变迁的历 史。处理事务时间、有效时间的数据库分别称为事务时间数据库和有效时 间数据库，同时处理这两个时间维度的数据库称为双时态数据库【9 】 ( b i t e m p o r a ld a t a b a s e ) 。 1 ) 事务时间维的特点 事务时间的特点是它总是递增的：在事务时间数据库中，新记录的存 储时间总是发生在原有记录存储时间之后，或者说被标以了新的时间戳 ( t i m e s t a m p ) ，这意味着原有的记录是不再会发生改变的( 因为新的记录 总是被标以新的时间戳) 。这个特性对于一些每项活动必须要登记并且登 记之后不能再有变更的数据库应用来说是非常有用的，比如审计、账务等。 因此，事务时间数据库比现实世界更能反映历史活动，它能“回滚 ( r o l l b a c k ) ”，或响应历史状态的查询。 用s 表示对象的集合，它记录对象的活动状态，并随着时间的变化而 变化，s 的变化包括对象的插入、删除或对象属性的变化。对象在从插入 到数据库中至从数据库中删除的这段时间内被称为是活动的，相应的时间 间隔称为对象的生命期。因此，集合s 中随时保存的是活动对象信息，假 设时间是离散和递增的，则s ( t ) 表示的是在时间戳t 的所有活动对象。 用ts t a r t 表示对象插入到数据库中的时间戳，te n d 表示对象从数据库中 删除的时间戳，对象的生命期用区间【ts t a r t ，t e n d ) 表示，若当前时间戳 对象仍处于活动状态( 删除时间未知) ，则对象的生命期用开区间 【t s t a r t ，n o w ) 表示。事务时间数据库中保存了过去任意时间戳的状态s ( t ) ， 可响应对过去任意时间戳的查询。 事务时间数据库的索引具有下列特性： 存储对象的过去逻辑状态； 支持对当前时间戳逻辑状态的插入、删除以及对象属性的更新； 支持对数据库任意时间戳的有效存取和查询。 重庆邮电大学硕士论文第二章空间索引和时间索引技术 2 ) 有效时间维的特点 有效时间数据库记录的是当前时间发生的所有事件。它存储过、正在 存储或是将要存储的是过去、当前或未来发生的所有活动对象信息。也就 是说，当进行数据修改或更新之后，新的活动记录将会替换旧的活动记录， 再也不能查找到修改更新前的记录数据。在有效时间维度内，可在任意时 刻对有效时间数据库进行更新。( 而在事务时间数据库中，数据更新只能 按递增的时间戳进行) 。 有效时间数据库索引具有下列特性： 存储最新的活动对象信息； 支持对当前时间戳对象的插入、删除以及对象属性的更新； 可对当前时间戳活动对象进行查询。 有效时问数据库的索引可直接采用传统的数据库索引方法。 3 ) 双时态数据库 双时态数据库也叫双时间数据库，它同时具有事务时间数据库和有效 时间数据库的特点，它既能保存过去时间的信息，又支持在任意有效时间 对数据库的更改，因此，这样的数据库更能反映真实世界。图2 8 给出了 双时态数据库抽象模型，其中c ( t i ) 是时间戳t j 的有效时间数据库的状态。 图2 8 双时态索引抽象模型 2 2 2 主要的时间索引方法 1 ) 快照索引( t h es n a p s h o ti n d e x ) 快照索引d o 支持事务时间索引，能有效地响应单个时间片 ( p u r e t i m e s l i c eq u e r y ) 查询，即给定时间戳t ，查找s ( t ) ，它由以下三个 数据结构组成： 对数据页按时间索引的平衡树( 时间树) ； 在平衡树的叶页面间链接的多链接结构( 存取森林) ： 1 2 重庆邮电大学硕士论文第二章空间索引和时间索引技术 支持按关键字存取对象记录的哈希表。 图2 9 是一个快照索引结构示意图，其中( a ) 表示活动对象及递增时 间序列，( b ) 是相应的时间树和存取森林。 ! ! !竺! !竺竺：! ! s f l - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - a e 0 - - - - - - - - - - - - - - - - - - - - - - c - - - - - - - - - - - - - - - - - - - - - f - 一 b 一 ( a ) 图2 9 快照索引结构 2 ) t s b - t r e e( t h et i m e s p l i tb t r e e ) t s b t r e e 1 1 1 能有效响应事务时间数据库的区域时间片查询 ( r a n g e t i m e s l i c eq u e r y ) 。它在结构上将数据按事务时间和关键字值聚集在 页面内，以使与区域时间片查询“逻辑相关”的数据可以在位置上聚集在 最少数目的存耿页内；采用平衡树结构，树的叶页面动态地与事务时间 关键字的两维空自j 区域相对应，叶结点结构为 ，其中 k e y 表示对象( 关键字) ，t i m e 是记录创建的时间，a t t r i b u t e 是与时间相关 的属性，索引结点结构为 ，k e y 和t i m e 表示p o i n t 指向的 下一层结点对应的事务时间一关键字矩形的最小关键字和最小时间值。 t s b t r e e 适用于对象的插入、更新比较频繁，而对象的删除很少的时间数 据库应用。图2 1 0 给出了一个t s b t r e e 的例子。 重庆邮电大学硕士论文第二章空间索引和时间索引技术 图2 1 0 ( a ) 索引的事务时间一关键字空间 图2 1 0 ( b ) t s b t r e e 3 )m v b t r e e( t h em u l t i v e r s i o nb t r e e ) m v b t r e e 【汜1 支持事务时间数据库，它的设计思想是将时间片的查询转 换为部分持久( p a r t i a l l yp e r s i s t e n c e ) 问题。部分持久指在数据更新时，建 立新版本的数据结构，而旧版本的数据结构仍保存并可以存取，同时只有 最新版本的数据结构可以被修改并用以创建更新的版本。每个版本的数据 结构都是离散的，称为暂态结构，时间戳t 的暂态结构对应于该时间戳的 对象状态s ( t ) ，暂态结构的树可以为b + - 树，可对相应时间戳的对象按关 键字索引。在m v b t r e e 中进行时间片查询时，只需先查找到相应时间戳 的暂态树，再在该暂态树中查找。 4 )重叠b t r e e ( t h eo v e r l a p p i n gb t r e e ) 重叠b t r e e t 】是在m v b t r e e 的基础上，认为相邻暂态b t r e e 间的变 化不大，为节省存储空间，可以共享相邻暂态b t r e e 问的某些分支，仅需 对有变化的分支更改。这样的索引结构可同样支持事务时间数据库的单个 4 重庆邮电大学硕士论文 第二章空间索引和时间索引技术 时间片、区域时间片的查询，重叠b t r e e 的例子如图2 1 1 所示。 r o o t o f o l d v e r s i o n r o o l o f n e w v e r s l o n s h a r e d s h a r e do l ds h a r e d 图2 1 1 重叠b t r e e 5 ) 双时态数据库索引方法 对双时态数据库索引的一种简单方法是用由对象的有效时间和事务 时间间隔确定的边界矩形( b o u n d i n gr e c t a n g l e ) 表示双时间对象，并用 r t r e e 结构建立索引 14 1 。这种索引方法的优点是只需要一种索引结构就可 以支持两个时间维度的索引，但在这种结构中，事务时间的特性会引起连 续的重叠问题。为了避免重叠，有一种双r t r e e 索引结构支持双时间数据 库索引【1 4 】，它用前一棵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 3 小结 空间、时间数据的特点以及空问、时间索引方法为进一步对空间位置 随时间变化而发生变化的时空对象索引机制的研究奠定了理论基础。 重庆邮电大学硕士论文第三章时空索引机制研究 第三章时空索引机制研究 时空数据库需要管理大量带有长期时间信息的空间数据，为了对这些 数据进行有效存取，对时空数据库索引机制的研究显得尤为重要。但空间、 时间索引技术的研究成果并不能直接应用于时空数据。因为：对空间索引 的研究成果可以支持对点、任意形状的对象及光栅数据的查询操作，但没 有考虑到时空应用中的时间特性，而已提出的时间存取方法只对有效时间 或事务时间进行索引以支持时间数据库的索引，没有考虑到时空对象的空 间属性。本章在分析时空对象的特点、时空索引支持的基本查询类型之后， 研究时空索引机制的方法并进行分类，讨论时空索引中的关键技术。 3 1 时空对象 3 1 1 时空对象的概念 空间位置或范围随着时间的变化而发生变化的空间对象称为时空对 象( 也称为移动对象) 。如正在飞行的飞机、高速公路上行驶的小汽车、 随着时间的变化其边界范围在扩大或缩小的森林等。有大量的应用需要存 储和管理时空对象，查找对象在过去、现在的位置和范围，推测其在未来 某一时间戳或时间间隔的行为。 时空数据库存储的是随时间变化的空间对象。在空间数据库中定义了 三种基本空间