基于动态平衡树的增量索引合并策略研究

李文杰

【摘要】 本文提出一种基于动态平衡树的索引构建合并策略，以提高其索引合并和检索的综合性能。这种高效的索引文件结构，允许多个子索引同时存在，并在某一特定时间进行索引合并优化，实现高效增量地构建索引。实验表明，采用类哈夫曼树的动态合并策略优于LOG和GP方法。

【关键词】 信息检索 倒排索引 在线索引 动态平衡树

一、增量子索引空间布局

在线索引环境下基于索引合并的索引管理方法是目前为止效率最高的方法，大致可以分为重建、原地、立即合并和按某种策略进行合并，这些方法区别在于内存耗尽时内存索引写入磁盘所采用的策略。之前的方法允许合并子索引ip和iq当且仅当p = q + 1 或者q = p + 1，即只允许合并相邻的子索引。这种模式很不灵活，限制了一些更加灵活的索引更新策略的使用。当文档删除导致相邻的子索引大小相差悬殊时，索引合并的效率大大下降。定义子索引序列I为：

I =，其中，bi （0 ≤i < n） 表示子索引所包含文档全局编号的基数，di 表示子索引包含的文档总数，b0 = 0，bi + 1 = bi + di 。子索引 的每个文档有一个局部编号和全局编号，局部编号以0为基数，全局编号和局部编号的关系为=。

内存索引可以被看作一个子索引，参与磁盘子索引的合并。通过调整子索引的起始编号bi可以调整子索引序列的顺序，子索引的局部编号是以0为基数的，因此可以选择任意子索引进行合并，仅需要在合并前调整bi的值，使各个待合并的子索引全局编号连续，而不必遵循创建顺序合并。我们可以任意选择多个子索引进行合并。每个子索引包含词一部分posting-list，相当于将词的posting-list分割成多个子posting-list，分布在各个子索引中且连续存放。检索需要一次读入这些posting-list，并依照子索引序列的顺序将其首尾相接。

二、基于动态平衡树的索引合并方法

动态平衡树是一棵m叉树，树的节点是一个数据容器。从离根最远的叶子节点到树的根节点，该树被分为h层，同时满足下述要求：

1）设第i 层的第j个节点大小为d i ， j，则di ， j 满足： di ， j = 0 或者ci ≤di ， j/s < ci + 1；

2）第i 层节点个数要么为0，要么小于m；

3）第i层合并新节点进入第i + 1层，出现碰撞合并时，将两次合并合成一次进行。

其中s > 0，0 ≤j < m，s 是子索引的比例因子，假设子索引为Ibi ， di ， 则di/s为节点大小；特别地，当s取0时，则树的叶子节点大小均为1，而与该节点容器所包含的数据量无关。c （c ≥m） 是一个关键参数， 用于限定各层节点的大小。

三、实验与分析

3.1实验分析

从下图3-1a和b中可以看出，在使用256MB和512MB索引内存的情况下，DBT方法均要优于LOG和GP方法。当m=c=10，s=0时总体性能最好，但不稳定可能时间变化曲线出现局部交叉，这是因为当m值较大时，可能出现局部无索引合并，一次需要合并10个子索引，合并时间较长，当局部无索引合并时性能较好，有索引合并时性能较差。DBT方法可以通过参数c和m控制一次合并子索引的数目，m和c取值越大越能符合条件2，索引合并次数越少，索引数据读取和写入次数也越少，因此索引构建性能越优。

3.2试验结论

实验表明，基于合并的在线索引构建方法其性能受内存大小的影响，但具有更好的规模可扩展性；每一次合并应尽量选择较小的子索引进行合并，合并应该按照多路归并进行，通过减少索引数据反复读取和写入的次数来提高索引合并性能；磁盘上多个子索引并存的布局会降低检索性能，通过有策略地控制索引合并使子索引数目较少，可以控制检索性能的下降幅度在一个较小的范围内，索引合并代价也能大幅度降低，提高在线索引构建的总体性能。

参 考 文 献

[1] 郭瑞杰，程学旗，许洪波，王斌，丁国栋.一种基于动态平衡树的在线索引快速构建方法[J].计算机研究与发展，2008，10：1769-1775.