李文杰

【摘要】 本文提出一種基于動態(tài)平衡樹的索引構建合并策略，以提高其索引合并和檢索的綜合性能。這種高效的索引文件結構，允許多個子索引同時存在，并在某一特定時間進行索引合并優(yōu)化，實現高效增量地構建索引。實驗表明，采用類哈夫曼樹的動態(tài)合并策略優(yōu)于LOG和GP方法。

【關鍵詞】 信息檢索 倒排索引 在線索引 動態(tài)平衡樹

一、增量子索引空間布局

在線索引環(huán)境下基于索引合并的索引管理方法是目前為止效率最高的方法，大致可以分為重建、原地、立即合并和按某種策略進行合并，這些方法區(qū)別在于內存耗盡時內存索引寫入磁盤所采用的策略。之前的方法允許合并子索引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的值，使各個待合并的子索引全局編號連續(xù)，而不必遵循創(chuàng)建順序合并。我們可以任意選擇多個子索引進行合并。每個子索引包含詞一部分posting-list，相當于將詞的posting-list分割成多個子posting-list，分布在各個子索引中且連續(xù)存放。檢索需要一次讀入這些posting-list，并依照子索引序列的順序將其首尾相接。

二、基于動態(tài)平衡樹的索引合并方法

動態(tài)平衡樹是一棵m叉樹，樹的節(jié)點是一個數據容器。從離根最遠的葉子節(jié)點到樹的根節(jié)點，該樹被分為h層，同時滿足下述要求：

1）設第i 層的第j個節(jié)點大小為d i ， j，則di ， j 滿足： di ， j = 0 或者ci ≤di ， j/s < ci + 1；

2）第i 層節(jié)點個數要么為0，要么小于m；

3）第i層合并新節(jié)點進入第i + 1層，出現碰撞合并時，將兩次合并合成一次進行。

其中s > 0，0 ≤j < m，s 是子索引的比例因子，假設子索引為Ibi ， di ， 則di/s為節(jié)點大??；特別地，當s取0時，則樹的葉子節(jié)點大小均為1，而與該節(jié)點容器所包含的數據量無關。c （c ≥m） 是一個關鍵參數， 用于限定各層節(jié)點的大小。

三、實驗與分析

3.1實驗分析

從下圖3-1a和b中可以看出，在使用256MB和512MB索引內存的情況下，DBT方法均要優(yōu)于LOG和GP方法。當m=c=10，s=0時總體性能最好，但不穩(wěn)定可能時間變化曲線出現局部交叉，這是因為當m值較大時，可能出現局部無索引合并，一次需要合并10個子索引，合并時間較長，當局部無索引合并時性能較好，有索引合并時性能較差。DBT方法可以通過參數c和m控制一次合并子索引的數目，m和c取值越大越能符合條件2，索引合并次數越少，索引數據讀取和寫入次數也越少，因此索引構建性能越優(yōu)。

3.2試驗結論

實驗表明，基于合并的在線索引構建方法其性能受內存大小的影響，但具有更好的規(guī)?？蓴U展性；每一次合并應盡量選擇較小的子索引進行合并，合并應該按照多路歸并進行，通過減少索引數據反復讀取和寫入的次數來提高索引合并性能；磁盤上多個子索引并存的布局會降低檢索性能，通過有策略地控制索引合并使子索引數目較少，可以控制檢索性能的下降幅度在一個較小的范圍內，索引合并代價也能大幅度降低，提高在線索引構建的總體性能。

參 考 文 獻

[1] 郭瑞杰，程學旗，許洪波，王斌，丁國棟.一種基于動態(tài)平衡樹的在線索引快速構建方法[J].計算機研究與發(fā)展，2008，10：1769-1775.