当前位置: 首页 > >

GIS空间数据查询优化技术研究_张宏

发布时间:

第 26卷 第 5期 2010年 10月

哈 尔 滨 商 业 大 学 学 报 (自然科学版 )
Journal of Harb in U n iv ersity of Comm erce ( Natural Sciences Ed ition)

V o.l 26 N o 5 . O ct 2010 .

G IS空间数据查询优化技术研究
张 宏, 夏洪山
( 南京航空航天大学, 南京 210016) 摘 要: 空间数据库是 G IS(地理信息系统 )的核心, 空间数 据查询是 空间数 据库的 关键技 术, 其 性能

的高低决 定着整个 空间数据库 的效率. 查询效 率一直是 G IS 系统 的一个瓶颈, 因此 研究空间 数据的 查询优化技术具有重要的意 义. 重点对提高数据库查询性能的关键技术 ) ) ) 空间 数据索引技术、 查询 处理算法、 空间数据访问技术进行了阐述. 关键词: G IS; 空间数据库; 查询效率; 空间数据查询 中图分类号: U 8 文献标识码: A 文章编号: 1672- 0946( 2010) 05- 0570- 03

Spatial data query and op ti ization of G IS m
ZHANG H ong , X I H ong-shan A
( N an jing U n iv ers ity o f A eronautics and A stronautics, N anjing 210016, Ch ina)

Abstract Spatial database is th e core o f G IS( Geograph ic Infor at io n System ) , w hile spatial : m data query is the key of the spatial database, its perform ance determ in es the eff iciency of the w ho le spatia l database Query effic iency is alw ays the bottleneck o f G IS so the studies of . , query and opti ize o f spatial data have becom e sign ifican. T o i prove the capability of spa m t m t ia l data query th is paper discusses on spatia l index, algor ith for query processin g and spa , m t ia l data accessing technology . K ey w ords: G IS spatia l database query effic ie ncy; spat ial data query ; ; 空间查询又称空间查找、 空间检索. 空间查询 是指从空间数据库中查找出满足某一条件的空间 目标的过程 ( 查找条件与空间位置有关 ). 空间数 据查询实质上是按照一定条件对空间对象的空间 数据和属性数据进行查询, 以形成一个新的数据子 集. 在 G IS中, 空间查询操作无处不在, 空间查询的 性能是这些应用系统成功的关键所在. 由于空间数据自身的复杂性, 空间数据查询的 效率成为了空间数据库性能的瓶颈, 而现有的关系 数据库查询优化技术不能完全适用于空间数据, 空 间查询优化势必成为空间数据库应用的难点和突 破点. 本文着重从空间索引、 查询处理算法以及空 间数据访问技术 3个方面对空间数据的查询优化 技术进行讨论.
收稿日期: 2009 - 07- 221 作者简介: 张 宏 ( 1984- ) , 男, 硕士, 研究方向: 航空运输经济地理信息系统.

1 空间索引技术
所谓空间索引, 就是指依据空间实体的位置和 形状或空间实体之间的某种空间关系, 按一定顺序 排列的一种数据结构
[ 1]

. 简单地说, 就是将空间对

象按某种空间关系进行划分, 以后对空间对象的存 取都基于划分块进行. 在空间数据库设计中, 为了 提高数据存取和管理的效率, 一般都要为空间数据 库建立索引, 不同的空间数据索引结构和索引管理 技术, 直接影响系统的性能. 目前国内外主要的空 间数据库大都是采用四叉树系列和 R - 树系列这 两类空间索引. 1 1 四叉树 . 四叉树是基于空间划分的一类索引, 将已知范

第 5期



宏, 等: G IS空间数据查询优化技术研究

# 571#

围的空间划分成四个相等的子空间, 如果需要, 可 以将每个或其中几个子空间继续四等分下去, 这样 就形成了一个基于四叉树的空间划分. 四叉树实际 上是指在 k 维数据空间中, 每一结点有 2k 棵子树, 用于对空间点的表示与索引. 每个结点存储了一空 间点的信息及 2k 个子结点的指针, 如二维空间的 四叉树, 每个子 结点对 应一 个矩形, 用 4 种 方位 NW、 S SE表示逐级将空间划分到含有数据 NE、W、 的个数低于某一值的矩形为止. 四叉树索引又分为 点四叉树索引和区域四叉树索引两类. 1 2 R树 . R树家族索引算法是面向对象分割技术的索 引算法, 将空间对象按范围划分, 每个结点都对应 一个区域和一个磁盘页, 非叶结点的磁盘页中存储 其所有子结点的区域范围; 叶结点的磁盘页中存储 其区域范围之内的所有空间对象的外接矩形. 这种 面向对象的索引数据组织方式节省了存储空间. R * + 树索引有 R - 树、 - 树和 R - 树三类. R

2 1 1 提高过滤步骤中对象*似程度 . . 在过滤步骤中的对象*似应当是简单的, 这样 才能够实现快速的过滤. 另一方面, 对空间对象的 *似程度越高, 滤除未命中对象的效果越好. 一般 来说, 用少量参数表示的凸*似是合适的. 通过目 标*似的方法, 和 M BR ( 最小包围 / 矩形 0 ) 相比, 其他*似描述的空间存取方法需要访问更多的数 据页, 但由于它们的*似质量高, 可以减少未命中 对象, 从而减少后继处理中的几何计算开销. *似 使用的参数越多, *似质量越高. 经过实验研究得 [ 2] 出 5- corner的*似性能和凸壳接* , 但所需要 的参数却要少得多, 它在*似性能和额外存储之间 达到了较佳的折中. 2 1 2 对候选集进行再次判断 . . 如图 2所示, R av ik # Kothur,i S iv a Ravada 在
[ 3]

