GIS空间索引方法述评

1、地理与地理信息科学Geography and Geo Information Science第20卷第4期2004年7月Vol. 20 No. 4July 2004GIS阎超德，赵学胜中国矿业大学测绘系.北京100083）:地理信息系统的主要任务之一是有效地检索空间数据及快速响应不同用户的在线査询°传统的索引方法只 能解决一维査询问题.无法满足地理信息索统的要求。该文介绍了 GIS中具有代表性的三玺空间索引方法.即基_ 千占只城创分的索引方法、菓于面区域划分的索引方法和空间实体的地址编码索引方法.并且进行了分析对比。:空间索引：地理信息系统：四叉树;R树:地址编码:P2O8:A: 1

2、672 - 0504（2004）04 - 0023 - 04© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 地理与地理信息科学Geography and Geo Information Science第20卷第4期2004年7月Vol. 20 No. 4July 2004© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 地理与地理信息科学G

3、eography and Geo Information Science第20卷第4期2004年7月Vol. 20 No. 4July 20041 K- D(a)(b)Fig. 1 K D FIree( a) and its plane part it km( b)地理信息系统（GIS）的主要任务之一是有 效地检索空I'可数据及快速响应不同用户的在线 査询。空间索引是通过对存储在介质上的空间数据 的描述建立空间数据的逻辑记录与物理记录之间 的对应关系最终目的是提高系统对空间数据获 取的效率。传统的索引方法只能解决一维査询问题无法 胜任G1S中海量空间数据的査询。传统树表冬引方 法冷中，

4、如二叉树、B 树、ISAM （ IndexeQ Sequential Access Method）等主要针对字符、数字等数据对象. 数据类型是在一个良序集之中.即集合中任意给出 两个元素都可以确定其关系（只可能是大于、小于、 等于这三种的其一）；若对多个字段进行索引，必须 指定各个字段的优先级形成一个组合字段但是 GIS中空间数据具有多维性在任何方冋上竺資 在优先级无法用于搜索具有多维特征的空间对象c 融列趟运是假定数据项中关键字与存储位置（存 储桶号）存在哈希函数（Hashing）对应关系，这在 多维空间中也是无法控制的。另外GIS中存储了 海量的空间数据一般数据库所使用的索引机制并 不适合

5、空间对象的査询要管理和检索这些海量空 间数据需要采用高效的多维空间索引技术0空间索引的基互方法就是将整个空輕企成丕I的搜索区域以一定的顺序在这些区域中査找空间实体。按搜索区域划分方法不同空间索引可 分为三类即基于点区域划分的索引方法、基于面区 域划分的索引方法和基于三维体区域划分的索引方 法山。本文研究的对象是前面两种类型以及空间实 体地址编码索引方法首先综述GIS中具有代表性 的空间索引技术然后进行分析对比0常见的基于点空理纱累引结构有上£ 树m、B树巴Kr DiB树点 四叉树（氐ini Quadtree）%。下面简要介绍其方法并进行对比分析。 （1）止丄 树（k维搜索二叉树）是把

6、二叉栉推广 到多淮数据的一种主存数据结构它是二维空 间中的二叉树。在每一个内部结点中用一个k1 维的超平面（如二维空间中的线）将结点所表示的k 维空间分成两部分.这些超平面在k个可能的方向 上交替出现.而且在每一个超平面中至少包括一个 点数据。在二维坐标下根据插入点的纵横坐标将 空间进行交叉分裂，把空间数据递归地划分为一个KD树是一种竝索引结构.它适合于索引空 间点目标。文献8介绍了一种应用KD树建立道 路节点索引的方法。对复杂的空间目标（如折线、多 边形等）的索引必须采用近似方法和空间映射技术. 如对干面实体.可以采用它们的中心点来近似代替。K- D树是一个非平衡树不同数据插入顺序会产 生不

7、同结构的K- D树。在KD树中数据分散出现 在树的任何地方而不是仅出现在叶结点上。KD树© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 地理与地理信息科学Geography and Geo Information Science第20卷第4期2004年7月Vol. 20 No. 4July 2004© 1994-2008 China Academic Journal Electronic Publishing House. All rights reser

8、ved 地理与地理信息科学Geography and Geo Information Science第20卷第4期2004年7月Vol. 20 No. 4July 20042004 - 05- 11 ;:2004-06- 15国家杰出書年料半基金4002501）间超德（1965）男.別教授博士研究生研究方向为GIS.LBS等.© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第24页地理与地理信息科学第20卷虽然存储需求较低(指针较少)却增加了树的深度. 不利于海量数

