GIS常用数据结构

 

陈玉进 李泉 南京跬步科技有限公司 http://www.creable.cn

 

 

计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息表示、信息处理，信息表示直接关系到信息处理的算法与效率。信息（数据）之间往往是有重要的结构关系，数据结构就是对数据表示以及其上操作或功能的封装，分逻辑结构和存储结构两个层面。

逻辑结构定义了数据之间的逻辑结构关系。数据元素相互之间的关系称为结构，有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。

存储结构定义了数据实际在计算机中存储结构关系，是某种逻辑结构在计算机上的具体实现，分顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

在GIS开发实现中，空间索引、空间数据存储、地图管理、地图符号化及渲染、空间分析等都会用到很多的数据结构，下面作一些简要介绍，仅供参考，读者可以有不同的实现，效率也会有一些差异。

数组或链表，在GIS中应用最为广泛，几乎到处可见其身影。比如，线或多边形就是Point类型的数组，读shapefile文件时，文件已经记录下该要素包含的点数，数组的长度就被确定了，如果添加节点，最好采用封装好的动态数组或链表来存储；网格索引，用二维数组表示，每个数组元素记录下该网格范围所对应的数据存储地址，方便空间数据的检索；图层管理，一张地图是由若干个图层叠加而成，用数组或链表来存储这些图层信息，图层顺序调的整转化为数组或链表的删除和插入。

堆栈和队列，也属于线性结构，只是比数组和链表多了一些限制，堆栈是先进后出，队列是先进先出。比如，线性四叉树索引，用中序遍历的方法降四叉树线性化，其中树的中序遍历，非递归算法就需要用到堆栈；GPS轨迹跟踪，随着GPS点的增加，轨迹会越来越长，在实时跟踪过程中，可能只需要保留当前最近一段时间的点，更早之前的点被保存到数据库中，不再绘制，所以，采用循环队列来存储GPS当前一些点，利用了GPS时间顺序先进先出的特点，同时能循环利用队列；客户端图片瓦片缓存池，也可以采用循环队列，当前可视范围内获取到的新瓦片插入到队列中，当队列满的时候，淘汰最早存放在队列中的瓦片，同时保持队列缓存池的容量。

优先队列，是不同于先进先出队列的另一种队列，每次从队列中取出的是具有最高优先权的元素，二叉堆就是优先队列，分最大堆和最小堆，它能快速地从一个集合中找出最大（小）的元素。最优路径，算法中经常执行一步就是从后继节点中找出最优的节点，采用的就是最小堆，它能迅速地找出到当前节点权值最小的节点。

树，是一种递归定义的数据结构，一对多的关系，树是没有回路的连通图。四叉树索引，就是典型的树结构，按MBR（Minimum Bounding Rectangle 最小外包矩形）相交条件从树根一步步往下查找，筛选出要素子集；OGC中XML解析，XML（GML）结构本身也是树状结构；等高线，嵌套关系的表达，是树结构；属性数据词典库，采用Trie数据结构，多叉树的形式，建立属性词典库，通过字符串的匹配实现属性查询。

图，是一种数据元素间为多对多关系的数据结构，通常采用邻接矩阵或邻接表的方式来存储。道路网或管网的拓扑构建，道路网或管网属于网状结构，用图来描述节点与弧段之间的拓扑关系，便于最优路径、最大流最小割通路、爆管、旅行商等网络分析。

哈希，设计Hash函数代入key算出地址，存储value值，哈希查找效率高，但可能存在冲突，对内存空间占用相对较大一点。道路网或管网构建，以节点的node_id为key，以后继节点的集合为value；GML引擎，以图层编号为key，属于该图层的要素集合为value；线标注，线被裁减后，通过统一的key来拼接，以不同裁减路段集合为value。

以上简要介绍了GIS常用数据结构，但应用远远不止这些。数据结构＋算法＝程序，在数据表示和处理上，具体采用哪种逻辑结构，需要分析数据元素之间的逻辑关系，而确定了逻辑结构，还要考虑采用什么存储结构来实现，也是需要根据实际情况来分析的，数据结构直接关系到算法的具体实现及效率，在GIS开发实现中应用非常广泛。