（计算机应用技术专业论文）空间数据库引擎关键技术研究.pdf

摘要 空间数据库是地理信息系统研究的热点，而空间数据库引擎则是空间数据库 的核心，使得传统数据库能高效处理和分析多维空问数据，使得空问数据有序化， 并从中挖掘各类信息，在地理信息高速发展的今天，高性能空间数据库引擎的研 制具有重大的理论和实际意义。鉴于此，本文研究和开发一种相对简单高效的空 间数据库引擎。本文研究内容包括： ( 1 ) 空问矢量数据存储 开发一种简洁的二维矢量数据存储模式，并实现多源数据存取，实现空问数 据与属性数据的无缝集成，数据具备可视化特征，表达能力强，并提供一定的对 外访问接口。 ( 2 ) 空间矢量数据索引 主要研究基于r 树的二维索引，包括动态索引更新和静态索引批量加载，索 引的创建、维护、存取、缓冲、优化及基于索引的空间检索和分析。 ( 3 ) 空问数据查询语言g s q l 研究标准化空间查询语言( g e o g r a p h i cs t a n d a r dq u e r yl a n g u a g e ，g s q l ) 的 词法、语法规则，并结合本文特征，提出一种简单的实现。 ( 4 ) 空间分析模型 开发一种统一的、可扩展的空间分析模型，模型定义空间分析计划以及基于 该计划的空问分析调度方式，并使得空问分析易于维护和扩展。 ( 5 ) 高效的空间数据库引擎体系架构 该架构属于一般网络服务器架构范畴，基于l i n u x 平台，由于l i n u x 特有的线 程机制，使网络服务在多线程互斥条件下运行效率较低，本文拟采用事件驱动、 多迸程相互通信的架构模式。 关键词：空间数据库引擎，矢量数据存储，空间索引，g s q l ，空间分析模型 b s t p a c t a b s t r a c t s p a t i a ld a m b a s eh a sb e e nb e c o m i n go n eo fn l eh o t t e s ti s s u e si ng i sf i e l di nr e c e n t y e a r s a n di ti ss p a t i a ld a t a b a s ee n g i n e ( s d e ) t h a te n a b l e si tt os t r u c t u r es p a t i a ld a t a ，t o q u e r ya n da n a l y z es p a t i a l i n t e r r e l a t e dd a t ae f f i c i e n t l y , a n dt om i n i n gu n d e r l y i n g i n f o r m a t i o n s o ，i ti so ff u n d a m e n t a li m p o r t a n c et os t u d ys d et e c h n o l o g i e sb o t hi n p r a c t i c ea n dt h e o r y , i nl i g h to ft h i s ，w ea n a l y z et h ek e yt e c h n o l o g i e so fs p a t h ld a t a b a s e e n g i n ea n dd e v e l o p a s i m p l ep l a n e rs p a t i a ld a t a b a s ee n g i n e ，o u rr e s e a r c hi n c l u d e s ： ( 1 ) s p a t i a ld a t as t o r a g e d e v e l o pas i m p l ea n de f f i c i e n tr e p r e s e n t a t i o no fs p a t i a ld a t a , b a s e do nw h i c hw e i n t e g r a t eb o t ha t t r i b u t ea n ds p a t i a ld a t a ，a n dp r o v i d ei n t e r f a c ef o rd a t aa c c e s s i n g ( 2 ) s p a t i a li n d e x s t u d yr - t r e ei n d e x e s ，i n c l u d i n gd y n a m i ci n d e xu p d a t i n ga n ds t a t i ci n d e xb u l k l o a d i n g ，i n c l u d i n gi n d e xc r e a t i o n , m a i n t a i n i n g ，a c c e s s i n g ，b u f f e r i n g ，o p t i m i z i n ga n d s p a t i a la n a l y z i n gb a s e d o ns u c hi n d e x ( 3 ) s p a t i a lq u e r yl a n g u a g eg s q l a n a l y z et h eb a s i cs y n t a xo fs t a n d d r dg s q l ，a n dp r o v i d eas i m p l ea n de f f i c i e n t i m p l e m e n t a t i o nb a s e do n o u rr e s e a r c h ( 4 ) s p a t i a la n a l y s i sm o d e l d e v e l o pas p a t i a la n a l y s i sm o d e lf o rs p a t i a la n a l y z i n g ，w h i c hd e t e r m i n ea n a l y s i s p l a na n dt h eo r d e ro f a n a l y s i ss t e p s ，a n dw h i c hm a k e ss p a t i a la n a l y s i se a s yt om a i n t a i n a n de x t e n d ( 5 ) s d es e r v e ra r c h i t e c t u r e o u rs d e ，i ns o m ew a y , i san e ts e r v e rw h i c hp r o v i d e ss p a t i a ld a t as t o r a g ea n dq u e r y , s o ，t h ea r c h i t e c t u r eo fo u rs d eb e l o n g st oc o n l m o nn e ts e r v i c ea r c c t a r em o d e l ，t h a t i s ，al a y e r e d ，e v e n td r i v e n ，m u l t i p r o c e s s e da r c h i t e c t u r eb a s e do i ll i n u x k e y w o r d s ：s p a t i a ld a t a b a s ee n 百n e ，v e c t o rd a t as t o r a g e ，s p a t i a li n d e x ，g s q l ，s p a t i a l a n a l y s i sm o d e l n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：二王三鱼l 一日期：圳6 月4 f 1 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：塞i 鬼聊签名：墨l 亟 日期：明年6 月( fe l 第一章绪论 第一章绪论 1 1 空间数据库与空间数据库引擎 空间数据库的研究始于2 0 世纪7 0 年代的地图制图与遥感图像处理领域卜”， 其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图：由于传统 的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷，从而形成 了空问数据库这一数据库研究领域h 4 j 。随着地理信息系统( g e o g r a p h i ci n f o n n a t i o n s y s t e m ，g i s ) 、计算机辅助设计与制造( c a d c a m ) 、机器人、多媒体系统、数 字地球、移动通信及定位服务等应用领域的发展，对空间数据库以及时空数据库 的研究越来越受到人们的重视。在这一过程中，空间数据库引擎技术也德以快速 发展，在数据管理方面，先后出现了文件与关系数据库混合管理、全关系型空间 数据库管理、对象一一关系数据库管理和面向对象空问数据管理等不同的空间数 据管理模式，在空间索引方面，发展出层次网格索引和基于r 树的一系列索引1 4 - 5 1 。 空间数据库引擎( s p a t i a ld a t a b a s ce n g i n e ，s d e ) 是空间数据库区别于传统 数据库的关键特征，是空间数据库独有的程序功能集合，负责空问数据的存储， 检索和分析，使得空间数据能有效组织并快速访阀和分析h 。】。 1 2 空间数据库引擎的研究现状 经过近3 0 年的发展，空问数据库引擎技术已经日趋成熟，s d e 产品也不断更 新换代，它们包括e s r i 公司的a r c s d e 、o r a c l e 公司的o r a c l es p a t i a l ，m a p l n f o 公司的s p a t i a l w a r e 以及北京超图s u p e rm a ps d x + 等，其中a r c s d e 功能最强。产 品的每一次更新，都提供更高的数据存储、检索和分析能力。 目前对空间数据库引擎的研究主要包括以下几个方面。 1 2 i 空间数据的存储 空间数据的存储主要包括：空问数据的组织和表示方式，空间数据的压缩与 还原。空间数据包括矢量数据和栅格数据。矢量数据是基于点、线、面及其拓扑 特征的图形数据，栅格数据主要是基于象元特征的地图影像数据。矢量数据由于 电子科技大学硕士学位论文 其多维和空间拓扑特性，不易采用简单的r d b m s 存储。空间数据的表示分为内 部表示和外部表示。对于矢量数据，由于数据源的多样性，数据内容的广泛性， 内部表示往往是独立自定义的，可以是基于二进制或字符序列。这种表示仅对数 据定义者可知，同时，定义者提供了外部访问接口，如e s r is h p t 6 1 文件。矢量数 据的外部表示，即用于定义、传输和共享矢量数据的编码规范，这种表示应该统 一并易于理解和传输，如地理信息标记语言g m l ( g e o g r a p h i cm a k e u pl a n g u a g e ) 盯l 。对于栅格数据，多用固定格式的二进制表示，其数据量甚大，数据压缩和解 压是关键的问题，目前多采用j p e g 、游程编码等压缩方式川【8 9 l 。 1 2 2 更高效的空间数据索引 到目前为止，并不存在一种对任意空间数据都高效的空间索引。r 树系列索引 对区域索引效率较高，但对线索引效率低下；网格文件索引对线索引效率较高， 但对区域索引效率较低：在新的变革性的索引出现之前，它们将被综合使用。目 前，对空间索引的研究主要有三个方向 5 1 ： 1 ) 目标映射：采用多属性数据索引直接索引点状空间实体，对于线、面等其 它形状的空问实体，将其映射为更高维空间的点，或采用某种方法将其映射为一 维目标，再用传统的索引技术( 如b + 树) 索引。k d 树和网格文件都属于这类索 引方式。 2 ) 目标重叠：将索引空问按照某种策略划分成许多子空问，空问目标属于与 其相交的子空间。对于非点状目标的索引，这种方法必然导致目标重复存储，除 了存储开销较高以外，还会增加插入、删除操作的复杂度。r 十树，m k d 树属于这 类索引。 3 ) 目标界定：允许索引子空间重叠，将目标界定在某一索引子空间之内，目 标的重复存储可以避免，但索引子空间的重叠必然会导致多条查找路径，因此如 何组织目标使索引空间的重叠最小是这类索引方法的主要目标，如r - 树，r ，树等。 1 2 3 时空数据存储与检索 随着数字城市、定位服务等概念的提出与应用，对大型空问数据库的性能提 出了更高的要求。它不但要求能够有效地检索海量数据，而且要求能够有效地存 储及检索随着时问推移，其位置关系在不断变化的移动数据对象。目前的空间索 引技术的性能往往随着索引数据量的巨增及索引数据的不断更新而急剧下降，因 2 第一章绪论 此研究针对时空数据库中面向移动数据对象的索引技术迫在眉睫，目前的时空数 据索引研究多是扩展传统的r 树嘲。 1 3 本文的研究目的和研究对象 本文着重研究空问数据库引擎若干关键技术，以期实现一个简单的二维矢量 数据空间数据库引擎。并在索引、缓冲等方面进行优化。本文的主要研究对象包 括： ( 1 ) 空问矢量数据存储 提出一种简单高效的二维矢量数据存储模式，并实现多源数据存取，实现空 间数据与属性数据的无缝集成，数据具备可视化特征，表达能力强，并提供一定 的对外访问接口。 ( 2 ) 空闻矢量数据索引 主要研究基于r 树的二维索引，包括动态索引更新和静态索引批量加载，索 引的创建、更新、存取、缓冲、优化及基于索引的空间检索和分析。 ( 3 ) 空问数据查询语言g s q l 研究标准化空间查询语言( g e o g r a p h i cs t a n d a r dq u e r yl a n g u a g e ，g s q l ) 的 词法、语法规则，并结合本文特征，提出一种简单的实现。 ( 4 ) 空问分析模型 开发一种统一的、可扩展的空间分析模型，模型定义空问分析计划以及基于 该计划的空问分析调度方式，并使得空间分析易于维护和扩展。 ( 5 ) 高效的空间数据库引擎体系架构 该架构属于一般网络服务器架构范畴，基于l i n u x 平台，由于l i n u x 特有的线 程机制，使网络服务在多线程互斥条件下运行效率较低，本文拟采用事件驱动、 多进程相互通信的架构模式； 电子科技大学硕士学位论文 第二章空间数据库引擎的概念与原理 空间数据库引擎是空间数据库进行空问数据管理的核心部件，从一定意义上 讲，空间数据库是传统数据库和空间数据库引擎的总和。传统的数据库可以是纯 关系数据库、对象一一关系数据库等。由于空间数据的独有特征，传统数据库不 便于直接管理空间数据。 2 1 空间数据的特征 2 1 1 空间特征 每个空问对象都具有空间坐标，即空间对象隐含了空间分布特征。这意味着 在空间数据组织方面，要考虑它的空间分布特征。除了通用性数据库管理系统或 文件系统关键字的索引和辅关键字索引以外，一般需要建立空间索引 5 1 。 2 1 2 非结构化特征 在当前通用的关系数据库管理系统中，数据记录一般是结构化的。即它满足 关系数据模型的第一范式要求，每一条记录是定长的，数据项表达的只能是原子 数据，不允许嵌套记录。而空间数据则不能满足这种结构化要求。若将一条记录 表达一个空间对象，它的数据项可能是变长的，例如，一条弧段的坐标，其长度 是不可限定的，它可能是两对坐标，也可能是十万对坐标；其二，一个对象可能 包含另外的一个或多个对象，例如，一个多边形，它可能含有多条弧段。若一条 记录表示一条弧段，在这种情况下，一条多边形的记录就可能嵌套多条弧段的记 录，所以它不满足关系数据模型的范式要求，这也就是为什么空间图形数据难以 直接采用通用的关系数据管理系统的主要原因肚”1 。 2 1 3 空间关系特征 空问数据除了前面所述的空间坐标隐含了空问分布关系外。空间数据中记录 的拓扑信息表达了多种空间关系。这种拓扑数据结构一方面方便了空间数据的查 询和空问分析，另一方面也给空间数据的一致性和完整性维护增加了复杂性。特 4 第二章空问数据库引擎的概念与原理 别是有些几何对象，没有直接记录空间坐标的信息，如拓扑的面状目标，仅记录 组成它的弧段的标识，因而进行查找、显示和分析操作时都要操纵和检索多个数 据文件方能得以实现嗍。 2 1 4 分类编码特征 一般而言，每一个空间对象都有一个分类编码，而这种分类编码往往属于国 家标准，或行业标准，或地区标准，每一种地物的类型在某个g i s 中的属性项个 数是相同的。因而在许多情况下，一种地物类型对应于一个属性数据表文件。当 然，如果几种地物类型的属性项相同，也可以多种地物类型共享一个属性数据表 文件嘲。 2 1 5 多尺度和多态性 空间数据来源广泛，数据由于采集时问、采集环境的不同，往往具有不同的 比例尺和不同的精度，同一地物在不同形态下也具有差异。比如，就城市而言， 任何城市在地理空间中都占有一定的区域，可视为面状物，然而在小比例尺空间 数据库中，城市是作为点状物来处理的。 2 1 6 海量数据特征 空问数据量是巨大的，通常称海量数据，其数据量比一般的通用数据库要大 许多。一个城市地理信息系统的数据量可能达几十g b ，如果考虑影像数据的存储， 可能达几百个g b 。这样的数据量在城市管理的其它数据库中是很少见的。正因为 空间数据量大，所以需要在二维空间上划分块或者图幅，在垂直方向上划分层来 进行组织【”】。 空问数据的这些特征，使得直接管理空问数据非常困难。在一体化管理空间 数据和属性数据的过程中，空间数据库引擎得以发展并日趋成熟。 2 2 空问数据库引擎功能定义 空间数据库引擎指提供存储、检索空问数据以及对空间数据进行空间分析等 功能的程序集合。空问数据库引擎包括以下几方面的内容1 4 1 0 - 1 1 1 ： 5 电子科技大学硕士学位论文 2 2 1 多用户权限和并发管理 由于空间数据的敏感性，空间数据库引擎必须对不同用户提供不同的权限， 以确保数据安全和一致。同时，在现代网络环境下，空间数据库引擎主要面向网 络用户，因此，必须对空问数据提供并发访问控制功能。并发访问通常通过多线 程、多进程和并发控制锁实现。并发控制对象包括一切原空问数据和空问索引。 对静态空间数据，并发控制相对简单。 2 2 2 空间数据存取功能 鉴于空间数据的特性，传统的关系数据类型不能直接表示空问数据，为了在 传统数据库中表示空问数据，必须建立从传统数据类型到空问数据模型的映像。 同时，还必须建立相应的辅助机制来维护空间数据的空间拓扑关系。空间数据存 取是空间数据库引擎的基础。 2 2 3 空间数据索引功能 空问数据库索引技术是对存储在介质上的数据位置信息的描述，用来提高系 统对数据获取的效率。空间数据索引由两方面因素所决定嗍： 1 ) 计算机的体系结构将存储器分为内存和外存两种，访问这两种存储器一次 所花费的时间相差十万倍以上，在实际应用中，绝大多数数据是存储在外存磁盘 上的，若对磁盘上数据的位置不加以索引和组织，则每查询一个数据项就要扫描 整个数据文件，这种磁盘访问代价将严重影响系统效率，数据索引对减少这种代 价至关重要。 2 ) 空问数据所表现的数据多维性使得传统的数据库索引技术( 如b 树等) 并 不适用，因为传统数据库索引所针对的字符、数字等数据类型是在一个良序集之 中，即都是在一个可比较维度上，集合中任给两个元素，其关系只可能是大于、 小于、等于三种。而空间数据具有多维性，目前不存在从二维或高维空问到一维 空问的映射，使得任何两个在高维空间接近的对象在一维排序序列中也相互接近。 传统的数据库索引技术并不能对空间数据进行有效的索引，需要使用特殊的能适 应多维特性的空间索引方式。 6 第二章空间数据库引擎的概念与原理 2 2 4 空间查询、运算和分析功能 空间查询异于传统的数据库查询，查询内容也包括空间拓扑信息，在空间查 询过程中，可能涉及空间运算和空间分析。空间运算和空间分析是空间数据库引 擎的核心。空间运算包括空问连接、空问分割、空间缓冲、空间距离等，空间分 析主要是拓扑分析，包括空问包含、空间相交、空间相离、空间相接等。但空间 运算与空间分析并无显着区别，同时，空间运算和空间分析是空间数据库区别于 传统数据库的显着特征。空间查询和空问分析都借助于空间索引实现h 1 。 2 3 空间数据库引擎的功能结构 鉴于以上对空问数据库引擎功能的分析，可以得到空间数据库引擎的功能结 构图如图2 - 1 。 口 脚 并 发 控 制 s d e 客户端应用 s d e 通讯协议接口 s d e 空间查询分析接口 s d e 空间查询分析服务 s d e 空间数据及索引存取 图2 1 空问数据库引擎功能结构图 从图2 1 可以看出空间数据库引擎在整个空间数据库系统中所处的位置。其中 空间索引功能包含于空间查询分析服务中，用户管理位于查询分析模块中，并发 控制则贯穿于整个引擎模块。 s d e 通讯协议接口用于接收来自客户端的应用请求，请求按一定的协议格式， 通过直接或网络传输到达服务器。s d e 通讯协议接口处理所有与协议格式相关的 报文验证、解析、转换等，以保证请求报文的正确性和完整性，该接口同时负责 应答报文的回送。 7 -ii；i_-_ 一 一空间数据库引擎一口e) _ 电子科技大学硕士学位论文 s d e 空间查询分析接口负责解析来自于通讯模块的查询请求，在支持g s q l 的s d e 中，主要负责分析g s q l ，将g s q l 分解为若干相关的空间数据检索、分 析等执行步骤，以提交给空间服务例程执行。 s d e 空间分析服务接收来自查询分析接1 3 的操作请求，负责具体空间数据检 索和分析，也即前面提到的数据检索、空问运算和空间分析功能。空间检索和分 析都基于特定的空间索弓l ，空间索引技术是决定空间检索和空间分析的关键因素。 s d e 空间数据及索引存取模块位于整个引擎的底层，是整个空间数据库引擎 的基础，也是整个引擎中唯一直接作用于空间数据和索引数据的模块。实现此前 提及的数据存取和转换功能。 2 4 空间数据库引擎的查询模式 空间数据库引擎一般采用二级查询模式来处理所有的空间检索和分析请求， 该模式图示如图2 2 所示。 初级 过滤 二级 过滤 图2 - 2 空间数据厍引擎二级查询模式 初级过滤主要基于空间索弓i 技术，对大批量的空间数据，通过一定的目标筛 选策略，尽快地选择所有可能的候选结果集。二级过滤对候选数据集执行具体的 空间分析运算，得到最终的结果集。初级过滤大大缩减了二级过滤空间分析的运 算量，从而提升整个空间分析运算的效率。现代主流空间数据库都是采用这种查 询模式的，如o r a c l e 公司o r a c l es p a t i a l i ”l 。 2 5 本章小结 本章论述的空问数据库引擎的基本概念与原理，包括空间数据特征、空间数 第二章空问数据库引擎的概念与原理 据库引擎功能结构、空间查询模式等，从根本上解释了为什么要使用空间数据库 引擎以及空间数据库引擎的整体结构和查询模式。至此，论文完成了空间数据库 引擎概论，下部分将具体论述空间数据库引擎的关键技术与实现。 9 电子科技大学硕士学位论文 第三章空间数据库引擎若干关键技术分析 空间数据库引擎涉及技术众多，本文着重从数据存储、空间索引、空间分析 和空间查询语言四个方面进行分析。 3 1 数据存储 数据存储是空问数据库的基础，早期空闻数据的存储主要是基于外部文件的 方式，并通过一定的途径将属性数据与空间数据联系起来。现阶段的空问数据库 引擎普遍将空间数据存储于数据库中，以实现属性数据与空问数据的无缝集成。 3 1 1d b m $ 存储支持 d b m s 的存储支持使得空间数据能存储到数据库中，d b m s 按逻辑页的方式 组织数据文件，页内分槽( s l o t ) ，槽与记录对应。记录分为若干域，每域存储一 数据项。一个逻辑页面对应一个或多个( 2 的整数次幂) 磁盘扇区。同时，d b m s 通过索引页面和槽号而索引所有记录0 1 。d b m s 对空间数据的支持主要包括以下 两个方面 3 1 1 1 数据类型支持 目前传统的数据库，都提供对b l o b 、c l o b 等大对象数据的支持。b l o b 为 二进制对象，c l o b 为字符对象。典型的o r a c l e 9 i 数据库直接提供b l o b 、c l o b 数据类型，最大支持2 g 单记录数据量，并对这些数据类型的存取提供了c 、j a v a 等语言接口；m y s q l 5 0 3 及其以后的版本支持v a r c h a r 、v a r b i n a r y 数据类 型，容量约为6 4 k ，同时支持b l o b 和t e x l 系列数据类型( t i n y b l o b， t i l q y t e x t ，b l o b ，t e x t ，m e d i u m b l o b ，m e d i u m t e x t ，l 0 咐g b l o g ， l o n g t e x t ) ，最大单记录数据量为4 g ，并支持c 、j a v a 、p h p 等多种语言访闯。 b l o b 适合二进制栅格数据的存储，栅格数据一般按格网单元分块，并将分块 按一定的空间位置关系序列存储，栅格单元数据在数据库中的表现形式为一系列 整块或分块的逻辑页面。同时，对于二进制矢量数据，也可存储为b l o b 数据类 型，比如，e s r is h p 【6 】文件，s h p 文件由一系列矢量数据记录组成，可将其与属 第三章空间数据库引擎若干关键技术分析 性数据对应，一并存储到数据库中。 c l o b 适合字符型矢量数据存储，比如基于g m l t 7 1 的矢量数据。数据库将这 些数据统一视为普通字符序列而直接存储，而数据的具体格式和意义则由应用程 序保证和解释f 3 l 。 3 1 1 2 存取优化支持 d b m s 对数据存储做了很多优化，主要包括： ( a ) 文件组织 文件组织主要针对属性数据而言，文件组织的目的是使整个文件有序化，从 而便于排序和访问。成熟的文件组织形势包括散列文件和有序文件。散列函数通 过简单的计算，将预先选择的一个主码域的值映射到一个散列单元之中，其重要 性在于将数量大致相同的记录放入每个散列单元中，在适当的散列函数前提下， 数据访问可以在一个常数时间内完成，而与记录数无关。有序文件按给定的主码 域对记录进行组织，可以用折半查找算法根据给定主码属性值查找记录。同时， 还可以通过索引文件加快访问速度o j 。 ( b ) 缓冲优化 缓冲管理器是d b m s 的一个软件模块，专门负责主存与二级存储之问的数据 传输。由于一个典型的空问分析或数据库事务所需交互的数据量远大于主存容量， 因此，需要为高效事务处理或空问分析实施一个协议，即置换策略，以确保事务 或空间分析不因一部分数据不在主存而停顿下来。对于d b m s 的缓冲管理，只利 用传统的虚拟内存置换算法，如最近最少使用( l r u ) 算法，可能是不够的。 现代关系数据库多采用d b m i n 算法l l 封来处理页面置换，它是以查询本地集 模型( q l s m ) 为基础的。q l s m 的页面引用模型不依赖任何的页面置换方案。q l s m 将数据库操作的引用模式特征化为顺序引用、随机引用和分层引用。缓冲区是以 一个文件实例( 表) 为单位进行分配和管理的。和一个文件实例相关联的缓冲页面集 合被看作它的本地集( 1 0 c a ls e t ) 。本地集的大小根据查询计划和数据库的统计信息 来确定。薄记( b 0 0 l ( 1 【e 印i n g ) 通过维护一个全局页表和全局空闲链表来实现。如果在 本地集和全局页表中找到了所请求页面，则直接返回该页，同时更新其使用统计 信息，反之，则将该页读入本地集合( 空白页) 中，若没有可用空页，则根据本地集 置换策略，替换一个已存在页面。一个详细的模拟研究发现，使用d b m i 比使用 频繁访问算法吞吐量高7 到1 3 个百分点“”。 屯子科技犬学硕士学位论文 3 1 2 数据聚类( c i u s t e r i n g ) 按其最抽象的形式来讲，聚类的目的是降低响应常见大查询的寻道时间和等 待时间。对于空间数据库来说，这意味着空间上相邻和查询上相关的对象在物理 上应存储在一起。空间数据库系统支持三种聚类，用于提供有效的查询处理1 i tl ： ( 1 ) 内部聚类 为加快对单个对象的访问，将该对象的全部表示存于同一个页面或多个连续 页面。页面的多少由对象数据量决定。 ( 2 ) 本地聚类 为加快多个对象的访问速度，将一组空间对象( 或者近似) 分配到同一页面。这 种分组可以按照数据空间中对象的位置( 或近似) 来施行。 ( 3 ) 全局聚类 与本地聚类相反，一组空间邻接的对象并不存储在一个而是多个物理上相邻 的页面上，这些页面可以由一条单独的读命令访问。 空间聚类技术远比传统聚类技术复杂，因为空问多维数据并不天然有序。空 间聚类主要研究从多维空间到一维空间的映射，该映射必须是“距离不变”，而且 是一一对应。现今，突出的映射方法包括z 序( z o r d e r ) 、格雷码( g r a y c o d e ) 和h i l b e r t 曲线。z 序和h i l b e r t 曲线都是不断二次迭代的过程，h i l b e r t 曲线的生成过程如图 3 1 ( 具体迭代过程略) ，从曲线的第一点开始对拐点排序，序号值就是对应坐标的 映射值。 第三章空间数据库引擎若干关键技术分析 n = 0 口 面圈 l 圳i 啦i 3 1 3 空间数据类型 a a n = 3 广1广广 l jl j r jl 1r j j ii l 1 广一 r 一 _ l 广jl 1 l j l 1r j广 l 一i l ji 图3 - i 生成一条h i l b e r t 曲线 对基于对象的空间信息模型来说，其关键问题是选择一组基本空间数据类型来 满足对地图常用形状建模的要求。目前，广泛接收的o g i s 制定的简单地理特征数 据类型规范 1 ，如图3 - 2 所示。 图3 - 2o g k 5 几何模型 1 3 电子科技大学硕士学位论文 o g i s 所建模的基本空间对象是基于简单要素的，即以点、线、面及其组合所 构成的简单空问对象集合。 这里所表示的空间模型只是一种概念模型，在空间数据库中，空间数据是以 物理的字符或字节序列存放在二级存储器中，但空间检索分析是建立在基本空间 类型对象上的，这就需要将物理格式的空间数据转换为计算机内部表示的空问对 象，即对空间数据序列化，但传统数据库只提供对简单内在数据类型的序列化支 持，比如数字、字符、日期、定长字符串等。所以，序列化是查询、分析空间数 据过程中必不可少的过程。该过程如图3 3 所示。 3 1 4 数据压缩 序列化 空问数据类型内存表示 图3 - 3 空间数据序列化 本文着重研究矢量数据。同时，栅格数据也可以向矢量数据转化，故这里主 要研究矢量数据的压缩技术05 - 2 1 1 。 数据压缩，从传统意义上讲，包括无损压缩和有损压缩。无损压缩主要基于 编码转换，通过新的编码方式来表达原有数据信息，使源数据达到“数据无损稠 密”，如游程长度编码，g z i p 压缩等。有损压缩的基本思想是冗余信息裁减，即 在尽量保证图形不失真的情况下，对图形进行特征点提取，或降低数据精确度， 采用较少的有效数据位来表示原有数据。 在基于特征点提取的矢量数据压缩算法i ”1 中，d o u g l a s p e u c k e r l l 6 - 1 7 1 算法堪称 经典。该算法以点与直线距离为特征，采用递归的方式，提取距离值大于特征值 的点，算法描述如下： 首先确定曲线的最左边和最右边作为起始点( 对于闭曲线) ，对于开曲线，可 选择其两个端点作为起始点。然后找出位于两个端点之问的曲线离散点距这两个 端点连线的最大距离点，如果该距离大于给定的精度限差，则该点被确定为保留 点。然后分别再用已经得到的各相邻保留点为起始端点，用同样的方法对于他们 4 冒虽 第三章空间数据库引擎若干关键技术分析 之问的曲线上的离散点进行检测，确定下一批压缩后的保留点。用上述方法反复 进行，直至两端点之间的曲线离散点距两端点连线的距离的最大值小于给定的精 度限差为止。最后可得到满足给定精度限差的曲线压缩后的全部保留点。如图3 4 所示。 p一肖 图3 - 4d o u g l a s - p e u c k e r 算法原理示意图 d o u g l a s p e u c k e r 算法具有平移、旋转的不变性、给定曲线与距离限差后，抽 样结果一致的特点。但由于d o u g l a s p e u e k e r 算法只采用垂直距离d 为约束元素， 在d 较大时，容易造成图形失真和拓扑变形。特别地，当一段曲线的所有点都在 两保留点同侧，曲线较长且曲线内所有点与两保留点连线距离都小于d 时，该段 曲线内所有点都将被删除，从而造成面积精度损失。对于这种精度损失，可采用 径向约束算法f 1 6 1 加以改进。如图3 - 5 所示。 r 么兰兰王 兰兰皇s p q 图3 - 5d o u g l a s p e u c l ( e r 算法径向约束 当对曲线p q 进行压缩时，如果p q 内的点到p q 连线的距离都小于d 时，此 时，r 点仅在 p r i 和i q r i 都小于径向约束r 时不保留。采用径向约束可在一定程度 限制d o u g l a s p e u c k e r 算法的面积失真。 d o u g l a s p e u c k e r 算法是一个经典的矢量数据压缩算法，同时后人对其做出了 很多改进，包括拓扑约束改进”、基于点遍历算法的改进 1 9 - 2 1 1 等。 无损压缩中，通过缩减有效位数来压缩数据( 利用单精度数取代双精度数、 利用整数取代单精度数) 的原理相对简单，本文不再赘述。 1 5 电子科技大学硕士学位论文 3 2 空间索引 空问索引即是空间数据在二级存储器中存储位置的描述，只是空问数据并不 天然有序，不便于使用传统的排序方法处理。 由于空间数据的多样性，空间索引技术也相当广泛。本文着重对网格文件和r 树系列索引1 2 2 - 3 6 1 技术进行研究。 3 2 1 网格文件索引 网格文件是针对点目标索引而提出的l ，】【2 2 j 。设k 为空间的维度，则网格文件 由两个基本结构组成：( 1 ) k 个线性刻度o c l i n e a rs e a l e s ) ；( 2 ) 一个k 维目录。如 图3 - 6 所示。 线 性 刻 度 舍 暑 冀 嚣 巳 窖 网 格 目 录 6 寻 3 垒 旦 辽 图3 6 网格文件结构示意图 网格文件的基本思想是根据一个正交的网格( o r t h o g o n a lg r i d ) 划分k 维数据 空间。k 维数据空问的网格由k 个一维数组所表示的刻度所定义( 对图3 - 6 而言， 是两个一维刻度：x 1 5 1y 【l 一2 】) 。刻度的每一个边界构成一个k 1 维的超平面 ( h y p e rp l a n e ) ，这一超平面将数据空间划分为两个子空间，所有边界一起，将整 个数据空间划分为多个k 为矩形子空间，这些子空间成为网格目录( g r i dd i r e c t o r y ) ， 由一k 维的数组表示。耳录项和网格单元之间有一一对应关系( g r i dc e l l ) 。每一网 格单元包含一外存页地址，这一外存页存储了包含于该网格单元的数据目标，称 为数据页( d a t ap a g e ) 。数据页可存储多个网格单元目标，只要这几个网格单元形 成一矩形区域。数据页对应的一个或多个网格单元称为存储区域( s t o r er e g i o n ) 。 存储区域两两不相交，它们一起跨越整个数据空间。 1 6 第三章空间数据库引擎若干关键技术分析 网格文件的查询操作较简单，只需找到查询涉及的网格单元，并提取相应的 数据页，然后比较数据页的目标是否满足要求即可。对于点查询，只需访问一个 网格目录项及其对应数据页即可，对于区域查询，需访问与该区域相交的网格单 元及其对应的数据页，查询效率一般。 网格文件的插入相对复杂，首先通过定位网格单元，提取相应的数据页，如 果该页未满，则直接插入目标数据即可。如果该页已满，则需要分裂该数据页。 网格文件的删除同样需定位网格单元，提取对应的数据页，然后从记录中删 除目标，如果删除记录的存储区域与其相连接的存储区域共同拥有的记录数少于 某一阈值，则需要考虑存储区域的合并。 网格文件实现了磁盘的二次访问原则：首先是访问目录项，定位网格单元： 然后访问实际的数据页取得实际记录，所以，网格文件的搜索时间是较短的，尤 其对于精确匹配点的查找。网格文件的主要问题在于目录的存储，当空问维度较 高或数据量较多时，网格目录将变得非常庞大，每一次分裂都要增加很多目录项， 由于目录常存于外存，对其存取代价较高。同时，当索引非点状目标时，需要采 取目标近似与目标映像或允许目标重复存储的策略，区域查询效率较差。 3 2 2r 树索引 3 2 2 1r 树的定义 r 树索引是基于空间划分策略的索引，始于g u t t m a n l 9 8 4 年提出的r 树m l 。 r 树是一棵高度平衡树，是b 树在k 维上的自然扩展，r 树利用对象的最小包围 矩形( m b r ) 来表示对象，并具有如下特这： 1 ) 每个叶节点包含m 至m 条索引记录( 其中m m 2 ) ，除非它是根节点。 2 ) 对于叶节点上的每条记录( i ，t u p l e i d e n t i f i e r ) ，t u p l e - i d e n t i f i e r 是空间对象 元组标志符号，并唯一对应空问数据库数据对象。i 是t u p l e - i d e n t i f i e r 对应的空间 对象的最小外围矩形。 3 ) 每个非叶节点至多有m 至m 个子节点，除非它是根节点。 4 ) 对于非叶节点中的每条记录( i ，t u p l e _ i d e n t i f i e r ) ，i 是其对应子节点中所有 矩形的最小外围矩形，t u p l e i d e n t i f i e r 是子节点指针。 5 ) 根节点至少有两个孩子，除非它是叶节点。 6 ) 所有叶节点出现在同一层。 树的每个节点对应于一个逻辑页面，每个节点包含一组项，格式为( i ， 1 7 电子科技大学硕士学位论文 t o u p l e i d e n t i f i e r ) ，其中i 为m b r ，用，= ( ，厶一i ) 表示，其中在沿i 方向的 一个闭合区间【a ，b 】上。用a 、b 或者两个都是无穷大来表示。 r 树的一个空间区域划分如图3 7 所示。 图3 - 7 一个空间对象集的r 树划分 + 该对象集对应的r 树如图3 8 所示。 r 图3 - 8 r 树层次结构 3 2 2 2r 树查询 基于r 树的点查询和区域查询通过自顶向下的方法迸行【2 3 l 。其算法如下： 。a l g o r i t h mr _ - s e a r c h ( n ，m 产在根节点为n 的r 树中查找所有与w 相交的数据矩形， b e g i n i f n l e v e l = 0t h e n ni sal e a f n o d e r e t u r na l ld a t ar e c t a n g l e st h a ti n t e r s e c tw i t hw e l s e f o r i ：= lt b n c o i ，n t d o 第三章空间数据库引擎若干关键技术分析 b e g i n i f n m b r i i n t e r s e c tw i t hw t h e n r s e a r c h ( n o p e l ，、聊； e n d ： e n d ；， 由此算法可以看出，r 树的搜索性能取决于两个参数：覆盖( c o v e r a g e ) 和交 叠( o v e r l a p ) 。树的某一层覆盖是指这一层所有节点的m b r 所覆盖的区域，覆盖 是对静态空间的衡量。树的某一层的交叠是指在该层上被多个与节点关联的矩形 所覆盖的全部区域。交叠使得查找_ 个对象时必须访问多个节点。r 树的这个问题 意味着，即使尽量减少交叠，其搜索的最差性能仍然是无法估量的。 3 2 2 3r 树插入 r 树插入一个空间目标，从根节点开始，检查所有的目录矩形，按照“最小覆 盖面积” 2 3 1 法则找出一个索引项： ( 1 ) 包围新目标后，目录矩形的“面积”增量最小的项。 ( 2 ) 如果增量相同，目录矩形“面积”最小的索引项。 然后对选中的索引项对应的子树按照“最小覆盖面积”优化原则进行递归式 搜索，直到叶子节点。若叶子节点未满，则直接插入，然后上溯更新父节点目录 矩形直至根节点，若叶子节点己满，插入新目标将导致叶节点溢出，这时，需进 行节点分裂，同时，节点分裂可能向上传播。r 树插入的算法描述如下： a l g o r i t h mr _ h l s e r t ( n