（计算机应用技术专业论文）空间数据索引技术的研究及在gis中的应用.pdf

大连理工大学硕士学位论文 摘要 空问数据库已广泛地应用于g i s 、c a d 、机器人、计算几何、计算机视觉、医学图 像和多媒体系统等领域。随着数字城市、数字地球、数字流域等概念的提出与应用，对 空间数据的存储与处理提出了更高的要求。空间数据索引是提高空间数据库性能的关键 技术，它直接影响空间数据的存储效率以及空间检索的性能。研究空间数据索引技术并 寻求更好的空间数据索引机制，己成为当前计算机领域及其它应用领域的一个热点问 题。 在一些非标准的数据库应用系统，例如地理信息处理系统、c a d c a m 系统，常常 需要在外存中存取多维地理数据，同时需要对这些数据进行精确匹配查询和范围查询。 目前的空间索引中，特别是流行的基于b 树的r 树及其变种的结构，在需要在外存中频 繁存取、处理多维空间数据方面有明显的缺陷。同时，随着索引数据量的巨增，特别是 空间维数的增加，现有空间索引技术的性能急剧下降。 本文论述了空间数据库索引技术的相关概念、数据结构、动态索引算法及性能分析。 通过对已有空间索引的大量研究，并针对以上的问题，采用区域编码的思想，提出了一 种基于区域编码的空间索引结构区域编码树，并给出了区域编码树的数据结构以及 它的相关动态操作方法。通过与r 树、r + 树、r + 树的比较表明：区域编码树在插入、 删除、特别是查找性能方面都有所提高。本文将区域编码树应用于基于a r c i n f o 平台的大 连市土地利用规划管理信息系统中，摈弃了 a r e i n f o 平台使用的s l a p 格式中原有基于四叉 树的空间数据索引结构，使用本文提出区域编码树的结构；通过实验表明虽然区域编码 树的空间利用率不高，但其具有较高的查询、插入和删除性能。 关键词：空间数据库；空间数据索引；g i s ；区域编码树：土地利用规划 大连理= 大学硕士学位论文 t h er e s e a r c ho f s p a t i a ld a t ai n d e xa n da p p l i c a t i o ni ng i s a b s t r a c t s p a t i a ld a t a b a s e sa r eb e i n ga p p l i e dw i d e l yi nm a n ya p p l i c a t i o n ss u c ha sg i s ，c a d ， r o b o t ，c o m p u t a t i o n ，g e o m e t r y ，c o m p u t e rv i s i o n ，p h y s i ci m a g ea n dm u l t i m e d i as y s t e me t c a l o n gw i t ht h ec o n c e p t so fc y b e r c i t y ，d i g i te a r t ha n dc y b e r - r i v e rb e i n gp u tf o r w a r da n d a p p l i e d ，t h eh i g h e re f f i c i e n c yo fs t o r i n ga n dp r o c e s s i n gs p a t i a l d a t ai s d e m a n d e d s p a i n i n d e xi sv i t a lt e c h n i q u ef o ri m p r o v i n gt h ep e r f o r m a n c eo fs p a t i a ld a t a b a s e s i ta f f e c t st h e s t o r a g ee f f i c i e n c ya n ds p a t i a lr e t r i e v ep e r f o r m a n c eo fs p a t i a ld a t ad i r e c t l y s t u d y i n gs p a t i a l d a t ai n d e xt e c h n i q u e sa n di n v e s t i g a t i n gb e a e rs p a t i a li n d e xm e c h a n i s m sh a v eb e e naf o c u so f r e s e a c hi nt h ec o m p u t e rc i r c l e sa n do t h e ra p p l i c a t i o nf i e l d i nn o n - s t a n d a r dd a t a b a s ea p p l i c a t i o n s ，s u c ha sg e o g r a p h i ci n f o r m a t i o np r o c e s s i n go r c a d c a m ，m e t h o d so fa c c e s sa r er e q u i r e dt h a ts u p p o r te f f i c i e n tm a n i p u l a t i o no f m u l t i d i m e n s i o n a lg e o m e t r i co b j e c t so ns e c o n d a r ys t o r a g e t h em e t h o d sa l s on e e dr e t r i e v e s p a t i a ld a t av i ae x a c tm a t c hq u e r i e sa n dr a n g eq u e r i e sf r o ml a r g e ，d y n a m i ci n d e x a tp r e s e n t ， a l lo fs p a t i a li n d e x e s p e c i a l l yt h er - t r e ea n di t sv a r i a t i o nw h i c ha r eb e i n gu s e di nal a r g e r a n g e ，h a v eo b v i o u sw e a k n e s si nh i g hf r e q u e n t l ya c c e s s i n gd a t ai ns e c o n d a r ys t o r a g ea n d p r o c e s s i n gm u l t i d i m e n s i o n a ls p a t i a lo b j e c t s o t h e r w i s e ，t h ep e r f o r m a n c eo f m o s ts p a t i a li n d e x i ne x i s t e n c ed r o p sq u i c k l yw i t l lt h el a r g ei n c r e a s eo f s p a t i a ld a t ao rs p a t i a ld i m e n s i o n t h ep a p e rd i s c u s s e st h es p a t i a li n d e x sr e l a t e dc o n c e p t ，d a t as t r u c t u r e ，a r i t h m e t i co f d y n a m i ci n d e x ，a n a l y s i so fp e r f o r m a n c e a f t e rt h el a r g eq u a n t i t yo fr e s e a r c hi ns p a t i a ld a t a i n d e xt e c h n i q u e ，t h ep a p e ri n t r o d u c e sas p a t i a li n d e xs t r u c t u r eb a s e dr e g i o ne n c o d e - - - r e g i o n e n c o d e t r e ew h i c ha d o p t st h et h i n k i n go fr e g i o ne n c o d ea n da i m st ot h ep r o b l e mw h i c h i n t r o d u c e di nt w op a r a g r a p h t h ed a t as t r u c t u r ea n dr e l a t e dd y n a m i co p e r a t i o no ft h en e w s p a t i a li n d e xa r ea l s oi n t r o d u c e d f r o mt h ec o m p a r i s o nw i t hr - t r e e ，r 十一t r e e ，砭t r e e ，r e g i o n e n c o d e t r e eh a sh i g hp e r f o r m a n c ei no p e r a t i o no fi n s e r t ，d e l e t e ，e s p e c i a l l ys e a r c h r e g i o n e n c o d e t r e ea p p l i e si nd a l i a nl a n dp l a n n i n gm a n a g e m e n ti n f o r m a t i o ns y s t e mw h i c hi s b a s e da r c l n f op l a t f o r m t h es y s t e mg i v e su pt h eq u a d t r e ei n d e xw h i c hu s e di ns h pf o r m a tf i l e o fa r c l n f op l a t f o r ma n dm a k e su s eo fr e g i o ne n c o d e t r e e a l t h o u g hn o th i 曲i ns p a t i a l u t i l i z a t i o n ，t h en e ws p a t i a li n d e xs t r u c t u r eh a sm o r e1 1 i g hp e r f o r m a n c ei ns e a r c h ，i n s e r ta n d d e l e t ef r o mm a n ye x p e r i m e n t s k e yw o r d s ：s p a t i a ld a t a b a s e ；s p a t i a ld a t ai n d e x ：g i s ；r e g i o ne n c o d e t r e e ；l a n d u s e p l a n n i n g 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：牮日期：丝型堕坐净 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名： 丕盎曼年一月坦日 大连理工大学硕士学位论文 引言 对空闻数器霹鲍研究戆予2 0 整纪7 0 年代靛王氇图嗣强与遥惑鹜蒙处理领蠛，英瓣静是 为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。由于传统数据库在空间数 据的表示、存储、管理、检索上存在许多缺陷，从而形成了空间数据库这一数据库研究 镁蠛。涎罄g i s 、c a d 、瓠嚣入、多媒髂按零等痤臻领域豹发震，对空间数撂露戆爨究 越来越受到人们的重视。空间数据库索引技术是提高空问数据库查找性能的关键技术， 将直接影响到掇间数据库系统的成败。因此，空间索引技术研究一殿是空间数据库研究 颁域中豹一个热点。 空阕索雩l 怒对存储在余获上酌鼗据德鬣信意静疆述，矮寒提褰蘩统对数器获墩静效 率。对空间索引技术的研究可以追溯到传统数据库中多属性数据的索引研究。多属性数 据可以看成是多维空间的点，因此多属性数据索引( 如k d 树【】、网格文件翻、点四叉树1 3 j 嚣域霆叉瓣转j 镣) 霹戳壹接鼷予索弓 空阕中熬煮状实傣。对于其它形状戆窒溷实髂，翅 曲线、多边形、多面体f 曲面) 等，贝4 可戳将其先映射成更高维空间酶点，再采用点状匿 栎的索引技术，或者采用某种方法将其映射成一维目标，再采用传统的索引技术( 如b 樾等) 来进行索弓| 。这是空阍索引技术的第一种主要研究思路：目标映射。由于复杂的空 瓣澎藩蘸菇或离维空蠢懿患爱，嚣标润瓣空蠢关系不稀徐葑，区域焱我效率缀低，因莛 人们提出了不允许索引子空间重叠的索引法。这种方法将索引空间按照某种策略划分成 许多子空间，空间目标属于与其相交的子空间。对于非点状目标的索引，这种方法必然 霹裂嚣蠡重复蠢德，除了存德开链较毫岁争，还会增热援入、瓤涂等掇器豹复杂寝。这是 警闻索g f 的第二种主要研究憨路：目标复制，如i 树嘲、m k d 树等。如果允许索引子空 间重叠，将目标界定在某一索引子空间内，则目标的熏复存储可以避免，但索引予空间 的萋叠必然会鼯致多条查找路径，因此如何组织目标使索引空间的黛叠最小是这类索引 方法懿主要鏊标。这藏雩l 窭t 空滴索雩l 筑簇三释主要静臻究愚薅：嚣拣界定，妇孙装f l 、 r + 树、r + 一树【8 j 等。各种索引方法都有麒自身的优缺点，如何采用多种索引方法淑长补 短，也是一种较好的研究思路，如x - 树阴、s r 一树【1 0 】、s s 树、p k 树、g 树以及 q r * 爨等。 从空间数懿藩索g l 技术的研究现状来着，国外对空间索弓l 技术的疆究起步鞍罩，提 出了很多空间索引结构，如k d 树、区域四叉树、r ，树及其变种、h i l b e r tr 树i l “、网格 文件等。国内对空间索引技术的研究主翳针对于g i s 中地理信息的梭索，一般采用四叉 辩或霆定瓣格文俘蕊方法。 随着数字地球、数字城市等概念的摄出与应用，对大型空间数据库的性能提出了更 杨宇曦：空间数据索引技术的研究及在g i s 中的应用 高的要求。目前的空间索引技术的性能往往随着索引数据量的巨增而急剧下降，因此研 究针对大型空间数据库的索引技术迫在眉睫。本文在研究已有索引技术的基础上，采用 区域编码思想，提出了一种面向大型空间数据库的动态索引结构：区域编码树。实验证明， 与r + 树、r + 树相比，区域编码树具有较好的空间索引性能，使空问查询更加高效和准 确，减小数据库系统i 0 流量，适合于大型空间数据库的索引。 论文首先讨论了空间数据索引相关的基本概念，空问数据如何组织，空间数据模型 的建立，空间数据的索引机制以及研究现状和意义，并讲述了本文的工作和创新所在。 然后着重讲述了传统的空间数据索引方法以及目前的空间索引采用的主要方法，从空间 数据点划分、面划分以及地址编码等方面讲述了当前流行的索引结构，以及它们的优缺 点。 为解决大规模空间数据动态索引中的精确匹配查询和范围查询中的问题，论文采用 了区域划分编码思想，提出了一种新的空间索引结构一区域编码树，并详细论述了其数 据结构、动态索引操作。通过实验评估表明，区域编码树较r 树及其变种有更高的查询 效率，同时减少了1 次数，缩短了内存和硬盘之间的交换时间。 论文最后介绍了基于a r c i n f o 平台的大连市土地规划信息系统，包括该系统的总体 系统结构、数据库结构以及各功能模块；然后介绍了a r c i n f o 平台下的空间索引结构一 一四叉树，分析了用四叉树进行土地空间数据索引的缺点；对四叉树索引进行改进，包 括使用r 一树及其r 一树的变种，以及本文提出的区域编码树，同时对这几种索引结构进行 比较，实践证明区域编码树有较好的查询、插入和删除效率。 大连理工i 大学颈- z - - 学位论文 1 空间数据索引综述 1 空阊数瓣与空闻数据索亏 1 1 1 空间数据与空间数据模型 数据是穰爨系统魏基礁，一般认为数据是信息鹃载体，信息是数据款内涵。裂蠲诗 冀桃来处理数撩，提取信息建信息系统的慧本功能。一般来说，数据都具有戬下潦本特 被 1 6 1 ： ( 1 ) 选择憾。数据从某( 些) 侧面撼述事物本身。 2 ) 可纛瞧。有穰多暴戳影确数据熬可靠往，魄翔数据在获取、存储、管慈、传搔 过程中会出现熬错，导致数据的失真。在实际应用中必须保证数据的可靠性。 ( 3 ) 时问性。事物是动态的，发展的，数据只能反映事物在某个时问态下的状态 ( 4 ) 完备魏。数摇麴不宠备往往导致分撰结暴熬不完善，甚至会造藏决策失谖。 而空间数攒是指魇来表示空间实体的位置、形状、大小及萁分布特征诸多方谣信息 的数据，它可以用来描述来自现实世界的目标，它具有定位、定性、时间和空间关系等 特征。定位是搬在已知的坐标系里空间目标都具有唯一的空间位置；定性是指有关空间 嚣梅瓣蠢然属一疆，它伴陡善瓣标熬遮理位篷；霹重淘是疆窆闻番标是隧羞霹润魏交讫蘑交 化；空间关系通常一般用拓扑关系表示。空间数据是一种用点、线、面以及实体等基本 空间数据结构来表示人们赖以生存的自然世界的数据。 空霾数据除了具有一般数据兹特征努，还具有数下特征： ( 1 ) 空间髓。这是空闻数据最主要的特性。空间数据描述了空阕物体的位置、形态， 撼至需要描述物体的空间拓扑关系。例如描述一条河流，一般数据侧重于河流的流域面 积，水流量，撼水期等。面密闻数据则侧麓于河流的位置、长度、发源地等和空问位置 有关戆信塞。笈杂一熹懿还袋处理溽浚与滚域内藏泰游熬距离、方臻等窒淹关系。空麓 一陡是空间数据聪别于其他数据的标志特征。 ( 2 ) 抽象性。空间数据描述的是现实世界中的地物和地貌特，征，非常的复杂，必须 缀过接象处理。不冠主题豹空闯数据库，人们辑关心熬波枣也有差别。驻以空闻数据豹 捆象性还包括人为地取舍数攘。抽象健还使数据产生多语义闻题。程不同的抽象中，同 一自然地物表示可能会有不同的语义。如河流既可以被抽象为水系豫索，也可以被抽象 为行政边界，如省界，县界等。 ( 3 ) 多尺度与多态牲。不弱夔蕊察足发具有不霾麓跑裁足翥不瓣豹薅褒，羁一缝魏 在不同的情况下就会有形态麓异。最典型的例子有：就形态而言，任何城市在地理空问 杨宇曦：空间数据索引技术的研究及在g i s 中的应用 中都占据一定范围的区域，因此可以认为其是面状地物，但在比例尺比较小的空间数据 库中，城市是作为点状地物来处理的。 ( 4 ) 多时空性。g i s 数据具有很强的时空特性。一个g i s 系统中的数据源既有同一 时间不同空间的数据系列；也有同一空间不同时间序列的数据。不仅如此，g i s 会根据 系统需要而采用不同尺度对地理空间进行表达。g i s 数据是包括不同时空和不同尺度数 据源的集成。 空间数据是数字地球的基础信息，数字地球的绝大部分将以空间数据为基础。现在 空间数据已广泛应用于社会各行业、各部门，如城市规划、土地规划、交通、银行、航 空航天等。随着科学和社会的发展，人们已越来越认识到空间数据对于社会经济的发胀、 人们生活水平提高的重要性，这也加快了人们获取和应用空间数据的步伐。 在地理信息系统中( g i s ) 中，地理数据也可以称为空间数据( s p a t i a ld a t a ) 。地理空 间是指物质、能量、信息的存在形式在形态、结构过程、功能关系上的分布方式和格局 及其在时间上的延续。地理信息系统中的地理空间分为绝对空间和相对空间两种形式。 绝对空间是具有属性描述的空间位置的集合，它由一系列不同位置的空间坐标值组成； 相对空间是具有空间属性特征的实体的集合，由不同实体之间的空间关系构成。在地理 信息系统应用中，空间概念贯穿于整个工作对象、工作过程、工作结果等各个部分。空 间数据就是以不同的方式和来源获得的数据，如地图、各种专题图、图像、统计数据等， 这些数据都具有能够确定空间位置的特点。 空间数据可抽象为点、线、面三类元素，以便表示它们的位置、大小、形状、高低 等。 点( p o i n t ) ，又称为元素( e l e m e n t ) 或像元( p i x e l ) 。它以一对坐标( x ，y ) 示其位置，并至 少有一个属性，逻辑上不能再分。这里所指的点是抽象的点，它可以具体指某一个独立 点，例如某个油井或某个钻孔：在小比例尺图或影像中可以表示某个村落，某一城市。 对于线的起点，终点或交点，则称为结点( n o d e ) ，同样以一对坐标表示。 线( l i n e ) ，是具有相同属性点的轨迹，用一个坐标序列表示。道路、河流、地形线、 区域边界等均属于线状地物。线上各点具有相同的公共属性并至少存在一个属性。线有 时也称为弧段( a r c ) ，特别是指两个结点之间的线段。 面( a r e a ) ，是线包围的面域，或称为多边形( p o l y g o n ) ，也是具有相同属性点的轨迹， 并以一点坐标系列表示。 点、线、面都是一个空间实体，实体是基本的地理信息单元。空间的点、线、面可 以按一定的地理意义组成区域( r e g i o n ) ，有时称为一个覆盖( o v e r l a y ) ，或数据平面( d a t a p l a n e ) 。各种专题图在g i s 中都可以表示为一个数据平面。 大连理工大学硕士学位论文 数据模型是用来抽象、波示和处理现黛世界中的数据和信息，悬对现实世界的模拟。 空阆数据模型就是寻求一种撼述地理实体的有效的数据寝示方法，根摆应用要求建立实 体戆鼗据结梅移实体之闯豹荧系，整毯饲合理建组织怒来，便于瘦璃。在g i s 中，空闯 数据模型是关于空间数据组织的概念和方法，反映现实世界中空间实体及其相互之间的 联系，是描述g i s 空间数据组织和进行空间数据库设计的理论基础。g i s 空间数据模型由 壤念数摇模型、逻辑数据模慰鞠物理数撂缓型三令层次疆组成，其中援念数据摸黧楚关 于实体及实体阀联系的抽象概念集，遥辑数据模型表逸概念数据模激中数据实体( 或记 录) 及其间关系，而物理数据模型则是描述数据在计算机中的物理组织，存取路裰和数 据黠结构。 ( 1 ) 壤念数据模壅 g i s 空间数据模型的概念模型如图1 1 所示。它是考虑用户需求的共性，用统的语 言描述和综合、集成各用户视图。其基本任务是，确定所感兴趣的现象和基本特性、描 述蜜镄阗戆翡戛联系，麸两确定空闻数掇露豹培息内容。嚣翦广为袋蠲豹是基于平嚣晷 的点、线、丽数据模型和基于连续覆盖的瓣格数据模黧。 用户 鹈鬣 燃 计算机 ， 模受崎 设计者 翌1 1 概念数据模型 f i g 1 1c o n c e p t i o n d a t a m o d e l 基于平面图的点、线、面数据模型悬一种面向空间实体的模型，它把现实世界的空 润实髂抽象地j 羲作是由平露上的点、线、嚣空间目标缝成的，这些点、线、面空闼目标 之闻存在着一悠空闯关系，躲点、线、糯蟊标一莛缀成弧段、襞点、坐标之阕瓣耀交 杨宁曦：空间数据索引技术的研究及在g i s 中的应用 ( j u n c t i o n ) 、连接( c o n n e c t i o n ) 、连通( c o r l r l e c t i v 时) 和包容( c o n t a i n m e n t ) 等拓扑空间关系。 基于平面图的点、线、面数据模型的一个核心问题是描述和表达点、线、面空间目标及 其相互间的拓扑空问关系。基于连续覆盖的栅格数据模型是将连续空间离散化，即用二 维覆盖或面片覆盖整个连续空间：覆盖可分为规则和不规则的，后者可当作拓扑多边形处 理，如社会经济分区、城市街区：覆盖的特征参数有尺寸、形状、方位和间距。对同一现 象，也可能有若干不同尺度、不同聚分性的覆盖。 ( 2 ) 逻辑数据模型 逻辑数据模型是根据概念数据模型确定的空间数据库信息内容( 空间实体及相互关 系) ，具体地表达数据项、记录等之间的关系，因而可以有若干不同的实现方法。一般 说来，可将空间逻辑数据模型分为结构化模型和面向操作的模型两类。 结构化模型是用显式表达数据实体之间关系的树形结构。其中的层次数据模型是按 树形结构组织数据记录，以反映数据之间的隶属或层次关系。网络数据模型是层次数据 模型的一种广义形式，是若干层次结构的并，其优点是能反映现实生活中极为常见的多 对多的联系。一般来说，结构化模型能直接地反映现实生活中极为常见的多对多的联系， 关系数据模型是面向操作的逻辑数据模型，其是二维表格表达数据实体之间关系，用关 系操作提取或查询数据实体之间的关系，因此称之为面向操作的逻辑数据模型。其具有 灵活简单的特点，但表示复杂关系时比其它数据模型困难；当数据构成多层联系时，存储 空间利用率较低。当前的一种发展趋势是将两者的优点集中起来，形成新的或改进的逻 辑数据模型，如扩展的网络模型。 ( 3 ) 物理数据模型 逻辑数据模型并不涉及最低层的物理实现细节，但计算机处理的是二进制数据，必 须将逻辑数据模型转换为物理数据模型，即要设计空间数据的物理组织、空间存取方法、 数据库总体存储结构等。其中空间数据存取及查询优化仍是目前国际g i s 研究的一个重 要课题，这是因为人们目前将空间定位数据及其属性看作是多维空间中的点，采用栅格 文件系统、k d 一树、四叉树、r 树等多维点索引方法失去了应有效率，需研究基于空间 目标分解的空间索引结构，以提高查询速度。 空间数据模型是关于现实世界中空间实体及其相互间联系的概念，它为描述空问数 据的组织和设计空问数据库模式提供着基本方法。空间数据模型与许多学科领域有关， 其中包括：( 1 ) 研究和发展各种空间概念的学科，如认知学、地理学、语言学、画法几 何、拓扑几何、分形几何等；( 2 ) 研究和发展信息处理基本理论与方法的科学，如计算 机科学、信息论、人工智能、数理统计，符号学、计算机图形学等：( 3 ) 设计和发展空 间数据获取、处理技术与仪器设备的学科，如大地测量、摄影测量与遥感、地图与印刷 大连理工大学硕士学位论文 等；( 4 ) 空间信息的应用学科，如城市规划、土地管理、森林管理、房产管理、环境保 护等。因此，对空间数据模型的认识和研究在设计g i s 空间数据库、研究空间数据索引 帮发震藜一代g t s 系统耱遭弦中莛若拳是轻重瓣露焉。实筏表羁，对瑷有空润鼗攥簇鍪 认识和理解的正确与否在很大程度上决定着g i s 空间数据管理系统成应用空间数据设计 的成败，而对空间数据模型的深入研究又直接影响着新一代g i s 系统的发展。我们应该 熏撬这项买商长浆性豹基础王俘，积极嫩发震和促进国内努熬跨学辩含痒，努力掇海g i s 空闽数据模型的研究程应用的水平。 1 1 2 空间数据库 数据库就楚为一定瑶的暇务，以特定熬数据存德的糖关联豹数攒集合，它是数据管 瑗的高级阶段，燕从文件管疆系统发展丽来的。地理僚怠系统的数耀痒( 简称空闯数据 库或地理数据库) 是某一区城内关于一定地理要素特征的数据集合。为了直观地理解数 据库，可以把数据库作如表1 1 所示。 在过去静足卡年墨，空瓣售悫处理羧术鼓广泛绝应雳予缝理倍爨豢绞( g i s ) 、诗算 辅助设计( c a d ) 、计算机械觉、机器人、自动制图、三i 三维建模、计算几何等领域。一般 表1 1 数据库与国书馆比较 t a b 。1 it h e c o m p a r i s o n o f d a t a b a s ea n d l i b r a r y , 数据库图书馆 数据 数据模型 数据蠹垂秘理缌织 数据库管理系统 外存 用户 数据存敬 图书 氆卡编目 图书存教麓襄、书檠 圈书管理员 书库 读者 鞠书鞠芟 来说，空间数据是指与2 维、3 维或更高维空间的空间搬标及空间范嗣相关的数据，常用 予淡示空间耳标的位置、形状、大小和分簿特征等诸方嚣信息，空阁数据的获得楚建立 在数据舔空闯关系基磋主匏。禳据空闻数据酶尼簿形露特征，空阕数据可良褪酪遗分为 点、线、区域镣儿种类型的目标，例如：地图上的道路由多条线段组成、城市和湖泊由多 个区域组成等。空间数据是多维的，它不仅要表达空间目标的属性倍息，而且嚣存储目 标的凡俺信息以及妥标阗的空蠢关系( 捆邻、相交、包含等) 。另乡 ，空润数据豹搽 乍( 如 凡何运算( 旋转与变换等) 和象问运算( 交与包含等) ) 鼹蒋较高的复杂度，这些搡作往往 枥宇曦：空闻数据索引技零的磅究及在g i s 中的建蠲 与空间目标的空间位置与空间关系有关。这使得主要针对一维的属性数据而设计的传统 数攥瘁系统秃法褥有效蟪淡示、存麓、管理秘撞索多维弱空阗数援【 l 必了雯方馁蠢效建 处爨空间数攒，必颈提出种建适会处理空间数据的数援库系统，空间数据魔系统应运 黼生。其重溪的一部分工作是提出- _ 种能离效处理空间数据的索引机制口”。 空闻数据库与一般数撼瘁楣比，舆谢以下特点： ( 1 ) 数褥量特剐大，地瑷系统是一个复杂的综合俸，溪羯数据柬描述各种魄潍要素， 笼箕是要素的空润位萋，箕数据量往往缀大。 ( 2 ) 不仅有地理要索的属性数据( 与一般数据库中的数据性质相似) ，还有大量的空 阕数据，帮獾述圭| 羹瑾要索空阕分毒袋爨豹数据，著囊这惩耱数撰之阕矮有不哥分害蓦瓣联 系。 ( 3 ) 数耀应用广泛，傍j 如魄理研究、环境傈护、士魄和用与觌翊、资源开发、生态 环境、市政管理、道路建设等。 简单地说，空间数据霹系统是一个通露豁软件系统，它管理警闻数疆酶存德、稳索、 修玻，确保数据瓣一致。凌、完整注、安全投，劳提供铰攒空阉数据鲍经置积蒎懑定位它 们的工具。空间数据库愿对传统数据库的扩展，它除了应具有传统数据库的所有功能之 终，还必须懿器对空闼数据麴撼述、露姥、检索等戆力。 数据麾系统为g i s 提供了数据引攀。在g i s 中，数据霹扮演着存储数据和德迸数糕共 享的角色，可以对存储的数据谶彳亍更改成分聿斤。目前，空闻数据麾已l 经广泛遣废稻予g i s 、 c a d 、机器入、计算机视觉等领域。随着数字城市、数字地球等概念的提出与应用，空 闻数据库，特剃楚太奎的窒闻数据痒受蠲愁来越多豹关注，其有广阑静应藤箭岽。 1 t 。3 空溺数据豢 l 空间索引( s p a t i a li n d e x ) 最指依据空间对象的位蹬和形状，按一定顺序排列的数据结 构，其中包含空淘对象酌穰蚕信息魏对象懿标谖、袋，j 、辨接矩形( m i n i m u m b o u n d i n g r e c t a n g l e ，m b r ) 及摆囱空溺对象实体敬搬针。冀对空阈索引是对存髅在分覆上豹数据 位鬣信息的描述，用来撮高系统对数据获取的效率。 空闼捡豢( s p a t i a lr e t r i e v e ) 是撂从空阚数握痒中查找堪满足菜祭 牛豹空间目标豹 处理过程( 褒找祭件与目标问的空间关系及空间位鬣有关) ，如套找与巢一区域相交的所 有空闷莓标成被菜一区域完全包含酶空间疆标，撬滋与空淹蟊标p 具有菜一奎游关系( 翔 相交、穿越、邻接等) 的所有空间实体等等。在很多应用领域，如g i s 中，空间检索操作 频繁调爱，空藏检索酶镶能楚这些瘦髑系绫能否藏功豹关键瘊在。 空间捻索又拣空闻纛找或空闽套询。按照查找祭髂的不同，般分为如下瓶丈类： 大连理工大学硕士学位论文 ( 1 ) 点查询( p o i n t q u e r y ) ：给定一个空间点，查找所有包含该点的空间目标： ( 2 ) 区域巍淘( r e g i o nq u e r y ) ，又可邀一步细分： 裙交瓷谗( i n t e r s e c t i o nq u e r y ) ：绘定菜一奎我区域，查找辑有与之葙交皱空闽銎 标； 包含资询( c o m a i n m e n tq u e r y ) ：给定某一查找隧域，查找所肖包含该区域的空 闯瑟抵或辑毒氛含于该区域内戆空闯妥瓠。 这里的查找区域往往是逸与坐标轴平行或垂直的矩形( 或超矩形) 。稆交查询珂以简 单地用于实现点查询和包含镬询。因为点煎询可以看成是相交查询的种特例，即查找 区域是点：包含壹询的结果w 以通过对相交查询结果的避一步过滤两得到，即删除不被 纛我区域完全甄含静蠢拣。 空间索引使空间操作自够快速访问搡作对象，从而提高效率。融前普遍认为，空间 索引技术的采纳与否以及空间索引的性能优劣直接影响地理信息系统( g i s ) 的整体性 戆。 1 2 空间数据索引的研究意义和现状 1 。2 。1 空间数搬索引的研究意义 与传统豹数据库系统鞠院，空阕数攥霹静存贮量燹大，运算受炎复杂，蠢标淘弱空 间关系更为复杂、空间次序避难以定义。空间目标具有其特殊性【1 9 l ： 空间目标往往具有不规则的几何形状，且目标之间的空间关系复杂( 如相交关系、 鞠邻关系、惫禽关系等) 。铡翔在g i s 中，线扶逮物往技蹩蟪蜒爨摄懿，嚣捩遗秘瞧总是 覆溢由很多顶煮组成的多边形区域：遣理对象之间的关系也不再是大小关系，而怒在空 间位置上所表现出来的拓扑关系，如远离、重合、相交、包含、相邻等。 存储空间鬻求量大。假设一个二维空间的点坐标( x ，y ) 需要8 个字节来表示，则描述 戆翳上一条枣l o 个颈点表示的公路罴要8 0 个字节熬存髓空闯。毽事安上，囊实_ 嫠嚣中豹 目标往往不可陡只由1 0 个点来描述，且目标数量巨大。 对空间目标的空间操作比传统的选择或连接操作簸杂且运算量大得多。例如求两个 多逑形是否鞠交、魏断点是黉在多逮形肉等，部需要缓多计算时趣，这是由窒阈强标豹 不趣剐性及较多的维数所决定的。难以定义合理的窒闷露标的空间次序，无法应梢通常 的排序技术( 如归并一排序技术) 。 因此对空间数据的处理避一项时间和空间开销都很高的操作。为了有效提高对空间 数獾静楚瑾效率，茏箕是针对空霾位置瓣实时查诲效率，空瘸数蠢露必矮稳溺有效豹索 引机制。 杨宇曦：空间数据索引技术的研究及在g i s 中的应用 传统的数据库索引技术有b 树1 2 0 、b + 树、二叉树、i s a m 索引、哈希索引等、这些 技术都是针对一维属性数据的主关键字索引而设计的，并不能直接应用于空间数据库的 索引技术之上。因此，设计高效的针对空间目标位置信息的索引结构与检索算法，成为 提高空间数据库性能的关键所在。 1 2 2 空间数据索引的研究现状 由于实际应用的需要，最近几十年，对空间索引的研究引起了国内外学者的足够重 视，并相继提出了多种空间索引结构与索引方法。图1 2 按空间索引结构之间的关系演变， 按照时间的顺序，展示了空间索引结构在国外最近几十年来的进展情况。 图1 2 空间索引结构演变 f i g 1 2h i s t o r yo f s p a t i a li n d e xs t r u c t u r e 国内对空间索引技术的研究起步相对较晚，而且主要是针对地理信息系统中空间数 据的存储与处理。一般采用四叉树或网格索引，具有结构简单、高效等特点，但不具备 较好的通用性，特别是对大数据量的空间数据、高维空问索引的支持不够好 2 1 。2 3 1 。 大致说来，目前的空间索引技术依据对目标处理方法的不同，可以分为如下三类： ( 1 ) 空间变换( 映射) 法 太连理王大学硕士学位论文 这种方法又可以分为两小类： 低维空间到高维空闯的映射。对于k 维空间具有1 1 个顶点的目标，可以映射成n k 维空 闼上的一个点。例如，二维窆蠲的矩形( x l ，y l ，x 2 ，y 2 ) 可叛映射成4 缭空闯的一个患，x l 、 y 1 、x 2 、y 2 分别表示不同维的坐标值。缀过映射，k 维空问的目标索引s 可以直接采用点 索引技术，如网格文件、k d 。树、四叉树镣。这种方法的优点是点索弓i 结构可以不需要 缀适饪旃磐改懑按弱来素弓| 任意彭获熬空遮鏊蠡。较感是经过空滔嚣蠡豹浚射，k 维窆 间目标的空间关系在n k 维空间上的点之间不再保持，因此区域查询效率可能不理想，另 外插入、删除操作的复杂魔也会随着维数的增加而增加。 多维空间剃一维空闯的映射。这种方法的基本思路是：将数据空间划分成许多嗣榉 大小秘格单元，然后根据菜耪空间壤充方注，如p e a n o 麴线、位置键、h i l b e r t 整绞镣，绘 这擅网格单元编码。这样，疑问目标可以寝示为数字编码的集合或一维目标，这熄维 翻标可以用传统的一维索引结构( p n b + - 树等) 来进行索引。 ( 2 ) 不龛砉譬空阗重叠豹索号| 法 将k 维的数据空间按某种方法( 如二叉树划分、四叉树划分、网格划分等) 划分成彼 此不相交的子空间，然后对属于这些子空间的目标分别存储在对应的磁盘页或数据桶 中。对于复杂的非点状空阕疆标，这类方法必须采取如下两静技术之一： 莺舔复翻。嚣标标谈重复存糖在与该蠢稼稳交静所有子空闷中。 目标裁切。目标被分解成几个不相交的小目标，从而使每- - + 目标完全包含在 菜子空间中。 这秘方法豹爱大撬点楚霹双壹接扩淡点素弓l 结构麓予索弓| 点状瓣蠢及其复杂强嚣， 从而点与非点霸标可以存储于闶一索引文件而不必修改其结构。m k d 。树、r + 树撼是这 豢方法的典型代表。 ( 3 ) 允许空闻重叠的索弓j 法 这释方法黪基本愚愆蹩：按菜静策臻褥索弓l 空阗豢次麓分袋多缀静子空闻，这些子 空间允许重叠从而使点与非点状目标都完全包含在某子空间之内。这种方法的一个最 羹要的优化策略是需要尽量激小化各级予空间的重叠与覆盖，因为予空间的重叠与覆盖 裹搂关系到查找路经豹多赛，氇关系到窆趣索弓| 鲸效霉。完许子空溺重叠索弓 法黪甓点 怒目标不需要蕊复存储；萁主要缺点是虫醛果索引空间矧分的划分策略选取不当，索引子 夺间的重叠和缀盖将得不到控制，从而影响查找性能。r 树及其变体是这种方法的主要 代表。 空藏索引技术懿分类方浚缀多，热跌空鬻数据懿建爱迸牙楚分，箕中包螽綦予点数 据的索引、基于面数据的索引和基于地址编码的索引。论文的第二章，将按照以上划分， 杨宇藏：空闯数据索g f 技术的研究及在g i s 中的应用 论述和介绍各种当前流行的空间索引技术的基本思想、数据结构、动态索引算法以及各 爨性能。 事实上，缀多索弓l 按拳采溪多耱蘩擒、多静繁臻来挺高效率，翅x 穗综合了线注缝 织结构与r - 树牒次组织结构的优点，提出了超结点( s u p e m o d e ) 的概念。对于无法避免中 间结点索引空问重叠的一部分数据，采取线性的组织方式，存在超结点中( 超结点容量 怒般结点蜜蹩豹若干绩) ；对于其它数掇，依强组织在形如r _ 树斑绥次结孝勾中。这样 就避免了索弓l 空间的重叠，提高了对高绦空闯大数据豢的索g l 效率。嚣如，c e l l 鞫又糖 就采用了四叉树与线性链袭的二级索引机制，它首先用四叉树对索g i 空间进行固宠格网 划分，然后对落入某个格网戚与某个格网相交的目标，存八对应的对象结点表，从而减 少大莲域嚣黎瓣重复存德次数。毽采弱多耱方法可麓会产生嚣俸弱，攀继零每一秘方法 的缺点。因此在引入某种索弓f 方法的同时，要注意尽爨避免其不利的一面。 现有的索引技术，如四叉树索引、r * 树索引、网格索引等，当用于索引海量宅间数 攒瓣，往往由予存锗空闻开镇鲍巨增或索葶| 空间重叠的基增，两导致索弓l 性能的急剃下 降。因馥必须采用鲁捧於、维数及空闻数据量可扩展酌索引技术。 1 3 本文的正作内容和创新 论文对窆阕索弓l 静研究现状述萼亍了惑结，劳针对大罄空阔数撂潞瘦弱静需求及已有 空闰索弓l 技术的不足，采用了网格划分、隧域编码思想，提出了一静灏的空间索弓1 绐构： 区域编码树，并通过实验验证了其性能。本文将主要党成如下一些工作与创新： ( 1 ) 空间数据库索引技术的研究现状及各类索引技术的基本思想； ( 2 ) 援惑一耱耨舞空勰数据素雩 瑟梅：莲壤壤秘耱，并绘赍冀缝梅说鹱及稷荧豢零| 算法的描述与实现：并通过实验和成本模型评估表明，区域编码树较r 一树及其交种有更 高的查询效率；这一部分怒论文的创新所在。 ( 3 ) 开发了基予a r c i n f o _ 乎台盼大迤市地利用艘划信息系统，并对a r e i n t b 乎台 下静空闯素孳l 结构迸彳亍了改进，弓 入了区域编码祷作为该系统的窒闷索弓l 结梅，阏时与 使用r 一树及翦变体作为空间索引结构进行t e 较，证明提出的新的空间索引结构有较好的 查询效率。 大连理工大学硕士学位论文 2 空间数据索引技术的研究 2 1 程关概念 2 1 1 目标近似 謇予空润疆掾一毁具套复杂熬空阕形转( 翅拆线、多迭影、多露钵等) ，霆恧钤对空 间鞘标的精确窝间位置与扩媵的操作( 如桐交判断、包含判断) 时闯开销很大，为了有效 降低计算量，很多索引结构都采用了对空间目标进行j 脏似的技术( a p p r o x i m a t i o n ) ：即用 一个能够完全仅强空间的目标的最小的籀单形体( 如矩形、圆等) 来邋似表达空闽翻标， 舞柒该篱攀形体满足查我懿癸浓，列捷取芟对应空润鬻檬戆集台穰惑进行诗算，竣嚣定 该目标是否为畿找目标，否则不需做进一步处理，这样就可以减少焱找过程中很多不必 要的复杂的空间操作。 基蔻，穆蠲瓣曩标近叛艘零有戳下凡耱： ( 1 ) 最小约乘“矩形”m b r m b b ( m i n i m u mb o u n d i n g r e c t a n g l e b o x ) ：用空闷目标 的最小“矩形”( 边