（计算机应用技术专业论文）利用层次网格索引和双缓冲技术提高webgis性能的研究.pdf

重庆邮电学院硕士论文 摘要 利用万维网发布空间信息是g i s 发展的一个重要方向，它把g i s 与w e b 技 术有机结合在一起。随着一些商用w e b g i s 软件的推出，w e b g i s 应用也越来越 深入。但当前w e b g i s 普遍存在网络响应慢、服务器负担过重的缺陷，这也成为 w e b g i s 应用进一步推广的一大障碍。 w e b g i s 处理的对象是复杂的空间数据，这些空间数据都存储在空间数据库 里。要在当前流行的关系数据库中对空间数据进行存储的读取必须引入空间数据 引擎。为了访问存储在数据库中的空间数据，需要空问索引的支持。本论文在空 间数据库引擎和传统网络索引的基础上提出了一种新的空间对象索引技术一一 层次网络索引技术，它大大减少了传统网络索引需要的存储空间，并大大提高了 跟空间范围有关的查询的效率。 为了降低网络传输量以及减轻服务器的负担，本论文还提出了一种新的数据 缓冲技术，即双缓冲技术。双缓冲技术由客户端缓冲插件和服务器端缓冲组件构 成，客户端插件在客户端维持一个缓冲区，缓冲客户端经常使用的空间数据，并 能在客户端本地对缓冲中的空间数据进行处理。服务器端缓冲组件维持一个服务 器端缓冲，在该缓冲中维持客户端可能经常请求的数据。层次网格索引是双缓冲 技术的基础，由于它大大压缩了索引数据块需要的存储空间大小，可以将其传送 到客户端缓冲中，从而客户端缓冲在向服务器端请求空间数据之前，能够利用索 引块对用户的请求做初步分析，只向服务器请求客户端需要的数据，达到减少网 络传输量和缓冲中空间数据重用的目的。 最后本论文介绍了一个利用层次网格索引和双缓冲技术开发的w e b g i s 应用 实例。通过对比，其响应速度优于瘦客户端的w e b g i s ，也不存在胖客户端第一 次响应很慢的缺陷。 关键词：w e b g i s 、层次网格索引、双缓冲技术 重壅墅皇兰堕堡主堡塞 a b s t r a c t w e b g i si sa ni m p o r t a n tb r a n c ho fg i s i tc o m b i n e sg i sa n dw e bt e c h n o l o g y n o wal o to fw e b g i sp r o d u c t sh a v eb e e nr e l e a s e da n dw e b g i si sa p p l i e di nm o l e a n di r l ( 腓f i e l d s b u tt h e r ei sac o m m o nd e f e c to na l lw e b g i s t h ew e b g i sr e s p o n s e s s l o w l ya n dt h ew e b g i ss e r v e rb u r d e n sh e a v i l y t h eo b j e c tt h a tw e b g i sd e a l sw i t hi ss p a t i a ld a t a , a n dt h es p a t i a ld a t ai su s u a l l y c o m p l e x t h i ss p a t i a ld a t am a yb es a v e di nd a t a b a s e i nt h i ss i t u a t i o n ，t h ed a t a b a s ei s c a l l e ds p a t i a ld a t a b a s e w en e e da s p a t i a ld a t a b a s ee n g i n et or e a da n d w r i t et h es p a t i a l d a t a t h em u l t i l a y e r e dg r i d d i n gi n d e xi sas p a t i a li n d e xt h a tb a s e do i lt h es p a t i a l d a t a b a s ee n g i n ea n dt h et r a d i t i o n a lg r d d i n gi n d e x ，i tr e d u c e st h em e m o r ys i z et h a tt h e i n d e xn e e d sa n di m p r o v e st h er e s p o n s es p e e dg r e a t l yo na r e ar e l a t e dq u e r i e s d o u b l ec a c h e si sat e c h n o l o g yt h a tw e p u tf o r w a r d t oi m p r o v et h ep e r f o r m a n c eo f t h ew e b g i s i ta i i i sa tr e d u c i n gt h en e t w o r kt r a f f i ca n dr e d u c i n gt h eb u r d e no ft h e w e b g i sa p p l i c a t i o ns e r v e r i tc o m p r i s e so ft w op a r t s ：o n ea tt h ec l i e n ts i d ea sa p l u g - i na n dt h eo t h e ra tt h es e r v e rs i d ea sac o m p o n e n t t h ec l i e n tp l u g i nc a c h e st h e s p a t i a ld a t at h a tt h eu s e ru s e sf r e q u e n t l ya n dc a nd e a lw i t ht h i ss p a t i a ld a t aa tc l i e n t s i d e t h es e r v e rs i d e c o m p o n e n tc a c h e st h ed a t at h a tc l i e n tp l u g i n w i l ln e e d f r e q u e n t l ya n db a c k u p si t t h em u l t i l a y e r dg r i d d i n gi n d e xi st h ef o u n d a t i o no fd o u b l ec a c h e st e c h n o l o g y t h em u l t i l a y e r e dg r i d d i n gi n d e xr e d u c e st h es i z eo ft h ei n d e xd a t ab l o c k a n dt h i s m a k e si tp o s s i b l et ot r a n s m i tt h ew h o l ei n d e xd a t ab l o c kt ot h ec l i e n ts i d e b e c a u s e t h e c l i e n tp l u g - i nh a sa m u l t i l a y e r e dg r i d d i n gi n d e x ，i tc a na n a l y z et h er e q u e s tt h a tu s e r p u ti na n do n l yr e q u e s ts e r v e rc o m p o n e n tf o rt h ed a t at h a tn o ta tt h ec l i e n tc a c h ea n d 血eu s e rn e e d s u s i n gm u l f i l a y e r e dg r i d d i n gi n d e xa n dd o u b l ec a c h e st e c h n o l o g i e s ，w ec a l l i m p r o v et h ep e r f o r m a n c eo fw e b g i sg r e a t l y k e yw o r d s ：w e b g i s ，m u l t i l a y e r e dg r i d d i n gi n d e x ，d o u b l ec a c h e s 4 重庆邮电学院硕士论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得重鏖整电堂院或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：舒& - 玲 签字日期：缈年6 月，弘日 学位论文版权使用授权书 本学位论文作者完全了解重庆整电堂院有关保留、使 用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复 印件和磁盘，允许论文被查阅和借阅。本人授权 重庆邮电堂院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：徨羹屯、玲 导师签名： 侈槲 签字日期：们。p 年6 月f 日签字日期：伽烀占月，弦日 重壅墅皇兰堕堡圭笙茎 一 1 引言 第一章绪论 地理信息系统( 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 ，简称g i s ) 这一术语由r o g e r e t o m l i n s o n 于1 9 6 3 年提出的，当时世界上第一个用于土地资源管理的地理信息 系统c a g i s 在加拿大建立。从此g i s 作为一门新兴的学科迅速发展，目前，g i s 已经被广泛地应用到了世界许多国家和地区的各个部门当中，在地理、环境、地 质、农业、林业、水利、电力、城市规划、公用设施管理、国防等方鹾发挥着巨 大的作用。2 0 世纪8 0 年代g i s 开始走向成熟。对于g i s 的具体含义，当今没有 固定的认识，中国地质大学吴信才教授这样认为：g i s 是处理地理数据的输入、 输出、管理、查询、分析和辅助决策的计算机系统。这一理解基本上概括了g i s 的含义。 上世纪9 0 年代，随着传统的g i s 日趋成熟，与此同时计算机技术、网络技 术、分希式技术的出现，特别是国际互联网技术的迅速崛起，使万维网逐步成为 高效的信息发布渠道。人们对g i s 的要求也越来越高，以往多用于单一部门内 部的g i s 系统已无法满足信息化时代信息分布和资源共享的需求，越来越多的 人希望在i n t e m e t 上也能访问到g i s 的数据。而另一方面，i n t e m e t i n t r a n e t 技术 的发展也为g i s 面向社会提供了技术支持。利用互联网技术在w e b 上发布和出 版空间数据，以提供用户查询、浏览并获取所需的空间数据和应用，是g i s 发 展的必然趋势，这就产生了w 曲g i s 。 w e b g i s 是g i s 发展的一大方向，它是w e b 和g i s 结合的产物，它利用h 1 1 p 协议来完成客户端和服务器端的交互，与传统的c s 模式的g i s 相比较，它具 有很大的优势，主要表现在： 1 ) 用户不需在客户端安装专业的g i s 软件，只需通过普通的w e b 浏览 器比如i n t e r n e te x p l o r e r 或者n e t s c a p e ，就可以访问该w e b g i s 应用， 大大扩展了w e b g i s 的应用范围。 2 ) w e b g i s 系统易于升级和维护。由于客户端就是普通的浏览器，每次 系统升级，只需升级服务器端。大大减少了系统升级和维护的费用 2 论文的背景 随着w e b g i s 应用的发展，各大g i s 厂商推出了自己的构建w e b g i s 的开发 平台，如m a p i n f o 公司的m a p x t r e m e 、e s r i 的a r c i m s 等，还有很多国内厂商 重庆邮电学院硕士论文 也推出了自己的开发w e b g i s 的平台。每一种开发平台实际是一种开发w e b g i s 的技术架构。当前开发w e b g i s 的技术架构处于一个比较成熟的阶段。 针对各自的开发平台，在空间数据的存储方面，各大厂商也推出了自己的空 间数据库引擎，如m a p l n f o 公司的s p a t i a l w a r e ，e s r i 的a r c s d e 。利用空间数 据库引擎，可以把空间数据存储在二维关系数据库中，并能很方便的读取。 所有这些构建w e b g i s 技术架构和空间数据库引擎的提出，解决了构建 w e b g i s 应用的绝大多数问题。利用这些平台，用户可以很方便的构建出功能强 大的w e b g i s 应用。 但当前w e b g i s 系统存在一个共同的缺陷：服务器负担过重，系统响应速度 偏慢。这个缺陷极大的阻碍了w e b g i s 应用的推广。 当前，w e b g i s 与办公自动化技术( 简称o a ) 的结合是w e b g i s 发展的另 一个方向，在w e b g i s 的基础上，用户可以直接面对实际的地图办公，而不像过 去总是面对一些抽象的表来办公。基于w e b g i s 的o a 系统目前正处于发展阶段。 3 研究目标与内容 为了从技术上提高w e b g i s 的响应速度，首先要分析当前w e b g i s 的实现方 式，从实现方式上改进w e b g i s 。 当前w e b g i s 的实现方式主要有瘦客户端、中客户端和胖客户端三种方式。 如下图： 鼠m 刍 卜。乍。 下 舀函函 m e d i u m f a t 图i ：当前w e b g i s 的工作方式 在瘦客户端和中客户端方式下，客户端看到的地图是某种格式的图片。所有 的空间数据和属性数据都保存在服务器端，所有的地图操作也都由服务器负责处 2 重庆邮电学院硕士论文 理。在胖客户端方式下，空间数据随着客户端插件下载到客户端本地，用户看到 的地图是客户端插件根据下载到本地的空间数据绘制出来的。 当前这三种方式都存在缺陷。在瘦客户端和中客户端方式下，由于用户看到 的是地图图片，每次地图更新，服务器端都需要重新生成新的地图图片，再通过 网络把该图片传送到客户端。这种方式下，一方面服务器负担重，另一方面每次 地图操作的网络传输量也比较大。在胖客户端方式下，空间数据被下载到客户端 本地。但目前的w e b g i s 应用都是在用户第一次访问该w e b g i s 页面时，一次下 载所有空间数据，需要下载的数据量过于庞大。因而通过网络传输的数据量也很 庞大，往往需要等很久，空间数据才方可下载完毕，用户才能进行地图操作。 对当前w e b g i s 实现方式分析表明，以传输图片的方式来实现的w e b g i s 系 统的很难降低网络的传输量，不能从本质上提高w e b g i s 的响应速度。但在胖客 户端方式下，对胖客户端工作方式进行改进。通过客户端插件和服务器端缓冲， 可以达到在客户端和服务器端动态分批交换矢量数据的目的。避免了传统胖客户 端方式一次下载所有空间数据。这样既减少了网络流量，又大大减少了服务器的 负担。矢量数据下载到客户端后，由客户端插件负责维护，客户端可以再次使用 已经下载到本地的空间数据，并可以根据下载到客户端缓冲中的矢量数据来动态 绘制地图。 在上述思路下，针对提高w e b g i s 响应速度，本论文主要研究了客户端插件 和服务器端缓冲( 我们称之为“双缓冲技术”) 的构造及其实现。其目标是达到 在客户端和服务器端智能动态交换空间数据。 主要研究内容和工作如下： ( 1 ) 深入研究现有的w e b g i s 的实现原理。本论文主要针对m a p x t r e m e 实现 w e b g i s 的方式的进行了深入的研究。 ( 2 ) 层次网格索引及其创建方法。客户端要动态灵活想服务器端请求数据， 客户端必须有一个本地的空间索引数据快，以便客户端可以利用此数据 块分析用户的请求。 ( 3 ) 双缓冲技术中，客户端和服务区端之问的数据交换方式。 ( 4 ) 客户端插件的具体设计和实现。 ( 5 ) 服务器端缓冲组件的设计和实现。 ( 6 ) 在f m s 系统中，对双缓冲技术进行验证并得出结论。 重庆邮电学院硕士论文 1 引言 第二章w e b g i s 基础 地理信息系统( g i s ) 通俗的讲，就是整个地球或者部分区域的资源、环境 在计算机中的缩影。严格的讲，它是反映人们耐以生存的现实世界( 资源或者环 境) 的现势与变迁的各类空间数据及描述这些空间数据特征的属性，并在计算机 软件和硬件的支持下，以一定的格式输入、存储、检索、显示和综合分析应用的 技术系统。 g i s 是6 0 年代中期开始发展起来的新技术。它最初为解决地理问题，迄今 已成为一门涉及测绘学科、环境学科、计算机技术等多学科的交叉学科。 w e b g i s 是g i s 与w e b 相结合的产物，是分布式g i s 的发展和万维网发展 的结果。在w e b g i s 应用系统中，用户可以通过w e b 浏览器访问远程g i s 应用 系统。 由于本文主要研究如何提高w e b g s 的性能和w e b g i s 与o a 的结合问题， 主要涉及到对g i s 空间数据的处理，所以本章主要对g i s 所解决的问题和它所 处理的对象空间数据作一个简介，并指出g i s 相对一般信息系统的优点，最后 给出当前w e b g i s 的基本技术构架。 2 g i s 的基本概念 2 1 空间数据、属性数据与地图 g i s 应用系统呈现给用户的是一组组地图，它最大的特点是处理空间信息。 实际生活中的空间信息可以从如下几个方面来描述：位置信息、非位置信息( 俗 称属性信息) 和时间信息。位置信息用定位数据来记录，它反映自然现象的地理 分布，具有定位的性质；非位置信息用属性数据来记录，它描述自然现象、物体 的质量和数量特征。我们一般把用来记录位置信息的数据称为空间数据，而把记 录非位置信息的数据称为属性数据。 在g i s 研究中，把对我们有意义的空间实体称为一个空间对象。在不同的应 用中，空间对象的含义不同。比如在一个校园内，我们可以把一幢教学楼当成一 个空间对象，但在一个行政区域图上，我们就把整个学校当成一个空间对象。 空间数据的表示方式有矢量格式和栅格两种。矢量格式的空间数据是以点、 线、面等方式采用编码技术对空间对象进行几何特征的描述及在他们之间建立相 4 重庆邮电学院硕士论文 互联系的数据集，它注重空间对象的几何意义。矢量格式是表示空间数据的主流。 当前关于空间数据的存储格式及其相互转换大多数国家都有自己的国家标准。描 述空间对象的矢量数据往往是不规则的。如一个点，只需存储一对坐标位置，一 条线需要存储两个点，一条多线( 折线) 需要存储很多各顶点等。对于描述空闻 对象的矢量数据，没有一个固定的格式。栅格是以点阵的形式来表示空间对象的 几何属性的及其位置关系的。如各种格式的栅格图片等。栅格数据的存储比较单 问，当前有很多种栅格数据的存储格式。矢量数据精度很高，而且不会失真，操 作很灵活，但栅格形式的空间数据精度有限，操作比较死板。本论文中的空间数 据都指用矢量格式保存的空间数据。 属性数据是用来描述空间对象的非几何信息的，跟位置无关。如空间对象的 名字或其他属性。属性数据一般是规则的，例如描述一座建筑物，其属性信息可 以概括为：建筑施工日期、承建单位、设计单位等内容固定的字段。属性数据很 容易组织成一个二维表的结构。 实际生活中，描述同一个空间对象的空间数据和属性数据应该互相关联。如 对于一座建筑物，除了知道其位置、轮廓等空间属性外，其他属性信息( 如设计 单位、用途等) 必须与其关联。只有完整的空间数据和属性数据，对一个空间对 象的描述才有意义。 我们日常生活中看到的地图是空间对象的一种存储方式，根据空间对象的空 间数据绘制出地图，再根据属性数据标注地图。地图实际上是描述空间信息的一 种表示方式。 2 2 空间数据和属性数据的存储 当前g i s 处理的对象就是空间数据和属性数据，首先我们必须弄清他们在计 算机上的存储方式。 由于描述空间对象的空间数据很没有也不可能有统一的规则，所以也没有一 个固定的存储模式。在g i s 系统中，空间数据既可以存储在文件中，也可以存 储在数据库中。 把空间数据存储在文件中，是在空间数据库技术不成熟的情况下，传统的 g i s 统称采用的做法。这时不光要存储空数据，还涉及到空间数据和属性数据之 间的关联方式。各大g i s 厂商都有自己的空间数据存储格式，如m a p l n f o 的t a b 文件、e s r i 的s h p 文件等。o p e n g i s 也对空闻对象的几何形状作了统一的划分， 有如下几类：点、多点、线、多线、面、多面等。 若要把空间数据存储在目前的r d b m s 中，必须首先把空间数据分解，因为 r d b m s 是以二维表的形式来存储的，但空间数据很难有一个固定的存储模式， 重庆邮电学院硕士沦文 我们没办法定义这个二维表的结构。实际的做法一般是把空间数据都分解为基本 元素点、线，然后在这些点、线的上层建立空间对象和这些点、线的关联。并把 这些关联也存储在数据库中。在存取和读出空间对象时，通过一个固定的空间数 据库引擎来分解和组装空间对象。当前各大g 1 s 厂商都推出了自己的空间数据 库引擎，如m a p i n f o 的s p a t i a l w a r e ，e s r i 的a r c s d e ，针对不同的关系数据库 结构，它们都有对应的空间数据库引擎。关于空间数据库引擎的研究，这是g i s 应用领域的又一个大的方向，这里不作过多的说明，目前还没有真正意义上的三 维或者高维数据库。我们一般把存储空间数据的数据库称为空间数据库。现在的 空间数据库本质上还是关系数据库，要利用空间数据库引擎进行空间对象的读 写。 在当前g i s 应用系统中，对于比较小型的应用，可以把数据存储在文件中， 但面对大型的g i s 应用，由于空间数据鹿大，往往几百m ，如果还存储在文件 中，每次读取都要进行大量的磁盘操作，对性能有很大的影响，而且不便于管理。 在大型的g i s 应用系统中，应该把空间数据存储在数据库中。 属性数据一般存储在关系数据库中。属性数据一般很规则，我们可以根据属 性把空间对象归类，把具有相同模式的属性数据存储在一起。根据这个划分，我 们一般把地图划分为多个不同的图层，每一个图层中的对象的属性数据具有相同 的模式。每一个图层对应一个实体表，包括该图层的所有空间对象的空间和属性 信息。例如，在一个行政区域图中，我们可以把道路作为一个图层，把建筑物作 为一个图层等。一幅地图中的所有图层的叠加就是一幅完整的地图。由于同一个 图层中空间对象的属性数据模式相同，很容易组织成一张二维表。属性数据既可 以存储在文件中，也可以存储在数据库中。当前大多数g i s 应用系统把数据存 储在数据库中，因为这样可以充分发挥数据库系统的优势，便于管理和随机存取。 为方便管理和维护，空间数据和属性数据一般是分开存储的。空间数据和属 性数据之间的关联是通过空间对象标识来联系的。同一个空间对象的空间数据和 属性数据有相同的对象标识。m a p l n f o 和a r c i n f o 都是采取这种办法来让空间数 据和属性数据关联的。 2 3 空间索引 如果把空间数据存储在数据库中，那么首先面临的一个问题，就是如何处理 跟空间位置有关的查询。 空间数据的访问在很大程度上体现空间位置的局部性和相关性，例如地图开 窗显示，显示的实体都在一定的空间范围内；地图漫游显示，通常浏览到相邻的 区域。又如实体空间查询，也要分析一定空间范围内的所有实体。 6 重庆邮电学院硕士论文 这种数据访问的空间局部性使得空间索引技术在w e b g i s 系统中的作用变得 非常突出。所谓空间索引，就是指依据空间实体的位置和形状或空间实体之间的 某种空间关系，按一定顺序排列的一种数据结构，其中包含空间实体的概要信息 如对象的标识、外接矩形及指向空间实体数据的指针。简单的说，就是将空间对 象按某种空间关系进行划分，以后对空间对象的存取都基于划分块进行。 利用空间索引技术，能在各种空间操作之前对操作地理实体作出初步的筛 选，大大减少参加空间操作的空间实体数量，从而缩短计算时间，提高空间数据 访问的效率，达到快速响应用户提交给系统的空间查询要求的目的。 空间索引技术一直是空间数据库和分布式地理信息系统的一项基本技术，空 间索引的有无可能导致效率的相差几十甚至上百倍，高效的空间索引方法更是对 系统的性能有着决定性的作用。 3g i s 的应用 g i s 相对于传统的信息系统来说，它的主要优点体现在： ( 1 ) 可以对地理数据进行方便直观的管理和维护； ( 2 ) 可以实现跟空间位置有关的查询和分析功能，如多边形区域查询，缓冲 分析、管网分析等。这是传统信息系统所没有的功能； ( 3 ) 可以直观的把用户操作的结果反馈给用户。查询的结果直接出现在地图 上，而不是以前的一些抽象的逻辑表。 ( 4 ) 统计功能。用户可以在g i s 中，根据某一属性，在g i s 系统中，制作统 计图例，并呈现在地图上。 当前g i s 的应用主要有如下几类： ( 1 ) 专题地理信息系统 专题地理信息系统是具有有限目标和专业特点的地理信息系统，为特定专门 目的服务。如水资源管理信息系统、矿产资源信息系统、农作物估产信息系统、 水土流失信息系统和地籍管理信息系统。 ( 2 ) 区域地理信息系统 区域地理信息系统主要以区域综合研究和全面信息服务为目标。可以有不同 的规模，如国家级、地区或省级、市级等为各个不同级别行政区服务的区域信息 系统。 4w e b g i s 的技术构架 w e b g i s 是分布式g i s 不断发展的产物。它的主要功能是在w e b 上完成空间 数据的发布和分析等。当前的w e b g i s 大多采用多级的c s 模式，客户端为通用 重庆邮电学院硕士论文 的w e b 浏览器，服务器端为w e b 服务器和w e b g i s 应用服务器，还有专门负责 数据维护和处理的数据库服务器。 当前实现w e b g i s 的技术构架大致如下： m a p x t r e m e 是m a p l n f o 公司推出的架构w e b g i s 应用服务器的产品，a r c l m s 是e s r i 推出的架构w e b g i s 应用服务器的产品。他们的架构基本都如上图所示。 5 本章小结 g i s 的任务是采集、存储、管理、分析和显示地球空间信息，并对其 进行分析处理。它处理的对象是空间信息，空间信息包括空问数据和属 性数据，空间数据反映实际地物之间的空间位置关系，属性信息反映实 际地物跟位置无关的信息。在g i s 中，空间数据可以存储在文件中，也 可以存储在空间数据库中。当前还没有真正意义上的空间数据库，当前 的空间数据库是在二维关系数据库的给基础上，附加空间数据库引擎来 实现空间数据的存取的。w e b g i s 是g i s 和万维网技术快速发展的结果， w e b g i s 用户通过普通的浏览器来访问地图数据。当前的w e b g i s 构架是 一个多层技术构架，在w e b 服务器、w e b g i s 应用服务器和数据库服务器 联合下，向客户端提供地图访问服务。 由于g i s 在处理空间数据方面的特殊处理能力，当前g i s 已经在很多 行业部门有着广泛的应用。 重庆邮电学院硕士论文 1 引言 第三章双缓冲技术 随着很多w e b g i s 产品的推出，w e b g i s 应用也越来越广泛，但当前w e b g i s 的响应速度普遍较慢。通过对w e b g i s 的实现方式的分析，当前影响w e b g i s 性 能的主要因素如下： ( 1 ) 网络传输效率不高。 ( 2 ) w e b g i s 应用服务器负担过重。 ( 3 ) 网络传输量过大。 为了提高w e b g i s 的响应速度，除了从硬件上提高网络传输速率以外，主要 考虑2 、3 两点。即如何减轻服务器的负担和减少网络传输量。 双缓冲技术是解决上述问题的一个很好的办法。双缓冲就是在客户端和服务 器端分别建立空间对象缓冲区，在他们和空间数据库之间动态交换数据，从而来 提高w e b g i s 性能的一种技术。由于大量的空间数据存储在客户端本地，因而客 户端可以分担很大部分本属于服务器端的工作，从而大大减轻服务器的负担。又 由于客户端可以再次利用本地的空间数据，每次请求空间数据时，只请求客户端 需要的空间数据，其请求方式是动态灵活的，从而大大减少了单次请求的网络传 输量。在服务器端缓冲一部分空间数据，可以减少向空间数据库请求空间数据的 次数，也在一定程度上减轻了服务器的负担。 层次网格索引是建立在空间数据引擎之上的一种空间索引技术。它通过层次 网格划分，大大减少了索引快需要的存储空间，使索引快传送到客户端变为可能， 客户端插件也因此可以在客户端本地完成一些空间查询操作，做到在客户端对用 户的请求做初步分析，只向服务器请求客户端需要的数据，减少了网络传输量 本章主要讲述双缓冲技术的构架和该构架的基础层次网格索引技术。 2 层次网格索弓 在w e b g i s 系统中，空间数据是基础。空间数据一般存储在空间数据库中。 在空间数据库中，层次网格索引是一种空间数据索引办法，利用层次网格索引， 可以大大压缩空间索引块需要的存储空间大小，并一定程度上改善空间数据检索 的效率。 空间数据和传统数据的主要区别就在于复杂程度的不同，其复杂性来源于描 述- 个空问对象时必须同时包含其属性信息和空间信息，而空间信息本身也是具 有复杂性的。因此与一般的系统相比，处理地理空间对象数据的g i s 具有数据 9 重庆邮电学院硕士论文 量大，数据表达形式复杂的特点。 要在关系数据库中存储空间数据，需要在关系数据库上建立一个空间数据库 引擎。通过空间数据库引擎来提取和存储空间对象。 空间索引技术就是将空间对象按某种空间关系进行划分，以后对空间对象的 存取都基于戈0 分好的块进行。利用这种空间索引技术，能在各种空间操作之前对 操作地理实体作初步的筛选，大大减少参加空间操作的空间实体数量，从而缩短 计算时间。 层次网格索引是在空间数据库引擎的基础上建立的，它所索引的对象的是空 间对象。读取和存储具体的空间对象是由空间数据库引擎来完成的。读取和存储 空间对象时，先通过层次网格索引来检索该对象，再调用空间数据库引擎来完成 进一步的工作。 一种传统的普遍采用的空问索引方法被称为网格索引。层次网格索引是在网 格索引的基础上，改变了网格划分方法和索引建立规则，来达裂减小索弓r 决大小 和提高效率的。 2 1 传统的网格索弓 传统的网格索引( 下文网格索引如没特别说明都是指传统的网格索引) 的方 法如下：把矩形地理范围划分成m 行、n 列，得到m n 个小矩形网格区域， 每个网格区域便是一个索弓i 项，对每一个索弓l 项分配一个动态存储区，该动态存 储区记录了所有完全或部分落在该矩形区域内的空间实体的标识( 般是d 号) 和外接矩形( 记录空间实体的外接矩形信息是为了使索引在执行查询时更好地筛 选空间实体) 。传统的网格索引的索引块划分是规则的。 如下图3 1 所示。图中有两个空间对象a 和b ，对象a 是一个线对象，对 象b 是一个点对象。每个小正方形块表示一个空间索引项。箭头后面的矩形框 表示该索引项所对应的动态内存块。每个索引块都记录了全部或部分落在该矩形 区域内的空间实体的标识。 利用传统的网格索引处理空间查询的过程如下：首先根据查询区域，计算得 到要检索的索引块列表；再依次检索每个索引快所指向的动态存储区，得到被查 询的空间对象标识；再用该空间对象标识，利用空间数据库引擎来从数据库中读 取空间对象。例如，查询某一空间区域内的所有对象，我们通过计算，得到该区 域所包含的索引块歹i j 表，如果该索引块列表包括索引项t ，则通过索引项t 所对 应的动态内存块，我们可以很快得到该区域包含空间对象b 和a 。 1 0 重庆邮电学院硕士论文 圈3 1 ：网格索引图 网格空间索引的优点显而易见： 索引速度快。网格空间索引的索引区域划分是规则的，当给定一个查询范围 时，不需要访问索引项记录，就可以计算出与查询范围相重叠的所有索引顼。 索引可调整。可以通过对m 和n 的值的调整，使索引达到较高的效率。 这种传统的网格索引虽然效率较高，但缺点也很明显。对于线、面等具有一 定空间范围的几何实体，有可能落在多个网格矩形区域中，特别是当这类几何实 体范围很大时，会有很多索引项中记录了该实体的索引信息，造成重复存储。例 如，上图中，一个空间对象a 同时在6 个索引项中有记录。这种重复在网格较 稀疏的时候也许并不明显，但随着网格数的增加，被网格边界切割的空间实体占 空间实体总数的比例随之上升，重复存储的现象将十分严重。重复的索引信息不 仅增加了索引项所指向的动态内存区的内存空间开销，而且查询时要去掉重复实 体，增加了查询的时间开销，造成空间索引整体性能下降。 例如上例中，我们除了从索引项t 中可以检索到空间对象a 外，还可以从 其它五个索引项检索到空间对象a 。但在得到查询结果时，我们只能向用户返回 一个空间对象a ，而不是五个。这就需要在处理查询时，除掉重复的实体，这样 自然给空间对象的查询添加了额外的工作。 2 2 层次网格索弓 虽然传统的网格索引有很大的优点，但其缺点也很明显。主要缺点是索引块 庞大，冗余工作量大。但它的空间索引方式提供了一种思路，我们可以在这种思 路下，对它加以改进。 可以从如下两个方面对传统的网格索引进行改进： ( 1 ) 可以改变网格的划分方法； ( 2 ) 可以改变索引的组织结构； 改变网格划分方法的思路如下：可以不采取规则的矩形划分，只要我们找到 重庆邮电学院硕士论文 一种速度足够快，能根据用户的查询区域得到要查询的索引块的算法就行。采用 这种办法的索引快的划分方法有三角形、多边形等等。但在根据查询区域得到索 引块的算法实现上，其他形状的索引快都没有矩形的索引块的效率高。因为矩形 只需比较几次坐标就行，不用转换。 改变索引的组织结构的思路如下：改变传统网格索引那种网格大小一视同 仁，每个网格都建立索引项的做法。因为实际生活中的空间数据往往分布不均匀， 比如一个城市地图，在市中心，可能空间数据的密度很高，但在郊区。空间数据 可能就很稀疏。每个网格建立一个索引项，对于在市中心的索引向，可能空间索 引项所指向的动态存储区会很大，但是对于在郊区的索引项，可能有大量的索引 项为空。大量的为空的索引项也会耗去大量内存，并在用户查询时，也会耗去额 外的时间。而一个索引块所指向的动态存储区过大，也会降低空间查询的效率。 传统网格索引的这种分配不均匀的情况，往往进一步导致索引所指向的空间索引 动态内存区所占用的内存过大和降低查询时的效率。 结合上述考虑，为了提高传统网格索引的效率和降低其索引大小，我们提出 一种层次网格索引技术。 层次网格索引是多层的网格空间索引。它的基本思想是：一个矩形地理范围 被划分了i t _ 次：第一次划分把矩形地理范围平均划分为m t 行n 列，每个划分矩 形的长和宽为l t 和w t 。第二次划分时，选取m 2 和n 2 为划分矩形的长和宽( 其 中l 2 和w 2 分别比l l 和w l 大，一般隋况下，我们选择l 2 ：l = w 2 ：w 1 = k 2 ) ， 以此类推，直至第n 次划分为l 行1 列。每个划分矩形称为一个分区，从l 开始 对所有各次划分得到的戈分矩形统一顺次编号，每一个编号( 索引号) 对应于一 个划分矩形范围，所有完全落在这个划分矩形范围内的实体拥有该相同的索引 号，又称为分区号。划分到最后，整个地图就是一个网格。我们称第一次的m t n 。划分网格为第一层，依次类推，最后一次1x1 的整图网格为第n 层。编号 的规则如下：第一次划分的m - n t 个网格的编号为1 m 1 n l ，第二次划分 的网格的编号是：m 1 n 1 + 1 m ix n l + m 2x n z ，等等依次类推。按这样的 编号规则，越小的编号，其划分的网格块也越小。 层次网格索引的建立规则如下： 对于任何一个空间对象，它的分区号按如下规则分配：检查该对象空间范围 是否完全落在第一次划分的某个划分矩形中，如果不在，看它是否落在第二次划 分的某个划分矩形中，依次查找，直到找到一个完全包含它的划分矩形( 由于越 后来的划分，网格的长和宽就越大，因此，总可以找到一个完全包含该实体的分 区) 。找到后，该实体的分区号就等于此划分矩形的编号。按上述规则，一个空 间实体只在一个唯一的索引项中有记录。 用上述规则构造的层次网格索引如下图二所示( 注：图中一些为n u l l 的 1 2 重庆邮电学院硕士论文 索引项没有画出) 。图中的细虚线是第一次划分的网格，粗虚线是第二次划分的 网格。第二次划分的网格是第一次划分的网格的大小的2 5 倍。对于对象b ，在 扫描第一次划分的网格时，因为它完全包含在一个网格中，所以它的分区号就是 包含它的网格的分区号。但对于对象a ，由于它不完全包含于第一次划分的某一 个索引项，所以，在第二次划分的更大网格中找，发现它完全包含在第二次划分 的某一个网格中。所以它的分区号就是图中粗虚线网格所对应的编号。 相对于传统的单层网格索引，层次网格索引的优点如下： ( 1 ) 由于每一个空间实体都属于唯一的一个划分矩形，所以不存在重复的索 引信息，减少了索引所需要的存储空间的大小。上图中，对于空间对象a 和b 都只在一个网格索引项中有记录。 ( 2 ) 查询空间对象时，一个空间对象只在唯一的索引块中有记录，没有冗余的 索引信息，减少了数据库的负担。 对参a ， | _ - j f - | ， 淼b 图3 2 层次网格索引图 层次网格索引的好处是每个空间对象只对应一个索引项。当检索某区域内的 空间对象时采取如下步骤： ( 1 ) 通过计算得到包含于该区域内的和与该区域有交集的所有索引项的列表 ( 这些索引项包括不同层次划分的索引块) ； ( 2 ) 检索所有这些索引项，索引编号从小到大的顺序，依次检索每个索引项， 对每一个索引项，得到其空间对象标识。 但按照上述办法，存在一个问题。首先在第一步时，我们计算索引项列表时， 我们计算的得到的索引项所对应的区域可能比用户查询的区域大。因为我们计算 得到的索引项包括与查询区域有交集的所有索引项。所以有可能根据我们的索引 项，查询得到的空间对象完全不在我们的查询区域内。 为解决上述问题，可以采取如下办法。因为只有高层次划分形成的较大的网 格，才有可能出现上述问题，所以对于高层次划分的索引项，应检验该空间对象 的外接矩形，判断是否在我们查询的区域内或与我们的查询区域相交，如果是， 返回该空间对象的标识；对于是低层次划分，直接返回该索引项所指向的空间对 团田 重庆邮电学院硕士论文 象的标识。因为高层次划分形成的网格区域比较大，有可能我们检索的索引块的 大小比我们实际查询的范围大很多。所以有时需要借助判断空间对象的外接矩 形。在实际的实现中，可以根据网格划分方法，得到一个l 临界划分层次。在这个 层次之上划分的所有索引项所指向的空间对象需要检验其外接矩形。 从上面的查询步骤，我们可以看出，属于高层划分矩形的实体的数目越大， 查询的效率越低因为查询时要判断空间对象的外接矩形，增加了时间开销。所以 划分的结果应保证较高层划分矩形中的实体的数目较小。 为了计算机算法处理方便，可以选择层次网格矩形划分时采用每次等比增 长，即每次划分矩形的长宽都是其上一次划分所用的划分矩形的长宽的k 倍， 暂且称它为网格步长。选取正确的步长，可以改进索引的效率。首先便于根据查 询区域计算索引向列表，其次可以确定一个合适的步长，来使高层划分矩形中的 实体数据较小。 具体的层次网格索引的划分算法如下： ( 1 )调用空间数据库引擎，读出当前w e b g i s 应用所对应的空间数据的 m b r ( 最大边界矩形) 。 ( 2 )以该m b r 左上角为基准，对其进行网格划分第一次划分的长和宽为 m ，n 1 ，第二次划分的长和宽分别为m 2 ，n 2 ，依次类推。对所有划分 的网格顺次编号。 ( 3 )按网格编排顺序，对每个网格调用空间数据库引擎查找所有完全落在 该网格内的空间对象，得到该空间对象的标识。为该网格创建动态存 储区，存储该空间对象标识。 ( 4 )对于高次划分的空间索引矩形，在查找其所对应的空间对象时，得到 的结果中，应该排除已经存在于其他索引块动态内存区中的空间对 象，并为其创建动态存储区，存储其空间对象标识该对象对应的m b r 。 对层次网格索引的一些性能的考虑如下： 在上述创建层次网格索引的算法中，对于低层次划分的索引块，其动态存储 去中只存储对应空间对象的标识，对于高层次索引快，其动态存储区中要存储对 应的空间对象的标识和外接m b r 。对于低层次划分，每个空间对象需要4 个字 节( 空间对象标识的长度) 。对于高层次划分，每个空间需要的动态存储区大小 是4 0 个字节( 每个空间对象在索引块中需要存储其外接矩形和空间对象标识。 m b r 包含四个坐标，加上空间对象标识) 。一般低层次划分的网格会索引绝大部 分对象，平均每个空间对象所需要的动态存储去大小可能为6 字节。如果一个 w e b o l s 应用中所对应的空间对象有1 0 0 0 0 个，那么索引快的大小大约为：5 9 k 。 这大大压缩了空间数据索引快的大小。在查询效率方面，如果