9、据存储树的更新也较困难01994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第#页地理与地理信息科学第20卷1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第#页地理与地理信息科学第20卷(2)匕一种平衡的多路査找树，其原理就2. 11994-2008 China Academic Journal Electronic Publishing House. All rig

10、hts reserved 第#页地理与地理信息科学第20卷是把数据划分为层次索引侮个节点占一甘储块C区域四叉树(Region - Based Quadtree)是以区域1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第#页地理与地理信息科学第20卷一颗m阶的B树或为空树或为必须满足五个特 目标为循环分解对象的四叉树,分解过程既可以按1994-2008 China Academic Journal Electronic Publishing House. All rights re

11、served 第#页地理与地理信息科学第20卷性的m叉树.B树五个特征见文献1 、2。B 树 索引是一种文本索引对于以文件形式组织的空间数 据通过建立B树索引结构实现空间数据的快速査 询。B-树索引结构广泛应用干点、线、面及体对象的 数据文件中.B -树还是其它树形结构的基础。KD-B树是KD树与B树的结合.兼有 两者的特性是B树向多维空间发展的一种形式。它昂一种完全平衡树以B树方式进行插入和删除o K- DB树的优点是可以对多维空间中的点对象进 行动态索引.査找速度快。缺点是不直接支持占据 一定空间范围的空间对象如二维空间中的线与面: 另外删除算法效率低.导致空间浪费|9-，uo为点四叉树和

12、区域里翌。点四叉树是以点目 标为依据.以当前输入点的位置为中心对空间进行 水平和垂直的循环划分每次平面被划分为四个部 照区域边界也可以按照区域内部对二维空间进行 划分內。在存储对象的空间区域时使用定长或不 定长的区域进行分割形成对分解区域的一个连续 铺盖。在形成的铺盖上根据分解的顺序形成代表 其顺序的编码规则.如码。在进行区域划分 的过程中根据研究的尺度可以定义区域划分的分 辨率。区域四叉树的优点是空间划分无重叠:通过规则 编码(如Morton码)可以快速找到区域所在的行列还 可以根据空间对象的稠密来确定分辨率:通过区域四 叉树可以判断筒单的空间实体关系。缺点是树的深 度相差很大空间利用率较低

13、:随着分辨率的提高层 次会变深结构更复杂数据维护也更为困难。四叉树被广泛应用于栅格数据的管理中与其 它索引配合，会产生更高禹效率如基干固总网格划 分的Cellqtree. SuperMap的线性可排序Pj冬磐g 索引ToRACLE公司的Spatialwarc同时采用R 树与四叉树两类索引方法。1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第#页地理与地理信息科学第20卷分分别对应着以输入点为中心的四个象限即东北R-1994-2008 China Academic Journal

14、 Electronic Publishing House. All rights reserved 第#页地理与地理信息科学第20卷事先需要知道点集的空间分布。随着应用中点的插 入与删除点四叉树的平衡将会被破坏，因此一定时 间之后需要对索引进行彻底维护重新生成新树。(aj(b)2 R (a)(b)Fig. 2 Plane p»rtitk>n( aland structure in R lree( b)(NE)、西北(NW)、东南(SE)、西南(SW)象限。点的 输入次序决定了树的层次结构。点四叉树是一种优秀的并行数据结构创建、査 找、插入和删除等操作均比较简单适用于动态管理 空

15、间点目标。点四叉树的缺点是树结构与点的插入 顺序密切相关当点目标分布不均匀时，点四叉树中 子树深度相差较大形成较多空节点造成树的利用 率降低。为了提高点四叉树的存储效率提高数 据査找速度有必要找出一种四叉树的近似平衡方 法。笔者曾经做过这方面的试验核心思想是循环插 入象限中点集的近似中心点直到所有点插入为止。 如果点目标在空间上分布均匀(如測量控制点、城区 移动通讯基站等)将最靠近几何中心的目标点视为 象限的近似中心;如果点目标在空间上分布不均匀 (如地名、电力设备、道路节点、公交站点等)则采用象 限中点集的近似质心将点集分为数目近似相等的四 个象限。该方法可以较大程度地减少树的深度但是2.2

16、.1 R树的数据结构R 树是空间数据索引 结构中最重要的一种层次结构目前已成为许多空 间数据索引方法的基础。其构建思想是以最小边界 矩形简称MBR)递归地对数据集空间按照“面积” 规则进行划分(叩。R树中非叶子结点代表一个划 分的空间区域即一个矩形空间区域：R树中的叶 子结点包含的矩形区域对应空间对象的MBRo构 造矩形空间的原则是：1)矩形之间尽可能少重叠；2) 矩形尽可能包含更多的空间对象：3)矩形可以嵌套 即矩形中可以包括更小的矩形山"。R树的平面划 分与数据结构如图2所示。进行空间检索时首先判 断哪些矩形区域与检索窗口相交再进一步判断落在 检索窗口内的矩形区域中有哪些被检索的

