一种P2P环境下的B^+树索引管理算法  

An Algorithm of B^+ Tree Management in P2P Environment

作　　者：鞠大鹏[1] 黎明[1] 胡进锋[1] 汪东升[1] 郑纬民[1] 马永泉[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机研究与发展》2005年第8期1438-1444,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2001AA111010);国家自然科学基金项目(60273006;60433040);国家"九七三"重点基础研究发展规划基金项目(G1999032702;2004CB318205)

摘　　要：PeertoPeer(P2P)广域存储系统的分布式数据查询是其重要组成部分.其中对连续有序数据的查询还没有有效的算法.提出了一种在P2P环境下为连续有序数据建立分布式索引的算法——PBlink树.PBlink树具有可靠性高、吞吐率高、网络开销低、负载均衡的性质,比传统的分布式索引算法更能适应P2P环境.理论推导和实验数据证明,PBlink树算法的数据通信开销是传统分布式索引的20%,查询效率是其7倍.在承受整个系统中50%节点失效的情况下,仍可以保证85%查询的正确性,具有很强的可靠性.Peer-to-peer storage architecture is booming in these years for its immense capacity, self organizing, high scalability, fault tolerance and so on. Distributed query is an indispensable part of it, composed of query on keyword and query on numeric range. There are many efficient algorithms for keyword query in peer-to-peer storage architecture, but few for numeric range query. In this paper, PB-link tree, an efficient indexing algorithm for numeric range query in peer-to-peer storage architecture is presented. PB-link tree has attributes as high availability, low networking overhead, and load balance. The experimental results show that PB-link tree＇s networking overhead is 80% lower, and the query efficiency is 6 times higher than the traditional distributed indexing algorithms. It can also guarantee 85 % queries＇ correctness when half of peers fail.

关 键 词：PEER-TO-PEER 广域存储系统 分布式索引 PB-link树 

分 类 号：TP393.09[自动化与计算机技术—计算机应用技术] TP316.4[自动化与计算机技术—计算机科学与技术]