对等计算(Peer-to-Peer,简称P2P)是一个分布式资源管理、定位系统一它的目标是聚集大规模具有存储能力和处理能力的资源并且最小化资源访问和查询代价。这种系统的出现给网络应用带来了新的活力,因为所有节点可以分布地、平等地管理网络中的资源。但这种分布式数据结构也向网络应用提出了很多新的挑战,例如如何保证数据可达性、系统的动态可维护性、自主性、如何使用没有认证的、匿名的组件实现各种高级应用等。尽管对等计算系统在查询处理方面已经取得不少研究成果,但仍然存在许多问题有待解决。本文的研究工作的重点是把集中式环境下成熟的索引树结构引入对等计算系统,解决结构化对等计算环境下查询处理问题,包括:单维范围查询,多属性范围查询,多维范围查询以及高维文本查询的问题。本文的主要贡献如下:1.针对单维数据范围查询(range query),在BATON索引结构的启发之下,提出基于多叉树(m-way tree)结构的高效P2P索引结构BATON*。BATON*可以实现更高效的范围查询,更良好的均衡负载特性以及更强壮的系统容错能力。通过重新定义节点的路由表,并设计新的查询算法,系统保证查询效率可以达到O(log_mN)(Ⅳ系统规模,m是树分支出度),并且不存在根节点瓶颈问题。考虑到查询代价的降低是以路由表更新代价变大为代价的,文中给出了简单的基于出度的代价模型。该代价模型可以根据查询操作和更新操作的比率估算使系统性能最优的近似出度值。在分布式系统测试平台Planetlab下的实验结果验证了这种新的结构不仅提高了查询效率,还加强了系统的容错能力,同时基于出度的代价模型也得到了验证。2.针对多属性范围查询(multi-attribute range query),探索了基于属性分组降维索引的技术。多属性查询的特点是查询属性(维度)、或查询属性数目不固定。用多维数据索引技术处理多属性查询时,查询转换后,冗余查询太多。用单维数据索引结构处理多属性查询时,系统的存储代价、维护代价很高。但这两种索引结构各有各的优点,前者存储代价小,后者查询效率高。因此本系统提出把发布的多维数据按照属性分组,然后采用流行的降维技术,把按组划分的数据降维到一维数据空间,最后采用单维索引结构BATON*索引数据。这种方法的优点是综合考虑了数据存储、维护代价和查询代价,并且BATON*结构保证了查询效率。在各个属性维度上的查询概率已知的情况下,这种基于分组策略的多属性查询的优势将更明显。模拟实验结果表明,把分组索引策略和高效的索引结构结合,可以达到用低存储代价、低维护代价实现高查询效率的目标。3.提出对等计算环境下支持多维数据范围查询的索引架构(framework)—虚拟平衡二叉树。它将集中式环境下成熟的、基于空间划分的树索引结构成功地引入对等计算环境。系统设计了网络节点(peer)和树节点映射的方式、数据储存方式以及邻居节点选择策略,在此基础之上,给出范围查询算法,它可以有效地实现P2P环境下的多维数据范围查询和κ最近邻(KNN)查询。算法保证查询效率是O(logN)(N是系统规模),并且不会出现系统根节点瓶颈问题。该架构为不同的层次树索引结构定义了统一的数据操作、网络维护操作的接口。任何基于空间划分的层次树索引结构都可以方便地映射到这个架构上。不同的索引结构可以使用相同的接口实现,唯一不同的是数据空间划分的方式,和被划分空间的选择方式。系统中只有最底层的叶子节点存放数据,中间节点是虚拟节点,它只维护索引空间。系统中每个中间节点具有纵向链接(父子链接,近邻链接)和横向链接(邻居链接),通过这些链接可实现有效的错误恢复。AVL-Tree的树分支旋转(rotation)的方法用来解决在均衡负载之后树结构的重构问题:即恢复树结构的平衡性。在分布式系统测试平台Planetlab下的实验结果验证了这种结构的合理性和它处理范围查询的有效性。4.在VBI-Tree基础之上,本文提出了对原有架构的改良方案SDI,主要目的是降低原有系统的更新维护代价。新的系统去除了原来系统中每个节点记录祖先节点的索引区域信息的数据结构,取而代之的是一个简单的、特定的祖先链接,祖先链接均匀地分布在各个节点上。根据新的索引结构,系统提出了完全不同的查询算法,该算法仍然保证同样的查询效率,但大大降低了原来系统的查询代价,即实现了用更少的路由消息数找到同样多的结果。模拟实验结果表明,当数据维度、系统规模增大,数据分布不均衡性增强时,新的索引结构表现出更好的性能,因此该改良系统的可扩展性更好。5.针对对等计算环境下基于内容的查询处理,提出了一种基于层次化树结构和Chord的索引结构。这种结构最大的优点是没有全局信息维护节点。每个文件或查询可以表示成由关键词构成的向量。系统采用Chord结构索引词,用层次树结构对文件的词向量逐层分类(classification)和聚合(aggregation)。树的每个分支孩子节点个数在m和2m之间(m是树出度),每层中连续出现的g(m≤g≤2·m)个节点构成组,选出一个叶子节点作为该组的父节点。每组父节点采用TF.IDF(词频与逆文档频率)技术计算聚合向量里每个词的权值,该值越大,词的重要性越强。然后,父节点直接发布组内一定比率权重较大的词,其它的词聚合之后继续往树的高层传送做进一步处理。因为树在各个层次都选择一定比例的重要词汇发布出去,故这种层次化结构不存在全局信息维护节点。并且词被索引出去时,所在的层次越低,词的重要性越强。系统定义的查询算法保证查询可以从树的任意位置开始,另外查询包含的词通常是重要词,那么查询操作通常在树的底层进行,故树的上层节点的负载不会明显偏重。系统提出了改进性能的方法,利用这些方法可以进一步提高查询质量,降低查询和维护的代价。模拟实验结果表明,该方法具有良好的召回率(recall)和精确率(precision),并且不存在系统瓶颈问题。综上所述,本文详细介绍了四种基于树结构的索引结构,并且在本文提出的单维索引结构的基础上,设计了一种支持多属性范围查询的数据分配策略。这些工作旨在满足高级应用中的复杂查询处理需求。对每种索引结构,系统给出相应的查询算法的说明和实现,以及均衡负载方法,并且用详尽的实验来验证正文的分析和结论。这些方法对现有对等计算环境下的查询处理技术是有益的补充和改进。