17、对象。 归面|00| lutz怕胃口1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第4期阎超德竽：GIS空间索引方法述评第25页2.2.2 R树索引结构存在的问题 R树具有很 强的灵活性与可调节性，建树过程中无需预知整个 空间对象所在的空间范围.同时它具有较高的执行 效率，被公认为是较好的空间索引结构，已经得到广 泛应用。但是R树也存在许多问题I）, 可以归纳为两方面：1）由于空间对象千姿百态其索 引空间经常重叠.且其重叠的程度随着数据量或空 间维数的増加而剧増。索引空间的重叠

18、必然造成树 的深度及存储空间的増加从而导致遍历时间増加 査询效率下降；2）在动态构建R-树时还会产生大 量阮空间”（不包含空间目标的索引空间）造成存 储空间的浪费产生无效的遍历。2.2.3 R-针对R树中索引空间的重叠许多学者提出了改进结构，统称为变种R树。 其中主要有R树,61.R*-树g、QR树3以及 CP-树（基于凸多边形的空间索引在R+ 树中不允许索引空间重叠但空间目标需要重复存 储.即当一个空间对象同时位于多个索引空间时空 间对象要分别存储在各自的空间中不仅会导致存 储空间浪费与树深度的增加还导致插入、删除算法 的复杂化。2）在R -算法中，构造算法不仅考虑了 索引空间的“面积” 而

19、且还考虑了索引空间的重叠o 该法对结点的分裂算法进行了改进.并采用“强制重 新插入”的方法使树的结构得到优化。但R 算法 仍然不能有效地降低空间的重叠程度尤其是在数 据量较大、空间维数増加时表现得更为明显W 3） QR-树利用四叉树将空间划分成一些子空间，在各 子空间内使用许多R树索引，从而改良索引空间 的重叠。QR-树结合了四叉树与R树的优势是 二者的综合应用。实验证明当索引目标较多时, QR-树的整体性能优势非常明显W赵学胜等提出了基于Voronoi的动态空间索引 模型I该方法采用Voronoi势力范围取代R树 中的矩形空间区域并且建立区域之间的邻近关系0 Voronoi区域之间没有重叠.

20、可以实现无缝连接. 该法在进行实体目标的邻近搜索中独具优势同时 又具有很好的动态维护性。在LBS （Location Based Services）及 ITS （Intelligent Transportation System） 应用中窗口査询与邻近査询通常是一种连续査询. 相邻的査询之间是彼此相关的。为了提高目标搜索 与空间事件匹配的计算速度必须考虑移动目标所 处的移动环境中空间实体之间的邻近关系，而 Voronoi图具有很好的空间邻近特性.MBR与格网 都无法很好地判断实体之间的邻近关系。笔者在研 究中采用空简实傩的近似Vorgnoi图对移动目标进 行位置跟踪及导航地图显示不仅提高了査询

21、效率， 同时也改善了导航效果。基于Voronoi图的R索 引其缺点是区域过于复杂，占用大量存储空间。鉴于R树和变种R树的上述缺陷,C旦丄树 应运而生。CELL树借鉴BSP树和R树机制.采用 凸多边形代替矩形作为区域划分的基本单元子空 间不允许重叠。CELL树的优点是軽i方问次数世 R-树和R+树少因而是一种较优秀的空间索引 方法。缺点是区域过于复杂而且与X、Y轴不平 行.计算量大I® °2.3格网索引是一种基于Hashing的存取方式在二 维空间上通过将二维空间降维为一维空间的编码 （可以排序的格网编号）从而达到简化存取的目的， 其基本方法是将索引空间划分为相等或不相等的方

22、 格网.记录每一个网格所包含的地理对象。在GIS中 常用的是规则格网它既适用于点对象，也适用于面 对象.当用户进行空间査询时首先计算出用户査询 对象所在的网格通过该网格快速査询所选地理对 象。为了建立空间索引的线性表，常将格网惣丄沁L 码进行编码并建立Morton码与空间对象的关系何。格网索引机制的优点是算法实现较为简单结合 编码技术可以快速实现目标査询。导航系统中使用 这种格网技术可以快速显示移动目标所在的区域, 缺点是数据冗余较大缺少层次灵活性差（无法实现 多分辨率）另外，空间对象在素引表中为一变长记 录数据维护较为困难。3空间实体的地址编码不同于属性编码它可以 表达空间对象在参照系中的位

