CAJ | 학술논문

如何有效地支持多维数据范围查询是传统数据管理领域的研究热点之一.但是,在大规模分布式系统中,这仍然是一个具有挑战性的研究工作.VBI-tree是一个对等计算环境下基于平衡树的索引架构,在该架构上可以实现集中式环境下的多种支持多维数据索引的层次化树结构,例如R-tree,X-tree和M-tree等.VBI-tree设计的查询算法保证查询可以从树的任意位置开始,而不是像集中式环境下层次化树结构那样采用从树的根节点开始查询的方法,从而成功地避免了根节点引起的系统性能瓶颈问题.对于有N个节点的网络,索引方法可以保证查询效率是O(log N).VBI-tree提出了基于AVL-tree旋转的网络重构负载均衡策略可以有效地均衡负栽.另外,在数据操作频繁的情况下,为了提高索引的性能,在VBI-tree上建立特殊的祖先-子孙链接形成VBI-tree的结构.通过使用祖先-子孙链接,可保证对于相关查询区域的探索尽量发生在同层节点之间,而不是一直往根节点方向发送,从而减轻上层节点的查询负担,并且显著地降低了更新代价.模拟实验验证了提出的方法的有效性.
여하유효지지지다유수거범위사순시전통수거관리영역적연구열점지일.단시,재대규모분포식계통중,저잉연시일개구유도전성적연구공작.VBI-tree시일개대등계산배경하기우평형수적색인가구,재해가구상가이실현집중식배경하적다충지지다유수거색인적층차화수결구,례여R-tree,X-tree화M-tree등.VBI-tree설계적사순산법보증사순가이종수적임의위치개시,이불시상집중식배경하층차화수결구나양채용종수적근절점개시사순적방법,종이성공지피면료근절점인기적계통성능병경문제.대우유N개절점적망락,색인방법가이보증사순효솔시O(log N).VBI-tree제출료기우AVL-tree선전적망락중구부재균형책략가이유효지균형부재.령외,재수거조작빈번적정황하,위료제고색인적성능,재VBI-tree상건립특수적조선-자손련접형성VBI-tree적결구.통과사용조선-자손련접,가보증대우상관사순구역적탐색진량발생재동층절점지간,이불시일직왕근절점방향발송,종이감경상층절점적사순부담,병차현저지강저료경신대개.모의실험험증료제출적방법적유효성.