摘要: 混合型P2P系统的overlay网络构建在超级节点之间，可以获得基于超级节点d的P2P系统和结构化P2P系统两者的优点，例如：可扩展性、搜索速度和网络流量等。在本文中，根据负载和关键词的热门度，我们在符合指数分布的目录节点之间构建了一个基于树型结构的索引overlay，可以增强混合型P2P系统的关键词的搜索效率。
P2P系统的设计，大多是为了通过节点之间的直接链接而共享资源（例如：文件，文档，存储，CPU周期）。考虑到P2P系统的设计愿景，关键词的搜索对于资源和服务的发现是非常重要的。尤其是，节点找到所需资源对象的时间是最重要的P2P系统的性能指标。
分布式非结构化的P2P系统(如Gnutella)，与中心化非结构的P2P系统(如Napster)和结构化的P2P系统(如：CAN, Chord, Pastry和 Tapestry等)相比，查询响应时间更长，而且带宽的开销更大。主要原因在于非结构化的P2P系统(资源)搜索是基于消息转发机制的（即flooding）。为了提高资源发现速度，(学者们)虽然进行了大量的努力工作，但其效果仍达不到中心化或者结构化P2P系统的性能。针对非结构化的P2P系统，已经有许多工作试图通过基于关键词的关系和Bloom过滤器的查询扩展来改善关键字搜索的问题。然而，这些工作仍然存在可扩展性问题和转发机制相关的搜索速度问题。
结构化的P2P系统(如：CAN, Chord, Pastry和 Tapestry等)采用的分布式散列表（DHT）只能支持基于密钥的完全匹配的搜索。因此，即使是搜索速度比非结构化的P2P系统快，它也很难直接支持关键词搜索，因为在结构化的P2P系统中，对象是通过由他们的名字散列表唯一组织的基于身份的结构网络进行查找的。为了提供关键字搜索， 在DHT的overlay(网络)之上应该再建立另外一个层次。因此，结构化P2P系统支持关键字搜索遭受搜索速度慢，维修费用昂贵的制约。
混合型(半结构化)P2P系统介于非结构化和结构化之间，通过超级节点进行overlay网络的构建。他们在最近使用过的基于超级节点的P2P系统中具有较大的(应用)前景。此外，混合型的P2P系统可以避免非结构化P2P系统的某些局限性，如可扩展性和搜索速度，并且获得基于超级节点的P2P系统和结构化P2P系统的两者的优势，如快速查找速度和分布式的系统负载。但是，现有的混合型P2P系统主要关注于如何使用hypercube和DHT在超级节点之间构建结构化的overlay网络，关注于改善查找速度，而不是强调关键字搜索（例如，如何根据负载和热度组织关键字）。
在本文中，我们在符合指数分布的目录节点之间构建了一个基于树型结构的索引overlay。基于树型结构的索引overlay根据负载和关键词的热度进行构建，也就是说，分别采用基于负载的范围分区和基于热度的范围分区。基于负载的范围分区按照目录节点的负载划分索引。当一个关键词变得热门之后，采用基于热度的范围分区划分。它的目的是复制热点区域，其中包含一个热门的关键字的子节点。因此，它可以分配负载于子节点之中。基于树的索引overlay还提供了使用复制和基于波动率、贡献和服务时间的目录节点选择为一体的容错索引服务。
为了评估设计目标，将基于树的索引overlay与现有的关键词搜索机制在以下方面进行了比较：关键字搜索，性能，去中心化，负载平衡和容错。为了衡量关键词搜索的性能，对关键次搜寻的开销也进行了评测。数学的分析和评估表明基于半结构化P2P overlay的关键词搜索能够提高搜索速度，同时可以减少消息流量和维护开销。性能提高的主要原因是：(1) 本文的机制使用基于树的索引overlay发送和处理查询消息。(2) 对于一个给定关键词，它只扫描目录节点的索引列表。
本文的机制不同于已经存在的其他研究，该机制主要根据混合型P2P计算环境下负载和关键词的热门度，在目录节点之间构建了一个基于树型结构的索引overlay。该目录节点的选择是基于波动率和服务时间的。另外，本文的机制也使用了不同于其他方法的树的构建方法，搜索过程和容错算法。