基于嵌入式数据库的移动GIS系统设计研究

白 凯，李 敏，王华兵 (长江大学计算机科学学院，湖北 荆州 434023)

基于嵌入式数据库的移动GIS系统设计研究

白 凯，李 敏，王华兵 (长江大学计算机科学学院，湖北 荆州 434023)

针对移动 GIS 平台的特点，设计并构建了一种基于嵌入式数据库的移动GIS系统。该系统的核心框架采用访问者设计模式设计空间索引接口，基于Packed R-tree 的数据结构与算法实现空间索引，基于适配器设计模式实现对空间数据的一体化存储。实际应用表明，该系统可提高移动 GIS 的空间查询效率与存储能力，且具有较好的可扩展性和灵活性。

移动GIS；嵌入式数据库； 空间索引策略； Packed R-tree

随着嵌入式技术和GIS技术的成熟和发展，两者相结合的产物——移动GIS(也称嵌入式GIS)的应用也逐步扩大并迅猛发展。移动GIS就是在嵌入式系统中实现的地理信息系统。与桌面计算机平台的GIS相比，移动 GIS具有体积小、功能简单、数据量不大、携带方便等特点。针对移动GIS的特点和嵌入式系统不足(如CPU运算速度慢、存储空间小等)，笔者设计并构建了一种基于嵌入式数据库的移动GIS系统。

1 移动GIS的特点

图1是一种典型移动GIS的主要组成结构图。

图1 移动GIS的典型组成结构图

移动GIS的数据除了具有GIS数据的数据量大和复杂的特点外，还必须符合嵌入式系统存储空间小和计算检索简单快捷的特点。这就产生了移动GIS数据处理中必须要解决的2大矛盾：①大数据量与小存储空间的矛盾。复杂的空间数据相对于传统的关系型数据库的数据来说数据量大，而且数据分布很不均匀。但是在嵌入式系统上，存储空间非常宝贵，这就要求用更有效的结构和方式使得GIS数据的存储空间更小，使用时所占内存更小。②复杂的空间检索需求与嵌入式系统的计算速度的矛盾。对于移动GIS数据库来说，其查询条件与空间位置相关而不是属性数据，因此必须采用比桌面操作系统更为灵活的机制来满足嵌入式系统的要求[1]。

2 移动GIS数据库的空间索引策略

解决上述2大矛盾，可以从2个方面来考虑：①采用合适的数据压缩技术；②定制合适的数据索引机制。由于嵌入式系统本身存储和速度的特点使得索引机制不能像在桌面操作系统上一样大而全，对于数据的管理和需求也不像桌面操作系统一样全面，通常它只是运用桌面GIS数据库的一部分功能。因此针对该数据特点需要定制特定的数据索引机制[2]。

常用的索引策略有：①基于B树的索引技术。其范例有R树及其改进，如Packed R树，R*树， R+树，Hilbert R树等；②基于Hashing的网格文件索引技术；③基于二叉树的索引技术，如KD树，KDB树，SKD树等；④空间填充曲线及四叉树类。

如果R树、四叉树、Buddy树作为只描述线型数据的主存索引，则四叉树空间占用量最小，Buddy树空间占用量最大。对于点查询，Buddy树速度最快，电量消耗最少，R树与四叉树在速度与耗电量上都差不多。对于范围查询，Buddy树与R树性能比较接近，速度差不多，耗电量也差不多，四叉树的速度慢，耗电量也大。对于最邻近查询，R树索引速度最快，耗电量最大，四叉树的速度一般，耗电量最小。可见，没有哪种索引结构有绝优势，应根据具体的系统实际应用来确定相应索引策略。

影响检索速度的一个重要因素就是检索树的深度。采用静态批量建树，这时R树的存储利用率最大，几乎达到100%，索引所占的空间最小，深度也最小。Packed R树的一个最大的缺点就是在插入方面存在缺陷。当需要插入一个数据的时候，基本上是对每一层的结点都需要进行分裂。由于在电子地图中不存在结点的插入操作，因此地图数据库对于用户来说是只读的、静态的。所以笔者在建树时采用Packed R树。

3 系统总体设计方案