23、置，主要是为了空间 査询和位置检索。地址编码是数据索引的一种重要 机制已经成为解决多分辨率动态数据库难题的新 希望。空间实体的位置编码具有两个重要特征即 位置编码的维一性（一个空间对象在一种编码机制 中只有唯一的编码与之对应）和可映射性（位置编码 与空间位置具有映射关系）。通常编码是基于一定的空间剖分方法.按剖分方 法的不同可分为规则格网与非规则格网。基干规则 格网的编码方法有Morton编码、无边界QuaPA编 码110 201、球面QTM编码、球面HSDS编码等。基于非 规则格网的编码有两类一类是基于行政区划或功能 异构的专题编码如ZIP编码、街区编码、人口普査编 M-2008 China

24、 Academic Journal Electronic Publishing House. All rights reserved, 第26页地理与地理信息科学第20卷码、公安110编码、电信分区编码等:另一类是基于势 力范围的编码如Voronoi分区编码、移动蜂窝编码 等。地址编码的优点是采用一维表达多维空间直 观简单它集位置、层次(尺度)以及精度信息于一体, 是进行海量数据多分辨率表达的有效手段。同时, 地址编码也是非空间信息与空间信息联系的桥梁借助 地址编码可以实现二者的融合。地址编码在非欧空间 数据建模中具有优势。地址编码的缺点是在分析、显示 操作时要进行频繁的转换(转换成矢量数据)

25、不同标准 地址编码之间的转换成为数据共辜的一大障碍跨平台 通用性较差多分辨率下数据存储量极大。4在众多空间索引中不同的索引有不同的优缺 点及适用范围孰优孰劣很难定论。所以目前很多 GIS软件中采用多种索引机制并存、取长补短的策 略。基于以上分析.笔者在表1中对主要空间索引 方法进行了对比分析。1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第#页地理与地理信息科学第20卷(Dla He 1 The compurison between nnin spatial uidexes索引

26、名称创分区疑方袪B W数据分层文本索引KD钳按点二分点对象K- D- B W枝点二分点对象点四叉材梭点四分点对象面四叉树面域四分空间对彙R W面域矩形划分空间对象R变种射矩形或不 規则多边形空间对象格网索引面域 等(不等)分空问对象地址 编码基于格网刮分空间对象高效、动态素引具有较低的存储需求高效査询 动态索引高效査询操作简单支持动态更新查找快驟较縈和四叉材更灵汛查询区域貳盏度改善效率有所改善结合编码高效查询算法简单无法胜任海量空间敎据无法管理海量敎据更新困难主要用于点对象索引 删除算法效率较低.空间浪费:线、面对蠻索引困难 非平衡材空间利用率低适用于点对象詈鸚礬棘髀分辨率隐深度相莹大数据结构

