注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

回首望星辰

See you in the next world

 
 
 

日志

 
 

GIS海量数据的存储和读取  

2009-11-13 17:05:29|  分类: 软件开发 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

虽然现在硬件发展很快,内存、CPU等硬件指标都有很大的提高,但要PC机上处理GIS海量数据,还是显得比较吃力,而核心问题就在GIS数据的存储和读取上,这里主要涉及到三个子问题:1,图元是按怎样的顺序存储在文件磁盘中的(抑或是随机无规律的);2,对这些图元建立怎样的空间索引,这种索引是稀疏的,还是稠密的;3,读取数据的策略,比如,采用多线程,横向上,对当前窗口周围数据进行预读取,纵向上,对缩放图层的数据进行预读取,还要对最不可能访问的数据,进行淘汰。下面结合ShapeFile文件,来说明前两点。

ShapeFile文件通常包含三个文件:.shp .shx .dbf,.shp存储了图元图形坐标数据,.dbf存储了图元属性数据,.shx存储了每个图元记录在.shp文件中的位置。同时.shp .shx .dbf记录顺序是一致的。在GIS中,总体上有两种类别的查询:

一、图元查属性,就是通过对图元.shp文件的查询,定位到对应的.dbf属性数据记录。而对.shp的查  

询,需要对图形建立空间索引,以便加速图元查找的速度。确定需要查找的图元在.shp中的记录位

置,以确定是第多少条记录,由于三文件记录顺序是一致的,同时.dbf记录是等长的,可以迅速通

过计算得到对应的图元属性数据所在的位置,读取属性数据即可。

二、 属性查图元,就是通过对属性数据的查找,来定位到地图上相应的图形。而对.dbf的查询,为

了加快属性数据查找的速度,需要对.dbf文件的相关查询字段建立索引,比如B树索引。返回查询

到的第多少条记录或者记录集合,借助对.shx文件查找(三个文件记录顺序是一致的),直接找出

图形在.shp文件中的位置。

通过以上的分析知道,需要额外建立两个索引:对.shp图形建立的空间索引,对.dbf属性查询字段建立的索引。这两个索引既可以动态在内存中建立,也可以自己定义文件格式,物理地把索引给存储起来,以减少动态建立索引所花费的时间和内存开销。下面重点就.shp文件数据存储以及相应的空间索引的建立与存储,做详细介绍。

一、.shp文件的组织结构和空间索引的结构。

本文采用四叉树的方式来组织图元数据,如图,图中红色矩形方框是图元的MBR(最小外包矩形),采用改进的四叉树索引的方式,把每个图元的MBR分配到不同的节点上,然后按hilbert曲线的排序方式来组织数据,图元在文件磁盘上的排列顺序如下:

GIS海量数据的存储和读取 - 辉 - 回首望星辰

GIS海量数据的存储和读取 - 辉 - 回首望星辰

18、20、17、19、15、14、12、11、9、8、10、7、13、16、6、4、5、3、2、1、24、26、25、21、22、24  按这样的顺序(即从叶子节点开始,每采集两个子节点,就采集一个父节点,依次迭代上去)把图元数据一一写进文件,所有子节点都是按hilbert排列曲线的顺序来组织的,这样就兼顾了空间邻近的图元,在物理存储上也能尽量保持邻近,同时为了便于对这些数据建立空间稀疏索引,就采用了两个子节点一个父节点的存储顺序方式。那具体怎么建立稀疏空间索引呢?也就是把那棵四叉树,每个节点换成这样一种结构(MBR,对应图元集合在文件中迄始位置,图元集合的个数),稀疏空间索引就建立好了。我们可以把这样一种索引结构用自己定义的索引文件给保存下来,便于以后直接读取还原。

而对大范围的海量数据,需要建立大范围的网格索引,每个网格里关联这样一个线,面四叉树索引结构或者点网格索引结构,这里需要在网格索引的边界对线,面对象进行裁减,以至于不产生冗余数据。

在策略上,采用对象池技术,缓存最有可能被访问到的数据,同时采用线程池,缓存多个线程,提高CPU的工作效率。在横向,纵向两个方向上利用后台预读数据线程来预读数据,同时,为了保持对象池的大小,还要采取淘汰机制,把最不需要读取的数据淘汰出对象池。

这样一种组织方式和索引方式,在PC机运算海量数据,资源相对稀缺的情况下,只需要把空间索引调入内存,内存占用也不会太大,而且实现了大数据量的快速访问,因为空间索引数据量相对较小,数据组织是有规律的,空间索引是稀疏的。

二、属性数据的索引结构

       属性查图元,需要建立属性数据的索引,可以采用基于有限状态自动机的Trie结构,建立属性词库,以支持对属性数据的模糊查找。

       总结:本文从I/O这一角度,提出了一种新的数据组织与访问方式,为海量数据快速访问提供了一条途径,为了进一步提高效率,把所有图层合并为一个文件,定义新的文件格式,矢量数据的压缩都是进一步提高效率的重要方面,需要作进一步的考虑。

  评论这张
 
阅读(1739)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017