图2是系统总体设计方案。在核心框架中采用一个抽象几何体类，该类与其他几何对象的基本拓扑关系进行比较，这样上层移动 GIS 空间对象的所有复杂形状可以通过统一封装成抽象几何体类的形式，实现对具体形状的解释，并以统一方式传递给索引框架进行空间查询、存储；索引结构的搜索、查询结果也封装成抽象几何体类返回给上层移动GIS。

图2 系统总体设计方案图

3.1空间索引框架

移动GIS对于空间索引框架的操作主要包括以下2种：①索引建立和修改，记录插入和删除；②空间查询，主要包括范围查询和点查询等。在公共抽象接口中定义了这些通用操作，而在索引结构类(Packed R-tree)中具体实现这些操作。通用存储接口对索引结构、空间数据的存储管理操作抽象定义，采用基于LRU 算法(Least Recently Used)的缓冲管理器实现对索引结构、空间数据的缓存，并在存储管理器中嵌入适配器接口实现索引结构和空间数据在移动 GIS 关系数据库的持久化。LRU算法的基本内容是：当内存的剩余的可用空间不够时，缓冲区尽可能先保留使用者最常使用的数据，即优先清除“较不常使用的数据”，并释放其空间。“较不常使用的数据”判断的标准是人为的、不严格的。

索引结构存储在关系数据库中，在内存中定义一个缓冲管理器，负责管理上层应用与底层关系数据库的数据传输。对于上层用户来说，这一处理是透明的。LRU算法实现的Packed R树索引结构的缓冲管理器，提高了索引结构的查询效率。

3.2缓冲管理器实现方法

缓冲管理器主要实现索引结构的存取操作，还要实现2个重要的缓冲操作：增加入口和减少入口。实现方法是：每个入口存储索引结构近期使用的一个节点信息，当索引结构载入或存储数据时，在缓冲区增加入口；删除数据时，在缓冲区减少入口。当缓冲区容量已满，而需要增加入口时，则采用 LRU 策略从缓冲区已有的入口中删去一个，加入新的入口。保证缓冲区的最后一项总是“较不常使用的数据即最近一段时间内最长时间没有被访问过的入口”，如果在操作过程中缓冲区溢出，则直接移走最后一项没有使用的数据块[3]。

3.3基于适配器的存储管理器的设计方法

在存储管理器中嵌入一个关系数据库的读写适配器接口，完成关系数据库中索引结构、空间数据信息和核心框架之间的读写逻辑及相互间数据传送。图2展示了存储管理器与嵌入式数据库之间的关系。该适配器接口分别继承存储管理器类和 GIS 地理要素类，完成以下适配功能：将字节组形式数据按Packed R 树节点数据结构解译成索引结构数据和空间数据2部分(对非叶结点，空间数据为空)，分别转换成索引表的数据和地理要素表的数据；将索引表的数据和地理要素表的数据封装成字节组数据。在进行具体的存取操作时，存储管理器通过使用适配器接口转换数据，用户可方便地利用 SQL 访问接口读写底层的移动 GIS 关系数据库。

4 结 语

笔者从嵌入式设备，嵌入式数据库和移动GIS三者的特点出发，本着充分利用嵌入式设备资源的设计思想，设计出一个完整的、高效的基于嵌入式数据库的移动GIS系统构架。该系统有一套相应的索引策略，能够高效低耗的管理数据，同时各个子模块之间实现了高内聚低耦合的特征，使系统有相当高的延展性。在移动GIS和嵌入式数据库之间设计一个核心框架，框架采用高效的索引策略，具有很强的针对性，其中基于适配器的设计模式实现了对空间数据的一体化存储。

[1]谢忠,凤鸣,马常杰.嵌入式空间索引策略[J].地球科学——中国地质大学学报,2006,31(5):653～658.

[2]裴凌,王庆,王慧青.嵌入式GIS的数据模型构造方法[J].东南大学学报(自然科学版),2005,35(3):480～483.

[3]蔡苗红,王庆.移动GIS的嵌入式空间索引框架的构建[J].计算机工程，2006，32(23)：91～93.

[编辑] 李启栋

TP393

A

1673-1409(2009)01-N082-03

2008-12-18

湖北省教育厅基金资助项目(B200612012)。

白凯(1980-)，男，2002年大学毕业，讲师，硕士生，现主要从事嵌入式系统方面的教学与研究工作。