（计算机软件与理论专业论文）空间索引技术在电力gis中的研究与应用.pdf

t_r古 独创性声明 舢l i f | l l l | i i i | i l l | l l | | l | | i f i l | f i i l l f f l | i f i 哪 y 18 0 2 6 0 9 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 日期：矽p 年歹月呼日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 虢耻 聊签名：谫栉导师签名： 竺圣：兰 日期：岔o 0 年厂月2 么日日期：驴o o 年j 月2 匕日 气、9 y ，v 摘要 摘要 在信息技术不断发展和进步的过程中，人们处理信息的手段日益多样化，这 也促进了智能化企业管理方式的诞生，电力g i s ( g e o 簪a p h i ci n f o 咖a t i o ns y s t 锄， 地理信息系统) 就是在这样的背景中成长起来的。 电力g i s 系统是将传统的g i s 技术，尤其是w 曲g i s 技术应用到电力行业， 并融合已有的m i s 系统，采用可视化界面和文字数据混合的处理方式，为电力行 业各职能部门和广大用户提供最优化配网模式的智能化分析管理系统。 电力g i s 系统需要对各种空间数据进行有效处理，这就要求有一个高性能的 空间索引结构。电力行业的空间数据又有其特殊性：点、线要素较多，多边形要 素较少，并且个别线要素可能跨越整个地理空间范围。传统的基于格网的索引会 使线要素跨越多个网格，从而导致较多的冗余存储，加大系统的存储开销；基于 对象的索引会使用目标近似技术对空间对象进行近似处理，但这样的处理方式会 使线要素失真，不利于空间对象的查询操作。所以寻找一种适合电力配电系统的 索引结构显得非常重要。 本文在大量阅读中外相关文献资料的基础上，对基于格网的索引和基于对象 的索引进行了分析和对比，并结合配网系统特性，提出了一种适合电力配电网络 的混合索引机制，其设计思想是先将待索引地理空间进行粗网格划分，建立基于 固定格网的一级索引，进行粗分的目的是为了减少跨网格空间对象数量；然后对 完全包含在网格区域内的空间对象建立聚类h i l b e nr 树，这是二级索引；最后为 跨网格的空间对象建立索引链表。这样，对于配电系统中较长的输电线路，虽然 跨越了多个网格，但其索引信息被存放在链表中，既克服了基于格网的索引将其 索引信息存放在多个磁盘页而造成的冗余存储问题，也避免了基于对象的索引中 因为线对象的失真而引起的节点数据矩形重叠率过高的问题。 混合索引机制的二级索引聚类h i l b e nr 树是本文在h i l b e nr 树基础上引 入k 平均聚类算法，对h i l b e nr 树叶节点再聚类，使同一节点的数据集合更加紧 凑，而不同节点数据集合的重叠率更小的空间索引结构。聚类h i l b 觎r 树在查询 效率方面有较好的表现，从而使混合索引的整体性能有较大提高。 在本文的最后，将混合索引机制和心c s d e 的层次格网索引以及纯r 树索引 应用于实际的电力g i s 系统进行了对比实验，实验结果表明，混合索引机制在实 摘要 统，格网索引，聚类h i l b e n r 树索引 i l t 0 铆 0 1 h ， ，v a b s t r a ( 玎 a b s t r a c t a si n f o 肌a t i o nt e d m o l o g yc o n t i i m e st oe v 0 1 v ea i l dp r o 皆e s s ， t h em e a n so f p r o c e s s i n gi n f o 彻a t i o no fp e o p l eh a v ei n c r e a s i n 哲yd i v e r s i f i e d ，a 1 1 di tc o 枷b u t e dt ot h e b i n ho fi n t e l l i g e n te n t 唧r i s em a l l a g e i l l e n t 1 1 1 仳sb a c k g r o u n d ，p o w e rg i s ( g e o 伊a p h i c 1 1 1 f o m a t i o ns y s t e m ) i s 伊o w i n gu p p o w e rg i si sa i li n t e l l i g e n ta n a l y s i sa 1 1 dm a i l a g 锄e n ts y s t e mw i l i c hm a k e st h e 昀d i t i o n a lg i st e c h n 0 1 0 9 y ，p 射i c u l a r l yw 曲g i st e c l m o l o g ya p p l yt ot h ep o w e r i n d u s 仃ya n di n t e 野a t e st h ee x i s t i n gm i ss y s t e mo ft h ep o w e ri n d u s t 够i tu s e sh y b r i d a p p r o a c ho fv i s u a li n t e r f a c ea i l dt e x tt op r o v i d eo p t i m u mp o w e rd i s t d b u t i o nn e t w o r k m o d e lf o rp o w e ri n d u s 时o ru s e r so fv 撕o u s 向n “o n a ld 印a n m e n t s p o w e rg i sn e e d st od e a lw i t hav 撕e t yo fs p a t i a ld a t ae a e c t i v e l y ，s oi tr e q u i r e sa h i 曲- p e r f o 彻a n c es p a t i a li n d e xs t r u c t u r e h o w e v e r ，t h es p a t i a ld a t ao fp o w e ri n d u s t 巧 h a si t sp a r t i c u l a r i t y ，f o re x a m p l e ，t h e r ea r em o r ep o i n te l e m e n t sa n d1 i n ee l e m e n t s ，b u t f e w e rp o l y g o ne l e m e n t s ，a n ds o m ei n d i v i d u a l l i n ee l e m e n t sm a ys p a nm ew h o l er a j l g e o fg e o 伊a p h i c a ls p a c e t h et r a d i t i o n a li n d e xm a tb a s e do n 鲥dw i l lm a k em e1 i n e e l e m e n t sa c r o s sm u l t i p l e 鲥d s ，s oi tw i l ll e a dt om o r er e d u n d a j l ts t o r a g ea n di n c r e a s e t h es t o r a g ep r e s s u r eo ft h es y s t e m t h et r a d i t i o n a li n d e xt h a tb a s e do no b j e c tw i l lu s e t h et e c h n o l o g yo f r i a 唱e ta p p r o x i m a t i o nt os p a t i a lo b j e c tw i t h 印p r o x i m a t et r e a t m e n t h o w e v e r ，m i sa p p r o a c hw i l ll e a dt h e1 i n ee l e m e n t st od i s t o r t i ti sn o tc o n d u c t i v et o s p a t i a lq u e 辑s oi ti sv e r yi m p o n 觚tt ol o o kf o ran e w i n d e xs t m c t u r e 、油i c hi ss u i t e d f o rp o w e rd i s t r i b u t i o ns y s t e m i no r d e rt om e e tm ec h a r a c t e d s t i c so fm ep o w e rd i s t r i b u t i o nn e 仰o r k ，m i sp a p e r h a sa n a l y z e da i l dc o n t r a s t e dt h e 鲥d - b a s e di n d e xw i t ho b j e c t - b a s e di n d e x 1 1 1t 1 1 ee n d ，i t p r o p o s e san e wm i x e di n d e x i n gm e c h a n i s mw h i c hi ss u i t e d f o rp o w e ri n d u s 吼t h e i n d e x i n gm e c h a n i s mp a r t i t i o n sm er e s e a r c hr e 百o nt ol a r g e 鲥d ，a n de s t a b l i s h e sm e f i r s t i n d e x c o a r s e p o i n to b j e c t i v ei s t or e d u c et 1 1 em m l b e ro fi n t e r _ 鲥ds p a c eo b j e c s t t h e n ， i te s ta _ b l i s h e sm es e c o n di 1 1 d e xf o r t h es p a c eo b je c t sw h i c ha r em l l yi n c l u d e di nt h es a m e 鲥d b a s e do nc l u s t i n gh i l b e nr t r e e f i n a l l y ，i te s t a b l i s h e si n d e x e d1 i s tf o r t h ei m 昏鲥d s p a t i a lo b je c t s t h u s ，t h el o n gt r a n s m i s s i o n1 i n e so i t h ed i s t m u t i o ns y s t e n ns p a n l l i o v e r c o m em er e d u n d 觚ts t o r a g ep r o b l 锄i i lm e 鲥d - b a s e d i n d e x ，b u ta l s ot 0a v o i dt h e d i s t o r t i o np r o b i e mo f1 i n ee l e m e n t si nt h eo b i e c t b a s e di n d e x n es e c o n di n d e x - c l u s t 嘶n gh i l b e nr t r e ei san e ws p a t i a l i n d e xs t m c m r eb a s e d o nh i l b e nrt r e e i th a sm a d es 9 m ei m p r o v e m e n t so nt h eh i l b 耐rt r e e t 1 1 r o n g l l i n t r o d u c t i n gk - m e a n sc l u s t e m ga l g o r i 姗1 1 1 en e ws t m c t u r em a l 【e sm ed a t as e t si nm e s 锄el e a tn o d em o r ec o h l p a c ta n dt h ed a t as e t si nm ed i 虢r e n tl e a fn o d eo v 甜印s m a l l e r t h ec l u s t e r i n gh i l b 积rt r e eh a sb e t t e rp 幽m l a n c ei nt h eq u e r y e 伍c i e n c ya n dt h u st h e o v e r a l lp e r f o 咖a c eo fm em i x e di n d e xh a si i n p r o v e d 盯e a t l y f i n a l l y ，t h ei n d e x i n gm e c h 孤i s ma n dt h ep u r er 仃e e i n d e x ，a n dt h el e v e l 刚di n d e x o fa r c s d ei su s e di nt h e p r a c t i c a lp o w e rg i ss y s t 锄t h ec o m p a r e de x p e m n e n ts h o w s t h a tt h em i x e d i n d e x i n gm e c h a n i s mi np r a c t i c a la p p l i c a t i o n sm o r ep r a c t i a l k e y w o r d s ：s p a t i a li n d e x ，p o w e rg i s ，g r i di n d e x ，c 1 u t e r i n gh i l b e r tr t r e ei n d e x i v 簟l ；，v 目录 目录 第一章绪论1 1 1 研究背景及意义1 1 2 国内外研究现状2 1 3 科研支撑项目3 1 4 本文的研究内容3 1 5 本文的组织安排4 第二章空间数据库相关理论6 2 1 空间数据及其特征6 2 2 空间数据类型7 2 3 空间关系8 2 4 空间数据模型9 2 5 本章小结1 0 第三章空间数据库索引技术及其算法研究1 1 3 1 空间索引技术的提出1 1 3 2 基于格网的索引研究1 3 3 2 1 基于固定格网的索引1 3 3 2 2 基于层次格网的索引1 5 3 2 3 自适应层次格网索引1 7 3 - 3 基于对象的索引研究1 8 3 3 1r 树索引18 3 3 2r + 树索引2 1 3 3 3r 宰树索引2 3 3 3 4h i l b 耐r 树索引2 4 v 目录 3 4 本章小结2 6 第四章一种适合配电系统特性的混合索引机制2 7 4 1 适合配电系统的索引结构探析2 7 4 1 1 影响索引效率的因素2 7 4 1 2 基于树的索引和基于格网的索引分析2 7 4 2 适合配电系统的混合索引机制2 9 4 2 1 混合索引设计策略2 9 4 2 2 混合索引机制3 0 4 3 二级索引一基于k - 平均聚类算法的聚类h i l b e r tr 树3 2 4 3 1k 平均聚类算法3 3 4 3 2 基于k 平均聚类算法的数据划分策略3 4 4 3 3 聚类h i l b 鲋r 树中节点的数据结构3 6 4 3 4 聚类h i l b e nr 树的插入算法3 8 4 3 5 聚类h i l b e nr 树的查询算法4 0 4 3 6 聚类h i l b e nr 树的删除算法4 1 4 4 混合索引机制的动态操作及算法4 1 4 4 1 混合索引的插入算法4 1 4 4 2 混合索引的查询算法4 2 4 4 3 混合索引的删除算法4 3 4 5 本章小结4 4 第五章混合索引在电网可视化管理系统中的应用。4 5 5 1 电力配电系统g v m s 2 o 概述4 5 5 2g v m s 2 o 系统的数据模型4 7 5 2 1g e o d a t a b a s e 模型4 8 5 2 2g e o d a t a b a s e 模型在g v m s 2 o 系统中的应用4 9 5 3g v m s 2 o 系统数据的组织5 0 5 3 1 传统三层数据组织模式5 0 5 3 2 适合配网线路操作的数据组织模式5 2 目录 5 4g v m s 2 o 系统数据的存储5 3 5 5 混合索引机制在配电系统中的性能评估5 4 5 5 1 评估标准5 5 5 5 2 评估过程5 5 5 5 3 索引建立过程分析与对比5 6 5 5 4 索引插入操作分析与对比5 7 5 5 5 索引删除操作分析与对比5 8 5 5 6 索引查询操作分析与对比5 9 5 6 本章小结6 0 第六章总结与展望6 1 6 1 工作总结6 1 6 2 工作展望6 2 至定谢。6 3 参考文献6 4 攻硕期间取得的研究成果6 6 v i i 第一章绪论 1 。1 研究背景及意义 第一章绪论 地理信息系统起源于上世纪六十年代，是在计算机科学、地理学、空间科学、 测绘学和地图学等多种学科基础上发展起来的具有独立学科体系的学科，是空间 信息科学与技术的一个重要组成部分。作为获取、管理、处理和分析空间数据的 重要技术和工具，地理信息系统已经在国民经济的各个领域有着深入的研究和广 泛的应用。我们的世界是立体的有方位的，所以世界上大多数信息都与空间位置 有关，随着人类获取空间数据的能力不断提高和信息空间化技术的发展，地理信 息系统的应用将会提升到一个新的深度和广度【1 1 。电力g i s ( g e o 酉a p h i ci n f o m a t i o n s y s t e m ，地理信息系统) 就是在这样的背景中成长起来的。 电力g i s 系统是将传统的g i s 技术，尤其是w 曲g i s 技术应用到电力行业， 并融合已有的m i s 系统，采用可视化界面和文字数据混合的处理方式，为电力行 业各职能部门和广大用户提供最优化配网模式的智能化分析管理系统【2 1 。近年来， 随着我国国民经济水平的提高，人们的用电需求日渐增大。面对日益密织的电网 和各种复杂的电力设备，电力部门的管理负荷日益显著。随着城市建设的不断发 展，道路和建筑的规划频繁变化，这给电网的设计、布线和管理带来了压力。为 了缓解用电质量与管理困难之间的矛盾，利用电力g i s 系统进行辅助管理越来越 受到各电力部门的关注与重视。 为了从复杂而巨大的数据集合中获取最有效的信息，电力g i s 系统必须借助 相关技术以简化数据存储、组织和检索工作，从而实现对海量数据快速有效的存 取和利用。采用空间数据库系统来管理空间目标已成为目前的主流方式。但空间 目标往往具有不规则的几何形状( 如电力g i s 系统中的杆塔、配电线路、变压器 等设备) ，并且各目标之间有较为复杂的空间拓扑关系( 如邻接、包含等) ，空间 目标之间也没有规则的次序，利用空间数据库处理空间对象比起传统的关系数据 库需要付出更高的计算代价【3 】。因此，为空间数据库设计高效的索引结构和算法， 就成为提高各种空间数据库性能的关键。 当前各大主流g i s 厂商提供的索引算法是一种大众算法，它需要达到以一应 百的效果，即索引算法应该适合大多数g i s 应用场合。但电力行业的空间数据有 电子科技大学硕士学位论文 其特殊性：点、线要素较多，多边形要素较少，并且个别线要素可能跨越整个地 理空间范围。所以这样的大众算法就不再适合电力g i s 行业，利用传统索引算法 设计思想，结合电力数据的特性，设计一种适合电力g i s 行业应用的空间索引具 有一定研究意义。 1 2 国内外研究现状 文献 4 】对空间索引有这样的定义：空间索引是将空间目标的地理位置、大小 或者它们之间的拓扑或几何网络关系，按照指定的某种顺序排列的一种数据结构； 其实质是通过对空间目标进行空间范围的排列组合，使系统进行检索时减少对磁 盘的访问开销，以达到对空间数据的高效获取。 空间索引中存有空间目标的基本信息，比如：空间目标的唯一标识符、最小 外接矩形( m b r ) 左下角和右上角点的坐标以及指向空间目标具体存储位置的指 针等信息。在实际应用中，对空间索引的使用介于空间目标和空间操作之间，通 过空间索引的筛选，排除了大量与指定操作无关的空间目标，从而减少了系统访 问磁盘页的i 0 开销，进而提高了系统响应效率。如在电力g i s 中经常用到的邻 接查询操作找到全网所有高压线路，在没有空间索引的情况下，对高压线路 的查询，需要对空间数据库进行全扫描，找出全网所有高压变压器集合，然后对 这个集合进行全扫描，找出所有与高压变压器关联的高压线路；对于含有成千上 万个高压变压器的海量数据库而言，这样的全扫描操作对系统来说无疑是一个天 文数字的开销，这大大降低了系统的响应效率；空间索引高效的筛选能力在这样 的情况中显得非常有效。 在空间数据呈指数增长的今天，为海量空间数据库设计高效的空间索引显得 非常必要。一个高效的空间索引结构通常需要满足较高的更新效率、较小的存储 开销、较小复杂性的索引算法和较高可扩展性等要求。空间索引技术经过几十年 的发展与演进，国内外学者提出了很多不同的索引结构和算法，主要分为以下三 类【5 】： ( 1 ) 基于空间映射技术的索引 基于空间映射技术的索引主要应用于高维空间向一维空间映射，然后利用成熟 的一维索引技术建立空间索引【6 】。其基本思想为：通过某种策略将地理空间划分为 许多大小相同的格子，然后对每个格子按照某种算法进行编码，使每个格子具有 唯一的编码，最后用这些编码为各空间对象赋予一个具有意义的数字。这种构建 2 第一章绪论 空间索引的方式其关键在于进行高维到一维的映射必须较好的保存了各空间对象 间的空间关系，因为只有这样才能提供较高的查找性能。 ( 2 ) 基于空间分割技术的索引 基于空间分割技术的索引不允许空间对象重叠，如网格索引 7 】 1 7 、r + 树索引。 其基本思想为：按照某种划分方法将地理空间的高维数据划分为多个互不相交的 子空间，然后将这些子空间中对应的空间对象按照复制( 将落在多个子空间的数 据对象重复存储在多个磁盘页上) 或裁剪( 将落在多个子空间的数据对象进行裁 剪使各子对象互不相交，然后将各子对象分别存储在对应的磁盘页上) 的方式将 空间对象存储在对应的磁盘页上。这种索引建立方式有利于点查询，因为这样的 分割方式使其查找路径只有一条，减少了搜索分支的数目，从而提高了系统的查 询效率。 ( 3 ) 基于空间界定技术的索引 基于空间界定技术的索引允许空间对象之间重叠，如r 树 8 1 7 。其基本思想为： 按照某种策略将地理空间划分为多级的子空间，各级子空间允许重叠，且空间对 象在各磁盘页只用存储一次。对于这种索引建立方式，需要尽量减小各子空间的 重叠率，因为重叠过高，对于查询操作会增加搜索分支的数目，从而加大系统的 响应时间。 对于上述三类索引建立方式，既有优点也有缺点，事实上，建立一种十全十美 的索引结构，在当前的技术范围内还达不到，在实际应用中，多将各种索引结合 使用，将其优势发挥到最大，而使其缺点最小化。 1 3 科研支撑项目 本文依托电子科大四川华雁联合实验室项目“电网可视化管理系统2 o ( g r i d s u a l i z a t i o nm a n a g e m e n ts y s t e m2 0 ，简称g v m s 2 o ) 的实施，致力于适合电力 g i s 配网的空间索引研究和应用。 1 4 本文的研究内容 在大量阅读各种相关参考文献的基础上，本文对传统空间索引技术进行了分 类比较，结合电力g i s 行业空间数据的特性，提出了一种适合配电系统特性的混 合索引机制，并在电网可视化管理系统中验证了其实用性。本文研究的主要内容 电子科技大学硕士学位论文 如下： ( 1 ) 从基于格网和基于对象两个角度对传统的经典索引算法从索引建立、索引 的动态操作、索引的应用领域进行了分类讨论，并分析了各自的优缺点， 为混合索引的提出奠定了基础。 ( 2 ) 针对电力g i s 行业空间数据的特性，并结合基于格网和基于对象索引结构 的优缺点，提出了一种适合配电系统特性的混合索引机制基于粗分格 网和聚类h i l b e r tr 树的混合索引。其中，聚类h i l b e r tr 树是本文在h i l b e r t r 树基础上引入k - 平均聚类算法对其叶节点再聚类，避免了h i l b 酣r 树 各叶节点目录矩形面积过大、重叠率过高而引起的查询性能低下问题。通 过对叶节点的再聚类，h i l b 甜r 树同一节点的数据集合会更加紧凑，而不 同节点的数据集合重叠率会更小，从而减少了系统访问磁盘页的时间，提 高了访问效率。 ( 3 ) 在对g v m s 系统测试和改进的过程中，采用m i c r o s o j f i s u a ls t u d i o2 0 0 8 平台，利用c + + 编程语言，将混合索引机制应用于g v m s 配网系统，通 过与a r c s d e 的基于层次网格的索引机制以及纯r 树索引机制的对比实 验，验证了混合索引机制在电力g i s 行业的实用性。 1 5 本文的组织安排 本论文分为六章，其结构组织如下： 第一章绪论 首先简要介绍了空间索引技术及其研究现状，然后阐述了在电力g i s 行业研 究空间索引技术的必要性和重要性，最后概述了本论文研究的主要内容及论文的 组织安排。 第二章空间数据库相关理论 首先详细介绍了空间数据、空间数据特征、空间数据类型以及空间关系相关理 论，然后介绍了空间数据库的三种模型以及空间数据的存储结构。 第三章空间数据库索引技术及其算法研究 首先对空间索引技术做了简要介绍，然后对传统空间索引结构进行分类讨论， 并分析了其优缺点，为后文混合索引机制的提出奠定基础。 第四章一种适合配电系统特性的混合空间索引机制 首先详细分析了影响配电系统索引效率的主要因素，然后对基于格网的索引 4 第一章绪论 和基于对象的索引进行比较，提出了一种适合配电系统特性的混合索引机制。在 介绍了混合索引设计的策略和机制之后，详细阐述了聚类h i l b e r tr 树的设计思想 及其对h i l b e nr 树的改进；最后给出了混合索引机制的各种动态操作及算法。 第五章混合索引机制在g v m s 2 o 系统的应用 首先对电网可视化管理系统( g v m s 2 0 ) 系统及其功能模块做了简要介绍； 然后详细介绍了g v m s 系统的电力数据在空间数据库中的组织与存储；最后将混 合索引、觚s d e 基于层次格网的索引以及纯r 树索引应用于g v m s 系统，并它 们的实用性做了评估。 第六章总结和展望 首先总结了本论文所完成的主要工作，然后对工作中待改进的地方做了规划 和展望。 图像处理、自然资源 分布有关的，一般都 以在传统的关系数据 库中存储、表示、查询和管理空间数据存在一定缺陷，对它们的操作需要一些特 殊的方法，这也就促进了空间数据库这一研究领域的快速发展。 2 1 空间数据及其特征 空间数据是对现实世界进行抽象之后用于描述空间实体的数据，不仅可以用 于描述空间实体的位置、大小、形状及分布状况等多方面的信息，还可以表示空 间实体的空间关系及属性信息，可以用点、线、面等基本空间数据结构来表示。 例如在电力g i s 行业中，把杆塔抽象为点，河流抽象为线，行政区和湖泊抽象为 面。空间数据是用来描述现实世界的实体目标，一般具有定位、定性、时间以及 空间等特征。在已知的坐标系里各空间实体都具有唯一的空间位置，这就是定位； 而定性是指空间实体的相关自然属性，如长度、高度、宽度等；时间指的是空间 实体随着时间的变化而变化；空间关系则指各空间实体间的拓扑关系，如相邻、 包含、相交等。 一般的数据具有选择性、时间性、可靠性、完备性等基本特征，空间数据除 了具有以上基本特征，还具有以下特征【1 0 j ： ( 1 ) 空间性。 空间数据并不是独立存在的，除了描述空间地物本身的定位定性特征，还描述 了空间实体间复杂的拓扑几何关系。如在配网系统中，描述一个杆塔，一般数据 侧重于杆塔的高度、材质等；而空间数据则侧重于杆塔的坐标位置、倾斜角度以 及与之关联的绝缘子个数；复杂一点还要描述该杆塔与邻近杆塔的距离等空间关 系。空间性是空间数据区别于一般数据的关键特征，是空间数据最主要的特征。 ( 2 ) 抽象性 空间数据描述的是现实世界中复杂的地貌特征，所以必须对空间地物进行抽 象处理之后才能存储于数据库中。空间对象可以被抽象为点、线、面要素，对于 6 第二章空间数据库相关理论 不同的应用环境，抽象标准也有所不同。在电力行业中，河流被抽象为线要素； 而在水利行业中，河流却被抽象为面要素。空间数据的抽象标准需要人为定制， 具有不确定性。 ( 3 ) 多尺度与多态性 对于同一地物，选取的比例尺和精度不同会产生形态差异，这就是空间数据 的多尺度和多态性。空间数据的这一特性很常见，比如在大比例尺中，一栋建筑 通常被抽象为面要素，而在小比例尺中却被抽象为点要素。这种将同一地物进行 不同形态的抽象就是空间数据的多态性。 ( 4 ) 多时空性 空间数据有很强的时空特性。一方面，空间数据可以在同一时间表现为不同 的空间序列；另一方面，在同一空间中，对同一地物又有不同的时间序列。空间 数据是不同时空和不同尺度数据源的集成。 2 2 空间数据类型 根据不同的观察角度、尺度特征和空间维数，可以将空间数据抽象为点、线、 面 1 1 1 三种数据类型，如图2 1 ： 嘉瑟赫濂纛譬 t 秘笺? j2 ：t j 。? ：一1 1 强_ l 善雾1 ：。“落辆菱：t “缸j 秀 蓥7 哮赫琴凌l ： 图2 1 三种基本要素：点、线、面 7 电子科技大学硕士学位论文 点( p o i n t ) 要素，是指可以用一对空间坐标( 五) ，) 、一个识别码和若干属性描 述标识来表示的空间实体。点是零维几何实体，不占任何空间，没有面积和体积。 点状目标是空间上的最小地理实体。实际上，地面上真正的点状地物很少，一般 都占有一定的面积。这里的点是指那些本身面积很小，但又必须定位的事物。其 实，点状目标和面状目标并没有严格的区分，正如上文所述，在不同的应用行业， 河流既可以表示为点状目标，也可以表示为面状目标。 线( l i n e ) 要素，是指用一个坐标序列眠l ，y 。) ，b ：，y ：) ，k ，y 。) ) 、一个识别 符和若干属性描述标识来表示的空间实体。任何连续而复杂的线状空间实体都可 以用线要素的坐标序列来表示。如g i s 系统中的河流、公路、边界线等。不过在 实际生活中，河流、公路、省界线并不是单纯的线目标，它们其实具有一定的面 积，所以，在不同的比例尺和应用环境下，这些具有宽度和面积的地物会用双线 或者条带状的面要素表示，而不是单纯的用线条来描述。 面( m e a ) 要素，或称多边形( p o l y g o n ) 要素，是指用一个坐标序列 ( g ，y 。) ，g ：，y ：) ，g 。，y 。) ，g ，少。) ) 、一个识别符和若干属性描述标识来表示的空间 实体。面要素是带有位置和边界的空间范围，它是最重要的一种描述空间信息的 数据类型。空间数据库中的面要素通常是空间地物经过目标近似处理后形成的简 单几何形体。如公路和河流可以用线段的组合来表示，而国家、省则用多边形来 表示。 地理空间中的任何地物都可以通过点、线、面要素来表示。空间区域( r e 西o n ) 可以按照一定的地理意义由点、线、面组成，有时称之为数据平面( d a t ap l a n e ) 。 地理信息系统中的各种专题图都可以表示为一个数据平面。点、线、面是g i s 系 统中不可或缺的基本地理要素。 2 3 空间关系 现实世界的地物要存储于空间数据库中，除了需要将它们抽象为上述点、线、 面空间对象外，还需要判定空间地物的方位联系，即空间关系。文献 1 2 1 2 】中将 空间关系划分为度量、方位和拓扑等三大类关系。 ( 1 ) 空间度量关系 空间度量关系即空间距离关系。空间实体间的关系是用度量空间中的某种度 量指标描述的。在实际应用中，地理空间通常被描述为欧式空间，因为欧式空间 中的距离等价于现实世界中地物间的真实距离。欧式距离又存在如飞机航线的直 第二章空间数据库相关理论 线距离和如铁路运输的旅行距离的区别。 ( 2 ) 空间方位关系 空间方位关系又称为空间顺序关系，是空间实体在真实世界中的某种顺序联 系，如上下左右、东南西北等。 ( 3 ) 空间拓扑关系 空间拓扑关系是指在任意拓扑变换下的拓扑不变量，如空间实体间的相邻 ( a d j a c e l l t ) 、相离( d i s j o i n t ) 和包含( i n s i d e ) 关系，以及表示线段流向( n o w d i r e c t i o n ) 的关 系等。最基本的拓扑关系包含以下5 种：关联、邻接、包含、几何、层次。 一般，空间对象间的空间关系与对象的形态、维数等属性有关，所以空间对象 间的关系是复杂多样的。 2 4 空间数据模型 数据模型 13 】是用来描述现实世界中的事物及联系在数据库中的体现。数据模 型是衡量数据库能力强弱的重要指标，所以数据模型是数据库的核心。数据库系 统一般具有三级模式的体系结构，即内模式( i n t e m a ls c h e m a ) 、概念模式( c o n c e p t u a l s c h e m a ) 和外模式( e x t e m a ls c h e m a ) 。外模式也称作子模式，它通常用外模式语 言表示，它是被数据库用户看到的数据视图，即与某一应用有关的数据的逻辑表 示；内模式通常用内模式描述语言来描述和定义，它是全体数据库结构的内部表 示或者底层描述，用来定义数据的存储方式和物理结构；概念模式通常用实体一联 系法来描述，它是一个部门或组织所对应的现实世界的真实模型，它独立于具体 的计算机系统。 空间数据模型是一种用来描述空间数据组织的概念集合，它是一种具有特定 性质的数据模型，还包含对大量空间实体和关系的归纳。不同数据模型由不同的 的归纳方法推导出。在空间数据库设计中，空间数据模型所提供的概念空间 实体的分类、实体的维数及其拓扑关系等，它们构造了数据库模式。可以把空间 数据模型映射为概念数据模型或直接映射为逻辑数据模型。它与数据库系统的三 级模式结构和三种数据模型之间的相互关系如图2 2 所示。 通常由完整性约束条件、数据操作和数据结构这几个条件组成了数据模型。 完整性约束是一种规则集合，该集合由给定的数据模型中数据及其联系所具有的 制约和依存规则组成，它的作用在于限制复合数据模型的数据库状态及状态的变 化，从而保证数据的相容性、有效及正确。数据操作是一种操作集合，构成该集 9 电子科技大学硕士学位论文 合的是对数据库中各种对象的实值允许执行的操作，它动态性的描述了系统，以 及检索、更新等操作的定义、与之相关的操作符号、操作规则及实现操作的语言 的精确定义。数据结构是一种对象类型的集合，该对象类型是所研究的对象，它 描述了系统的静态特性。对象是数据模型的基础，它主要有两大类，即与数据之 间联系有关的对象和数据类型、内容、性质有关的对象。这些对象组成了所有符 合某种模型的任何数据库的逻辑结构。 2 5 本章小结 图2 2 空间数据模型、数据模型以及数据库模式间的关系 本章首先概述了什么是空间数据库以及空间数据库的作用，然后详细介绍了 空间数据、空间数据类型以及空间关系相关理论，最后阐述了空间数据模型与数 据库模式间的关系。 l o 第三章空间数据库索引技术及其算法研究 第三章空间数据库索引技术及其算法研究 3 1 空间索引技术的提出 空间索引是将空间目标的地理位置、大小或者它们之间的拓扑或几何网络关 系，按照指定的某种顺序排列的一种数据结构【1 4 】【1 4 】【1 5 】；其实质是通过对空间目标 进行空间范围的排列组合，使系统进行检索时减少对磁盘的访问开销，以达到对 空间数据的高效获取。 在空间索引中存有空间目标的基本信息，比如：空间目标的唯一标识符、最 小外接矩形( m b r ) 左下角和右上角点的坐标以及指向空间目标具体存储位置的 指针等信息。在实际应用中，对空间索引的使用介于空间目标和空间操作之间， 通过空间索引的筛选，排除了大量与指定操作无关的空间目标，从而减少了系统 访问磁盘页的i o 开销，进而提高了系统响应效率。如在电力g i s 中经常用到的 邻接查询操作找到全网所有高压线路，在没有空间索引的情况下，对高压线 路的查询，需要对空间数据库进行全扫描，找出全网所有高压变压器集合，然后 对这个集合进行全扫描，找出所有与高压变压器关联的高压线路；对于含有成千 上万个高压变压器的海量数据库而言，这样的全扫描操作对系统来说无疑是一个 天文数字的开销，这大大降低了系统的响应效率；空间索引高效的筛选能力在这 样的情况中显得非常有效。 在空间数据呈指数增长的今天，为海量空间数据库设计高效的空间索引显得 非常必要。一个高效的空间索引结构通常需要满足较高的更新效率、较小的存储 开销、较小复杂性的索引算法和较高可扩展性等要求。空间索引技术经过几十年 的发展与演进，国内外学者提出了很多不同的索引结构和算法【1 6 】【1 7 】【1 8 1 【1 9 】【2 0 1 。由图 3 1 可知，空间索引结构大致可分为基于二叉树的索引、基于b 树的索引、基于哈 希表的格网索引以及基于空间填