版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、海量瓦片数据管理及优化方案1、 海量瓦片数据的管理1. 瓦片数据的特点瓦片数据是应用地图瓦片技术对地图数据进行切片所得到的,其对数据的切分规则通常是按照固定的若干个比例尺(瓦片级别)和指定图片尺寸,切成若干行、列的正方形图片,并以指定的格式保存为图片文件,再按一定的命名规则与组织方式存储到目录系统中或关系数据库里。地图切图所获得的地图切图也叫瓦片,瓦片金字塔是瓦片数据的一种多分辨率层次模型,从金字塔底层到顶层,数据分辨率越来越低,但是其表示的地理范围不变。瓦片数据是改进系统性能的最佳选择,它通过对地图数据预先渲染、切片,有效减轻服务器处理压力,减少网络负载和响应延迟。但是,瓦片地图服务都基于文
2、件方式进行图片缓存,这种方式实现简单,但因瓦片数据动辄几百至上千万个文件,且文件很小,导致磁盘存储碎片化严重,影响性能,且数据可迁移性差,无论是数据备份、迁移或是恢复都耗时漫长。如何优化瓦片技术,减小数据冗余,提高访问效率和管理效率是当前我们急需解决的问题。2. 海量瓦片数据的管理目前很多GIS平台对数据的管理方式虽然类似但也不尽相同。总结起来大概有三种方式。一是基于文件系统凡人管理,对切分后的数据按照瓦片数据的切分规则分别用文件夹存储管理,即地图瓦片数据的组织方式采用数据集、层、行目录结构描述,并基于文件系统的方式进行调度;此方法调度简单,检索过程依赖文件系统的文件查询方式和访问方式,容易实
3、现,但效率不高,维护=复杂,同时存在数据的安全隐患。图 1 瓦片文件组织二是采用大型的关系数据引擎:此种方式通常将预处理后凡人瓦片数据以一条独立记录的形式存放于数据库中,通常可以根据瓦片切分的层级或则金字塔结构分表存储以提高数据的检索效率。这种方式可以利用数据库的安全机制有效的解决基于文件系统管理存在的安全隐患,但是由于关系型的数据库对于此类数据很难建立快速的索引机制,所以相对调度效率较低,但是实现相对容易。三是基于GIS自身为满足空间数据检索而开发的一些专用数据库管理引擎,如GFS等等,这类引擎能够较好的解决数据调度的效率同时也能有效的避免文件系统存在的各种安全隐患,但实现复杂。3. 瓦片数
4、据的调度(1) 数据的格网分割由于影像等数据通常都是以一个大的数据文件格式的形式存在的,而如此庞大的文件不可能也不需要一次性的全部加载到GIS系统中来,更多的时候是我们仅仅需要加载我们所关心的部分数据。因此,此类数据在使用之前需要进行一些列的处理,即大的数据分割为小块的数据,这样在调度时仅仅需要调度用户需要的那部分数据即可。目前绝大多数GIS采用的分割方式是以固定大小的网格分割,在关系数据库中,对于数值和字符的索引已经比较成熟,且效率很高,但是对于诸如影像等变长的二进制数据来说很难建立的高效的索引机制。通常将对此类数据的索引通过网格分割,改成对格网编号的索引,从而大大提升索引的效率,从而提升数
5、据调度的效率。分割方法是按照一定的规则将大的数据分割为规则(如正方形区域)并且彼此之间没有重叠的图像块,并且给每个块一个唯一编号(如网格行列号),从而通过对格网编号索引实现数据的检索。索引算法如下:若(X0,Y0)为格网的起始坐标原点,设窗口显示的范围为(X1,Y1,X2,Y2),如图2所示。图 2 格网索引图起始格网的行号为:(取整)(X1-X0)/x),其中x为格网的宽度值;终止网格的行号为:(取整)(X2-X0)/x)+1;起始格网的列号为:(取整)(Y1-Y0)/y),其中y为格网的宽度值; 终止格网的列号为:(取整)(Y2-Y0)/y)+1;由此通过格网的起止编号来检索(X1,Y1,
6、X2,Y2)对应包含的数据块编号即可。(2) 金字塔建立金字塔是指在同一的空间参照下,根据用户需求以不同分辨率进行存储和实现,形成分辨率油由低到高,数据量由小到大的金字塔结构。这样在数据的最底层存储最高分辨率的数据,然后随着金字塔层数的增加,数据的分辨率依次降低,数据量依次减少,在金字塔的顶层,则仅仅存储用户所需要的最小分辨率的数据。在进行显示时,根据当前用户的浏览范围及显示设备的分辨率和范围,使用能够满足用户视觉要求的金字塔层次中的最高层数据作为显示数据,这种方式在一定程度上会增加数据存储开销,但能加快实时显示速度。(3) 基于金字塔的瓦片分割与数据调度数据金字塔建立之后要分别对其各层数据进
7、行格网分割,分割时要根据瓦片所处的层级及所在区域的不同对瓦片进行唯一编号,这便是瓦片数据的生成。基于金字塔的瓦片切分通常采用四叉树形式,即以金字塔最顶层数据为基准,依次向下做22n瓦片数量等大小分割,n为金字塔层级,这也就是前面所阐述的金字塔层级之间分辨率通常保持4倍关系的原因,如图所示。在GIS对瓦片数据的调度过程中,对顶层数据为基础,随着距离的拉近,当需要调度金字塔下一层数据时,系统自动对当前视域范围的瓦片按照四叉树规则,调度其下一层该瓦片数据对应分割后的四个子瓦片,因此新加载的瓦片所代表的地理区域总和与其父节点瓦片相同,从而达到加载更加清晰数据以满足显示效果的目的。如图3中,根据当前加载
8、的瓦片数据的编号可以按照四叉树分裂规则直接计算出其上一层或下一层需要加载的瓦片数据编号,如当前视域范围内加载的瓦片的空间编号为5-5-15-25(即第三个Face的第五级横坐标为15,纵坐标为25)的瓦片,随着距离的拉近需要更加清晰的数据来填充当前的地理范围,则对该瓦片进行四叉树分割后的四个瓦片的编号分别为3-6-30-50、3-6-30-51、3-6-31-50、3-6-31-51,从而可以根据瓦片的编号直接请求响应的瓦片数据即可。图 3 瓦片数据分割图2、 海量瓦片数据优化管理方案1. 瓦片数据的紧缩处理由于瓦片的数据通常以离散文件的形式存在,因此对于瓦片数据进行必要的紧缩处理可以大大提高
9、瓦片数据的可维护性,因此这或许也是越来越多的GIS平台均或多或少的对瓦片数据进行一定的紧缩处理的主要原因所在。而数据的紧缩方式对于紧缩后数据管理与维护的便捷性有着重要的影响,因此引擎的设计首先要考虑的就是紧缩数据的结构设计问题。对于紧缩数据的总体结构,本文对紧缩数据采用数据文件与索引文件相分离的形式,机数据文件中仅仅包含紧缩后的瓦片数据,而对于数据的检索信息则单独以检索文件的形式存在,其总体结构如图4所示。图 4 引擎数据紧缩的整体结构离散瓦片数据紧密的紧缩到数据文件中以形成文件体的数据文件,由于瓦片数据量庞大,而一个数据文件的大小也不可嫩无限增大,因此将文件限制在一定大小之内,从而可以保证数
10、据转移和数据可维护性,而且可以避免因部分数据毁坏而造成数据服务的整体瘫痪。多个数据文件构成一个数据文件集,文件集中每个数据文件都有一个唯一的ID编号以便于检索时的快速定位。数据文件完全有瓦片数据按照一定的规则组合而成,其中不包含瓦片数据的相关检索信息,对于堆积到数据文件中瓦片数据的检索是通过瓦片数据紧缩过程中同步建立的检索文件实现的。检索文件在瓦片数据紧缩时记录了每个瓦片数据的基本属性信息及所属数据文件的相关检索信息,从而可以通过对检索文件的解读实现瓦片在数据文件中的检索,检索文件也可以根据需要建立多个从而实现检索文件集的建立。由于数据文件仅仅用来保存瓦片数据,而检索文件是实现对数据文件解读的
11、唯一方式,因此紧缩后数据的安全性相较于紧缩前也会有较大提升。另外由于检索文件对于数据文件解析的重要性,因此保证检索数据的完整性与有效性是紧缩后数据能否正常对外提供数据服务的一个重要部分,设计中我们在瓦片数据紧缩时对索引文件的建立采用多文件相互备份和同步验证的方式保证索引文件的正确与有效。通过采用数据文件与索引文件相分离的方式可以较大程度的减小瓦片紧缩过程中的数据结构的设计复杂度。对于数据文件来说其存储过程不需要增加冗余的瓦片文件信息,从而可以通过相对简单统一的结构以实现瓦片数据的紧缩存储,并且在数据检索过程中,通过检索信息检索到的数据也是纯粹的瓦片数据而不需要做额外的数据过滤工作。而检索文件是
12、在瓦片数据紧缩过程中或数据维护更新中生成或更新的,它实现了对所有瓦片在数据文件中的检索信息以及瓦片数据自身必要信息的管理与维护。检索文件的结构设计与维护在一定意义下可以独立于数据文件,即当瓦片数据紧缩的前提下,通过修改或重建符合新功能需求的检索文件实现,从而可以较大程度的提高数据维护与数据服务的灵活性。2. 数据调度的快速索引模型关于索引的建立,可以根据常见的快速查找算法实现,简单的可以理解为根据算法要求对检索文件解析出来的数据按照一定的数据结构进行组织,从而使重新组织后的数据可以满足快速查找算法的要求。对于算法的选择,可以通过对检索算法的比较来确定,检索算法的效率可以通过平均检索长度ASL来
13、衡量,所以平均检索长度,是指为确定检索对象位置所执行关键码比较次数的期望值,比如对于含有n个对象的表,检索成功的平均检索长度为(公式1);ASL=i Ci其中:Pi表示第i个对象的概率,且i=1。Ci是检索到第i个对象所需要的关键码比较次数。检索方法的不同,Ci可以不同。依据这个方法,接下来将对本课题用到折半检索和四叉树检索算法进行分析。(1) 折半检索折半检索又称为二分法检索,它是对有序数据的一种有效检索方法,其前提是要求被检索数据为有序数据,也就是说此类数据必须可以按照一定的规则进行排序,排序后可以得到一个有序序列。在检索时首先取该有序序列中间位置的记录与待查数据进行比较,如果待查的数据较
14、该记录值“大”(大的含义不仅仅是数字比较上的大小,而是可以按照任何意义的规则进行比较),则待查的值必在该记录所在表中的后半部分;在这后半部分中再取中间位置记录进行比较,这样又可舍去这部分中的一半。依次反复,直到找到待查数据为成功或查不到为检索失败。对于折半检索的检索效率,从上述检索过程看,以有序序列的中点为比较对象,并以中点将序列分割为两个字序列,对定位到的子序列继续进行这种操作。所以,对序列中每个数据元素的查找过程,可以用二叉树来描述,称这个描述查找过程的二叉树为定树。如以有序表1、3、7、10、11、19、23、30、33、35、38、46、55为例,其按折半查找构造的判定树如图5所示。图
15、 5 折半查询算法判定树示意图可以看到,查询序列中任一元素的过程,即是判定树中从根到元素结点路径上个结点关键码的比较次数,即该元素结点在树中的层次数。对于n个结点的判定树,树高为k,根据二叉树的性质有n2k-1,即log2(n+1)=k,所以k=(log2(n+1)。因此折半查找在查找成功时,所进行的关键码比较次数最多为(log2(n+1)次。接下来讨论折半查找的平均查找长度。为便于讨论,以树高为k的满二叉树(n=2k-1)为例。假设表中每个元素的查找是等概率的,即pi=1/n则树的第i层有2i-1个结点,因此,折半查找的平均查找长度为:ASL=i Ci=1/n(120+221+.+k2k-1
16、)=log2(n+1)-1log2(n+1)-1所以,折半检索的时间效率为O(log2 n)。虽然折半检索的平均查找效率高,但折半检索只是用于顺序存储结构,因此其主要适合哪种一经建立就很少改动、而又经常需要查找的线性表。而对于本文探讨的瓦片数据紧缩也属于多读少写的数据类型,因此可以再数据紧缩后为检索文件建立静态索引信息或索引文件,并伴随着数据文件的维护更新而同步更新即可。(2) 四叉树检索四叉树在空间离散数据点的存储表达和索引中有着广泛的应用,如点四叉树、区域四叉树和CIF四叉树等,对于瓦片数据的四叉树索引我们采用线性四叉树编码的形式,即通过建立金字塔结构中的一个基本数据单元,即类似于树结构的
17、叶子节点,而由于瓦片数据在金字塔结构中编号(FileID)的唯一性,因此可以建立一个由瓦片数据编号映射而成的线性四叉树结构,进而通过对线性四叉树FileID的检索以实现对瓦片数据的检索。这个过程首先要建立瓦片数据编号到线性四叉树的映射关系,通常金字塔每一级都会遵从四叉树方式切分,由此金字塔的层级可以与线性四叉树的层级进行一一映射,即对于一个n层的金字塔建立一个D=n的线性四叉树,然后对于金字塔顶层瓦片将其编号直接与线性四叉树的根节点对应,再次对于顶层之外的每层瓦片数据编号与对应层级的线性四叉树节点进行一一映射。如图6所示。其中(a)为瓦片在金字塔结构的编码结构,编码第一部分为多金字塔结构中的区
18、域编码,即采用多金字塔结构的Face序号,第二部分为瓦片数据的层级编号,即对应线性四叉树结构的深度层级,第三部分为瓦片数据的行号,最后一部分为列号,节点在线性四叉树结构中映射如(b)中所示。经过这种映射之后线性四叉树中每一层的节点分别对应金字塔相应层中瓦片数据节点编号,同时将检索文件中对应的瓦片的检索信息存入该四叉树节点中,对于不存在的瓦片对应的四叉树节点,仅保留该瓦片编号而相应的数据检索信息留空,由此可以将金字塔中对瓦片数据的检索转化为对线性四叉树节点的检索。如此建立的线性四叉树的检索效率ASL,由于可采用的检索方式不同其检索效率也存在一定差异。四叉树节点的顺序检索过程就是对树中节点的检索,通过建立一个从根节点到被检索节点的一个遍历路径来实现节点的检索。如四叉树的深度为n,检索L层第i个瓦片所需要时间为从根节点到该节点最短路径的遍历时间,以上述映射线性四叉树为例,假设要检索节点3-3-5-7的索引则首先根据四叉树节点编码特征建立一个从根节点到该节点的遍历通道,这个过程可以跟进要检索的节点向根节点反溯的方式,即3-3-5-7父节点为3-2-2-3节点,依次向上追溯到根节点为3-1-1-1,3-0-0-0,即从根节点到检索节点的遍历路径为3-0-0-0到3-1-1-1再到3-2-2-3最后到3-3-5-7节点,从而需要四次节点访
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学五年级EV3机器人编程课程探索车二代教学设计
- 高二英语选择性必修一 Unit 1 Welcome to the unit 教学设计
- 浙教版七年级科学“生物体的基本单位(三)”教学设计
- 高三化学电化学章末综合测评复习教学设计
- 高中地理必修一《4.1 常见地貌类型》教学设计
- 初中八年级生物教学设计 生物与细胞专题复习
- 高中语文必修上册《声声慢》寻寻觅觅情境化教学设计
- 初中语文中考一轮复习记叙文阅读教学设计
- 小学四年级道德与法治教学设计:防灾减灾日主题班会-生命至上科学避险
- 初中九年级科学《认识能源》习题课教学设计
- 高甘油三酯血症管理专家共识(2025版)
- 体育场馆安全生产管理台账
- 2026年(完整版)院前急救知识培训题(含答案)
- 2026年行测类题库及答案详解
- 2026年度专项行动保密工作排查整治专项行动方案
- 桥梁伸缩缝更换工程施工组织方案
- 混凝土路面拆除及恢复施工方案
- 2026及未来5年中国航空飞行培训行业市场全景调研及前景战略研判报告
- 2025河南洛阳国裕集团招聘6人笔试参考题库附带答案详解(3卷合一版)
- 中医治疗慢性疲劳综合症中药治疗
- 梅毒防治知识培训
评论
0/150
提交评论