基于動態平衡樹的增量索引合并策略研究

李文杰

【摘要】 本文提出一種基于動態平衡樹的索引構建合并策略，以提高其索引合并和檢索的綜合性能。這種高效的索引文件結構，允許多個子索引同時存在，并在某一特定時間進行索引合并優化，實現高效增量地構建索引。實驗表明，采用類哈夫曼樹的動態合并策略優于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.