● 摘要
本文提出了如何组建一个平衡二叉树网络结构的BATON集群并在该集群中实现检索的方法。该集群支持精确查找和范围查找，节点可以动态的加入或离开集群且不影响树结构的平衡性。精确查找和范围查找的最大时间复杂度为 。在实现检索的过程中本文提出了改进的n-Gram/2L和Random Jump Index（随机跳跃索引）。前者用于建立索引，它是在n-Gram/2L的第二级倒排表中加入对文章标识的索引，在对数据量较大的文章进行检索和索引时，该算法在保留原有算法特性的基础上进一步减少了索引冗余，降低了索引的存储量，同时对查询算法的优化降低了检索时的系统开销，并且减少索引中记录访问次数提高了查询效率。后者用于检索过程中间结果的合并与连接操作，与Jump Index不同，随机跳跃索引不受序列严格单调递增的约束条件限制，可以处理非顺序的序列，同时具有与Jump Index相同的检索效率。此外，随机跳跃索引中的每一个节点到根节点的路径固定且唯一，保证了索引的可信赖性。