云计算环境中高效分布式索引技术  

An Efficient Distributed Index Method for Cloud Computing

作　　者：黄斌[1,2] 彭宇行[3] 彭小宁[2] 

机构地区：[1]武汉大学计算机学院,湖北武汉430079 [2]怀化学院计算机系,湖南怀化418008 [3]国防科技大学计算机学院,湖南长沙410073

出　　处：《武汉大学学报（信息科学版）》2014年第11期1375-1381,共7页Geomatics and Information Science of Wuhan University

基　　金：国家973计划资助项目(2011CB302601);国家863计划资助项目(2011AA01A202);湖南省科技计划资助项目(2013FJ4335;2013FJ4295);怀化学院重点学科建设资助项目~~

摘　　要：针对现有索引方法中的性能瓶颈和维护成本问题,提出了一种分布式多访问入口B+树索引方法,实现了区间查询的高效并行,以及索引结构的较低维护成本。首先通过给分布式B+树的每个叶子节点维护一个路由表,并通过在树的不同层次上构建平衡二叉树来选择有关节点作为路由表的表项,实现区间搜索的高效并行;然后利用B+树节点分裂逐层传递性和B+树结构的平衡性实现节点分裂时只在较小子树内更新路由信息,减少更新消息数量,从而降低路由信息维护成本。实验表明,本文方法有很好的性能和较低的维护成本。To improve the performance and maintenance cost of existing index methods, this paper presents a distributed multi access entrance B＋ tree index method, which features：@ efficient paral- lel interval queries, and （2） and low maintenance cost for index structure. Our scheme relies on four key techniques to achieve the advantages mentioned above： （1） It provides a routing table for each leaf node of a distributed B＋ tree, so a interval search can be completed from any leaf node to break through the bottleneck caused by the root node in a distributed B＋ tree; （2） It constructs a balanced binary tree at different levels of a node, and selects the relevant nodes for its routing table; （3） It uses layer-by-layer transitivity of a B＋ tree node to split information to sense the node splitting position and only updates routing information within the subtree of a corresponding particle at the time of node splitting; （4） It uses the balanced structure of B＋ trees to only update single route information for relevant nodes at the time of node splitting, without adjusting the route tables of a large area. Our scheme has been implemented and evaluated. Performance results are encouraging.

关 键 词：云计算 分布式B+树 索引 性能 维护成本 

分 类 号：P208[天文地球—地图制图学与地理信息工程]