PB-link树:一种P2P环境下对连续有序数据的分布式索引算法

摘要

Peer-to-Peer(P2P)广域存储系统以其海量、自适应、高可扩展、广域容灾等特性成为当前的研究热点.分布式数据查询是其重要组成部分.其中包括对关键字的查询和对连续有序数值域的查询.现有的P2P存储系统中基于关键字查询算法已经比较成熟,但对连续有序数据的查询还没有有效的算法.本文提出了一种在P2P环境下为连续有序数据建立分布式索引的算法—PB-link树.PB-link树具有可靠性高、吞吐率高、网络开销低、负载均衡的性质,比传统的分布式索引算法更能适应P2P环境.理论推导和实验数据证明,PB-link树算法的数据通信开销是传统分布式索引的20％,查询效率是其7倍.在承受整个系统中50％的节点失效的情况下仍可以保证85％的查询的正确性,具有极强的可靠性.