方志传记资料索引数据库的设计与实现

方志传记资料索引数据库的设计与实现

1.方志传记资料索引数据库的设计与实现 篇一

关键词：矢量数据,空间索引,四叉树,网络

在当今信息科技如此发达的社会, 地理信息系统获得前所未有发展。地理信息系统所面临的是组织、索引空间数据的问题。空间索引网络在分布式P2P环境下构建过程中, 将分布式QUAD-TREE与P2P CHORD网络相结合, 这样可同时对高效率的检索与良好负载平衡性能加以利用, 将网络索引更有效、更快捷地实现。

一、构建矢量数据结构索引网络

1、索引网络体系结构

体系结构由QUAD-TREE与CHORD两部分构成。下层将四叉索引树各层之间用控制点联系起来, 数据块最小外包矩形中心点则为控制点, 因每个四叉树节点都具有不同的地理区域范围, 所以, 为了确保索引的唯一性, 不会重复使用四叉树各个节点所对应的控制点。上层为CHORD网络, PEER节点是网络上的节点, 汇聚节点是CHORD上的节点。该层的通信层协议采用CHORD, 其为带弦环拓扑结构, 其路由定位机制具有高效、简单、可扩展、负载均衡等特点。

2、多图层、多尺度索引网络体系结构

以多尺度、多图层为基础进行思考, 下层是混合结构索引网络影响查询效率的主要原因, 因此, 需要分析下层分布式QUAD-TREE。在地理信息系统中, 通常以最小外包矩形为基础构建了四叉索引树, 亦或是改进。假设有S个图层, 而在每个图层中又包含了N个尺度, 如果将四叉树构建与每个图层的每个尺度中, 这样四叉树就需要构建S×N棵。不断增加比例尺与图层数, 同时对网络承载能力提出了越来越高的要求。四叉树的构建采用金字塔融合多尺度实现。将S× (N-1) 棵四叉树的负担减少, 每个图层建构一颗四叉树即可, 也将对网络负载能力的标准降低了。构建多尺度QUAD-TREE, 同一图层不同尺度之间具有的相关性可用金字塔形式表示。同一范围内, 地理信息从塔顶至塔底尺度越来越小、数据量越来越大、地理信息越来越细。除了存储本区域地理范围, 四叉索引数上的节点还需要对各自主节点与子节点的索引信息进行存储。

二、四叉树、网格、B+树、R树的对比

1、R树

R树所有叶结点在同一层, 且允许重叠各子树的索引空间。查找始于整个索引空间, 即从树的根结点开始进行查找。无论是对空间取悦中所有与之相交的空间目标进行查找, 还是对包含该点空间目标进行查找, 都可能是多路查找。但是, 当增加索引数据量时, 都会增大索引空间的重叠以及R数的深度从根结点开始查找, 相应增加了对须要访问的结点数、分枝数进行的查找, 显著降低了查找性能。

2、四叉树

在查找、删除、插入算法效率来看, 四叉树较R树更优, 在一定范围内, 四叉树性能越好, 说明其深度越大。当增加索引目标数, 四叉树的性能就更加突显出来, 显著优于R树。主要选择深度合适, 可以提升更高查找性能, 提升空间利用率。四叉树整体越具优势, 说明索引目标数越多, 因此适用于大型空间数据库系统。

3、B+树

B+树能够进行的查找运算有两种, 随机查找, 从根结点开始;顺序查找, 始于最小关键字。B+树索引不论是否实现成功查找, 但从根至叶子结点是每次查找必经之路。因此, 在查找过程中, 给定值等于终端结点上关键值, 索引才会终止。

4、网格

网格空间索引的基本思想是按照不同层次, 将空间区域划分为网格, 其大小相等, 将动态存储区分配给每一个小网格, 在该小网格动态存储区内, 存入空间实体标识号。通过划分, 每个小网格都会对应一个位移的空间实体, 在第一层某个小网格中有零维空间实体, 复杂空间实体、二维空间实体、一维空间实体落在哪层、哪个网格中, 需根据其MBR进行确定。

三、查询空间矢量数据算法

经过P2PQUAD-TREE和CHORD网络, 查询空间矢量数据。各节点间接或直接的通信以及网络核心功能由CHORD承担, 其PEER定位通过关键字得以实现, 在网络初始化, 建立四叉索引树之前, 需要对合适的关键字进行选取。定义关键字数据结构如下:

c Keyk= (scale, center, layername) , 其中, layername是图层名;center为数据块控制点的坐标;c Keyk为空间矢量数据尺度。关键字可作为QUAD-TREE中索引的唯一标志, 每个矢量数据块在经过划分后, QUAD-TREE中的索引节点与KEY逐一对应。查询算法伪代码如下:

一个PEER向另一PEER发送消息由“→”表示。集中式与分布式系统报文处理能力的分析可采用数学方式, 在降低网络负担的同时, 通过数据分析能够提升索引效率。集中式系统是在网络环境相同的条件下, 在同一节点上完成查询与数据操作的系统。假设由P个汇聚节点构成了上层CHORD网络, 且网络中的网络稳定汇聚节点不会退出。图层有S个, 每个图层包含N个尺度, 数据最大划分层数为fmax (fmax≥fmin) , fmin为最小划分层数。因尺度一共有N个, 在得知fmax及fmin的前提下, 推算N=fmax-fmin+1。假设将X作为每个图层需要查询数据块的个数, 被查询的尺度是scale (1≤scale≤N) , 划分层数越小说明尺度越大, 数据的划分层数在第scale个尺度时为:lN=fmin+scale-1。1作为系统四叉查询过程中节点向下遍历的次数, 因此, 查询一颗四叉树X块数据需要的报文数是:W=X´ (lN-fmin+1) =X´scale, S个图层就有:WS=S´4fmin´W。针对集中式系统而言, 同一个节点上着数据, 因此, 所有的报文由该节点进行处理。分布式系统处理报文能力提高, 说明网络中增加了汇聚节点, 从而将分布式系统的优势体现出来。

四、总结

多用户并发所产生的问题在应用空间数据服务技术后得以解决, 文章介绍P2P空间矢量数据索引网络, 并因此为基础, 探讨了查询索引网络空间矢量数据算法。以索引网络为前提, 将该较为简单的索引网络进行改进, 这样能够将网络性能更进一步提高, 如将缓存机制引入等。

参考文献

[1]付仲良, 刘思远.MR-tree空间索引的Voronoi图改进及其并行空间查询方法[J].武汉大学学报:信息科学版, 2012 (12) .

[2]余冬梅.基于K-Means聚类的R-树空间索引方法研究与分析[J].科技导报, 2012 (11) .