27、复杂动态维护困难区域重委膨响效率动态维护性能较差算法复杂动态维护性能较盖敎据冗余大单一分辨率变长记录难以维护.多分辨率.可用于非欧曹零位置表达转换计算量大敎据存储量大.通用1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第27页地理与地理信息科学第20卷(D赵学胜基于QTM的球面Voronoi数据模型研究(博士论文)中国矿业大学.2002. 1 - 10由前述可知空间索引技术是GIS的关键技术 之一 它是快速査询、显示、更新地理空间数据的重 要指标。随着地理信息技术与应用的发展对

28、空间 索引技术提出了新的要求。针对多尺度数据的存储 组织，用户在同一管理系统下同时存储多个比例尺 的空间数据霄要研究专门的空间索引来实现不同 尺度数据的切换0丨；针对LBS及ITS应用的深入. 对移动目标的适时、快速査询提出了更高的要求需 要研究高效的移动目标数据库MOD (Moving Object Database)索引:针对复杂的非欧空间数据表达.有待 研究更为高效的空间对象地址编码技术。I 11严蔚敏吴伟民数据结构I ML北京：清华大学出版社.1997. 251 - 262 238 246.2蒋捷 韩刚味军 导航地理数掲庫IM.北京：科学出版社. 2003.90 106.3 BENTL

29、EY J L Multidi nicnsioniil binary search trees used for mr sociated searching (J Communications of the Asscxriation for Computing Machinery ,19758(9) :509 - 5174 ROBINSON J T. The K D B Tree :a search structure for large multidimensional dynamic indexes| A Proceeding of ACM SIC? MOD Intcrnationiil C

30、onference on Management of Data(C. 1981 10 1&5 FINKEL R A .BENTLEYJ L Quadtrees:a dxita structure for r(r Irieval on composite keysJ ). Acta Inf .1974 ,4(1) : 1 9.6 SAMET H. The quadtree and related hierarchical data structures J |. Computing Surveys .1984 .16(2) :187 260.171李萍空间索引技术的研究IJ 1.盐城工学

31、院学报(自然料学 版).2003 36(2) :26 - 29.18刘春史文中刘大杰导航电子地图中道路数据的空问索引和 俎织J工程勘察.2003(1) :3941.9梅承力周源华高维数据空间索引的研究【J L红外与激光工 程.2002 3KB :77 81.110吴立新史文中地理信息系统原理与算法【M.北京:科学出 版社.2000. 22 - 27.111陶志刚赵敬道谭逮成地理空间索引技术研究【J 1.測绘学 院学报.2002 39(1) :73 - 75.12 CUTTMAN A. R - Trees:a dynamic index structure for spatial searchi

32、ng! A |. Proceeding of ACM SIGMODC 1984. 547 557(13)郭芽郭蔽胡志勇大型GIS空间数据庫的有效索引结构QR WUb武汉大学学报(信息科学版)2003 .28(3):306310.H4)史文中郭蔽一种面向地理信息系统的空间索引方法(Jl.iW 绘学报.2001 .30(2) : 156 161.|15J SH匕KHAK SCHAWLA S谢昆者等(译)空间敖將库 M.北京:机械工业出版社.2004. 118 - 132.(下转第39页)1994-2008 China Academic Journal Electronic Publishing H

33、ouse. All rights reserved 第4期王 军竽:长江口潮滩环埴信息糸统功能设计研究第39页基于组件技术在Visual Basic(Visual C卄)环境 下可实现长江口潮滩环境倍息系统所需的各项功 能。该系统可以对潮滩环境信息进行编辑、显示、査 询、检索、统计分析、空间分析、空间数据挖掘、潮滩 围垦与保护辅助决策等。长江口潮滩环境信息系统 的建立为长江口潮滩环境监测与管理、潮滩围垦与 保护提供科学的决策依据。1刘光地理信息系统二次开发教程一 件篇【“】北京洁华 大学出版社.2003. 1 - 401.12胥可辉孙效功刘展等基于MapObjects俎件的海岸带地理 借息系统

34、开发最倍技术【J 音岛海洋大学学报.2002 .32(5): 770- 776.3 KOPERSKI K.ADHIHARYJ HAN J.Spatkil data mining:progress and challenged A. SIGMOD'96 Workshop on Research hsueson Data Mining and Knowledge Discovery (DM KS' 96C Canda: Montreal. 1996.14J李德仁王树良史文中等论空问数据挖掘和知识发现J 1 武汉大半半报(信息科学版).2001 ,26(6) :491499.6

35、69; 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第4期王 军竽:长江口潮滩环埴信息糸统功能设计研究第39页6© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第4期王 军竽:长江口潮滩环埴信息糸统功能设计研究第39页Design of the Environmental Information System for tlw Tidal Flat

36、of the Yangtze EstuaryWANGJun .CHEN Zhen - lou .XU Shi yuan .GUO Zhong yang .LU Yuc xian(The Kry Laboratory cf Go information Science of the Ministry of Ed mat ion. East China Normal University Shanghai 200062. China) Abstract : Based on the analysis of the necessity and urgency of upbuilding the en

37、vironmental iinformation system for the tidal flat of the Yangtze Estuary , tliis paper ooiKludcs the total object and techiwlogical routine of this inl'ormation systcm and expatiates the de velopmental thinking on the COM technology.Key Mords : the Yangtze Estuary: tidal flat; environmental inf

38、ormation 号stem: COM technology6© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第4期王 军竽:长江口潮滩环埴信息糸统功能设计研究第39页6© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved 第4期王 军竽:长江口潮滩环埴信息糸统功能设计研究第39页(上接第26页)161 SELLIS T ROUSSOPOULO

39、S N FALOUTSOS C The R" Tree:a dynamic index for multi dimensional objects | A |. The 13th Int. Conf, on very Large Databases .Brighton .V KC 1987.17 BECKMANN N . KRIEGEL H P SCHNEIDER R , cl a) The R * Tree: an efficient and robust access method for points and rectangles! A J. ACM S1GMOD t Atlantic . USACJ. 1990.181 ZHAO X S.JUNC ZHAO R L Dynamic spatial indexing model Kised on Vor