摘要
如何有效地支持多维数据范围查询是传统数据管理领域的研究热点之一.但是,在大规模分布式系统中,这仍然是一个具有挑战性的研究工作.VBI-tree是一个对等计算环境下基于平衡树的索引架构,在该架构上可以实现集中式环境下的多种支持多维数据索引的层次化树结构,例如R-tree,X-tree和M-tree等.VBI-tree设计的查询算法保证查询可以从树的任意位置开始,而不是像集中式环境下层次化树结构那样采用从树的根节点开始查询的方法,从而成功地避免了根节点引起的系统性能瓶颈问题.对于有N个节点的网络,索引方法可以保证查询效率是O(log N).VBI-tree提出了基于AVL-tree旋转的网络重构负载均衡策略可以有效地均衡负载.另外,在数据操作频繁的情况下,为了提高索引的性能,在VBI-tree上建立特殊的祖先-子孙链接形成VBI*-tree的结构.通过使用祖先-子孙链接,可保证对于相关查询区域的探索尽量发生在同层节点之间,而不是一直往根节点方向发送,从而减轻上层节点的查询负担,并且显著地降低了更新代价.模拟实验验证了提出的方法的有效性.
How to efficiently support multi-dimensional range search is one of the research hotspots in the traditional data management area. The design and implementation of multi-dimensional range query processing in large-scale distributed systems, however, remains to be a great challenge. VBI tree is a peer-to-peer indexing framework based on a balanced tree structure overlay and it can support any kind of multi-dimensional hierarchical tree structures such as R-tree, X-tree, and M-tree to be implemented in peer-to-peer computing environment. VBI-tree designs the search algorithms which can start from any position or any node instead of the root node used in the centralized hierarchical tree structures, thus successfully avoiding the performance bottleneck problem introduced by the root node. Specifically, in a network with N nodes, it guarantees that queries can be answered within O（logN） hops. It takes network restructuring based on AVL-tree rotation method as the load balancing strategy, which can balance work load efficiently. Additionally, a succinct structure of VBI^＊-tree is provided by setting up special ancestor-descendant links when facing a large number of data operations, which can improve the indexing performance. By using such new links, it is ensured that the related area checking to the queries will happen among the nodes of the same level to the greatest extent instead of sending checking requests directly to high level nodes, thereby reducing the load of high level nodes and also system updating cost. Experimental results validate the efficiency and effectiveness of the proposed approach.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2009年第4期529-540,共12页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60496325
60673137
60673134)
国家"八六三"高技术研究发展计划基金项目(2006AA01Z103)~~
关键词
多维数据
范围查询
对等计算
架构
分布式系统
multi-dimensional data
range query
peer-to-peer computing
framework
distributed system
