面空间数据中网格索引和四叉树索引的重组及优化的一种方案

小说版权由小编李晓晖和博客园共有,若转发请于分明处标明出处:http://www.cnblogs.com/naaoveGIS/

1.背景

针对判断一个点落在面图层中哪些要素上的急需,在本身事先的博客:WebGIS中一种按照网格索引判断点面关系的方法http://www.cnblogs.com/naaoveGIS/p/5148185.html)中有详细的叙说。其规律差不多为:

             图片 1

其处理步骤为:

                     图片 2

2.脚下网格索引的多少个毛病

a.网格索引方案分为了一个索引文件和一个数据文件,任何请求进入时均会先读取索引文件,再读取数据文件,那么很简单并发能源争抢状态,不便利并发资助。

b.网格的大大小小会严重影响到查询效用,然而若是网格建立的丰裕小,那么索引文件不断增大,同样会招致磁盘寻址开支的年月净增。

c.数据的读取一定要经过一次IO,五回读索引,四次读数据,会潜移默化读取功能。

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

四叉树、Qashqai树等均是空间索引常用的算法,那里小编选用使用四叉索引来举行更进一步优化。四叉树索引原理卓殊简单,即将一个限制依据深度,不断平分,如图所示:

                     图片 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