美学原理当空间数据中网格索引和四叉树索引的结合和优化的同种方案

文章版权由作者李晓晖同博客园共有,若转载请于大庭广众处于标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

针对判断一个点落在面图层中谁要素上之需求,在自家之前的博客:WebGIS中一致种植根据网格索引判断点面关系的不二法门(http://www.cnblogs.com/naaoveGIS/p/5148185.html)中起详实的叙述。其规律大致为:

             美学原理 1

其二处理步骤为:

                     美学原理 2

2.即网格索引的几个缺陷

a.网格索引方案分为了一个目录文件及一个数据文件,任何要进入时俱会先行念取索引文件,再读取数据文件,那么坏易并发资源争快状态,不便民并发支持。

b.网格的高低会严重影响至查询效率,但是要网格建立的足小,那么索引文件不断增大,同样会招致磁盘寻址花费的时刻增加。

c.数据的读取一定要是透过简单软IO,一软读索引,一浅读数据,会影响读取效率。

3.方案的优化,基于网格索引的索引四叉树划分

季交树、R树等均是空间索引常用底算法,这里自己选择以四叉索引来进行更优化。四立交树索引原理非常简单,即以一个限根据深度,不断平分,如图所示:

                     美学原理 3

这边优化思路是:将要素首先进行四叉树平分,然后针对每个叶子节点包含的范围重新展开网格索引生成:

            美学原理 4

4.优化方案的详细描述

4.1搜寻引的别步骤

a.首先生成为数据文件。

b.通过安装的四叉树深度,算有叶子节点的个数。然后经过获得到之要素四竞赛坐标,算有叶子节点的四角范围:leafminx、leafminy、leafmaxx、leafmaxy。

c.因要素个数与网格因子,算有尽范围外网格的个数,用全套范围之季比坐标与网格因子计算,得出一个网格的BlockXsize和BlokcYsize。

d.针对每个叶子节点,建立拖欠节点的网格索引,索引中带有了网格与素的附和关系。

变动文书截图:

                        美学原理 5

4.2数码读取

a.读取配置获取到要素的四角范围mapminx、mapminy、mapmaxx、mapmaxy、leafgeoxsize、leafgeoysize。

b.通过mapminx、mapminy、leafgeoxsize、leafgeoysize参数算有该XY坐标所在的网格索引编号。

c.读博该网格索引,获取到该索引的leafminx、leafminy、leafmaxx、leafmaxy、blockxsize、blockysize。

d.通过leafmaxx、leafmaxy以及blockxsize、blockysize算有XY所在网格索引的字节位置pos,将磁盘指针动至该pos处。

e.获得到目中涵盖的要素信息,比如要素所于的数据文件中之datapos。

f.读取数据文件,在该文件的datapos处将详细信息读取返回。

5.方案优点总结

a.将一个大索引文件分为基本上只目录文件,在大气如约机点并发访问时,可以拿压力负载至各级文件及,减少同一文件读取时的资源争快IO瓶颈。

b.每一个目文件大小大大削弱多少,读取会另行快,磁盘寻址也会见再快。

c.为增加网格命中单个(非多个)要素的几率,可以以每个网格的尺寸进一步压缩,其造成的网格索引增大会平摊到每个网格索引上,从而使副作用变多少。

6.尤其优化

a.在读取索引基本信息后方可拿该信息缓存至内存中,减少Config文件的IO次数。

b.生成索引时,如果一个网格只含了一个因素的信,可以用拖欠信息呢结到网格索引中。这样,查询时,如果查询及之网格只含单个要素,则可以直接以目中将要素信息得到,而非欲再行对数码索引做读取操作,减少对数据索引的IO次数。

                                                                        
—–欢迎转载,但保留版权,请于大庭广众处于标明出处:http://www.cnblogs.com/naaoveGIS/

                                                                       
    
如果您看本文确实帮了卿,可以微信扫一扫,进行小额的打赏和鼓励,谢谢
^_^

                                                                                                   
        美学原理 6