过滤步和精炼步之间插入一个中间步骤, 对对象的 MBR与查询窗口的内部表示 ( Interio r( Q ) ) 的关系 进行判断, 满足查询条件 ( M BR ( G) 完全包含在 In terio r( Q ) 内 ) 的直接作为结果输出, 否则仍进行计 算, 但计算量已大大减少.

2 查询处理算法
空间查询处理的过程一般分为 2个步骤 ) ) ) 过滤和精炼. 从图 1可看出当执行空间查询时, 查 询处理器首先访问空间索引, 对其存储的空间对象 的*似表示做相关的操作, 过滤掉其中不满足查找 条件的目标, 余下的对象就构成了候选集, 这就是 过滤步骤. 接下来提取所剩候选目标的精确几何信 息进行计算, 得到查询结果, 这就是精炼步骤.

图 2 加入内部*似比较的空间 查询的处理步骤

2 2 提高几何检测速度 . 使用多次执行简单快速的算法取代复杂的几 何算法, 有利于提高几何检测的速度. 一般而言, 对 象分解技术是将对象分解为满足一些定量约束的 简单子对象 ( 例如三角形、 不规则多 边形、 凸多边
图 1 空间查询的处理步骤

形等 ) . 在对象分解后, 为决定一次处理所涉及的 子对象, 需要空间存取方法合理地组织对象各组成 子部分的位置和形状.

候选集当中有相当一部分对象并不满足实际 的查询条件, 尽可能地减少这样的对象进入精炼步 骤, 从而避免不必要的几何计算, 这是提高查询效 率的途径之一. 精炼步骤是对实际数据进行几何计 算, 显然这是耗费计算时间和空间的. 对这 2方面 的改进可以有效提高查询效率. 2 1 减小候选集 . 减小候选集可以从以下 2个方面进行.

3 空间数据访问技术
从广义的角度讲, 数据缓存技术的含义广泛, 它指对一切广义数据的缓存. 从狭义的角度讲, 数 据缓存技术专指对后台关系型数据库中数据的缓 存. 前者是基于 www 技术的, 是对站点、 网页、 链接 等非结构化或半结构化内容的缓冲; 而后者是基于

# 572#

哈 尔 滨 商 业 大 学 学 报 ( 自 然 科 学 版 )

第 26卷

传统的数据库应用领域, 对索引文件和数据库数据 等结构化内容的缓冲 . 在空间数据库系统中使用数据缓存技术, 可以 大幅提高数据检索效率. 其工作原理是: 为后台数 据库设置大容量的缓存区, 用于缓冲客户对数据库 的访问请求, 减少对服务器访问的输入 /输 出次数, [ 5] 从而提高数据库系统的检索效率 . 在笔者开发的 / 航空运输经济信息管理系统 0 中, 空间数据量非 常大达 115 M B, 因此系 统显示 时, 如果每次都从空间 数据库中读取 数据到客户 端, 这将造成很大的系统开销, 严重耗费网络带宽 资源. 另外, 就系统应用而言, 一部分数据, 如省界 线、 国界线、 高速公路、 铁路等属于基本背景信息, 此类信息更改频率较低, 则每次大规模地从服务器 上读取基本相同的数据, 也影响系统的效率. 由此 可见, 应用数据缓存技术可在一定程度上解决系统 应用中空间数据存取效率的问题, 从而提高系统信 息查询速率. 系统采用客户端数据缓存系统, 对数 据库一部分数据建立本地镜像, 将此类数据按照一 定方式组织在本地存储器上, 也即一种使用存储空 间换取查询速度的策略, 具体原理如图 3所示.
[ 4]

本系统中只建立了一级缓存, 在客户端首次连 接空间数据库时, 系统根据用户登录信息, 确定用 户权限, 读取该用户能够访问的空间数据至本地存 储器, 当用户执行空间查询时则首先读取本地存储 器上的数据, 无满足条件的数据时再访问空间数据 库. 客户端更新数据时, 首先更新本地缓存, 随后更 新空间数据库及其他客户端缓存, 以此保持数据的 一致性.

4 结



空间数据查询优化技术是空间数据库的关键 技术之一, 也是衡量 G IS 应用系统性能的重要指 标, 国内外很多学者都在积极探索更有效的方法来 提高查询速度. 结合笔者所开发的系统, 初步讨论 了一些改进查询性能的措施, 如何将这些措施更好 的应用到实际系统中, 将是进一步研究的方向. 参考文献:
[ 1] [ 2] 郭 方 薇, 郭 裕, 楚 菁, 胡志勇. 空间数据库索引技术 [ M ] . 上海: 放. 空间 查询 优化 [ J] . 中国 图像 图 形学 报, 上海交通大学出版社, 2006: 68- 83.

2001 6( 4 ): 307 - 314 , . [ 3] RAV I K, SI K VA R. E ff icient Processing of Large Spatial Q ueries U s ing In terior A pp roxi at ion[ C ] / /Proceed ings of the 7 th Inter m n at iona l Sym pos ium on A dvances in Sp at ial and Tem poral D atab ase, [ S l]: [ s n ] , 2001: 404- 421. . . . [ 4] [ 5] 过志峰, 王宇翔, 杨崇俊. 空间数据 索引与查 询技术研 究及 其应用 [ J]. 计算机工程与应用, 2002 23: 176- 178 , . 王 卉, 夏宏山 1 基于组件的 G I 技术研究 [ J] . 哈尔 滨商业 S 大学学报: 自然科学版, 2009, 25 ( 4) : 446 - 448 .

图 3 系统缓存工作原理




友情链接: