基于動(dòng)態(tài)平衡樹的增量索引合并策略研究

李文杰

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

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

一、增量子索引空間布局

在線索引環(huán)境下基于索引合并的索引管理方法是目前為止效率最高的方法，大致可以分為重建、原地、立即合并和按某種策略進(jìn)行合并，這些方法區(qū)別在于內(nèi)存耗盡時(shí)內(nèi)存索引寫入磁盤所采用的策略。之前的方法允許合并子索引ip和iq當(dāng)且僅當(dāng)p = q + 1 或者q = p + 1，即只允許合并相鄰的子索引。這種模式很不靈活，限制了一些更加靈活的索引更新策略的使用。當(dāng)文檔刪除導(dǎo)致相鄰的子索引大小相差懸殊時(shí)，索引合并的效率大大下降。定義子索引序列I為：

I =，其中，bi （0 ≤i < n） 表示子索引所包含文檔全局編號(hào)的基數(shù)，di 表示子索引包含的文檔總數(shù)，b0 = 0，bi + 1 = bi + di 。子索引 的每個(gè)文檔有一個(gè)局部編號(hào)和全局編號(hào)，局部編號(hào)以0為基數(shù)，全局編號(hào)和局部編號(hào)的關(guān)系為=。

內(nèi)存索引可以被看作一個(gè)子索引，參與磁盤子索引的合并。通過調(diào)整子索引的起始編號(hào)bi可以調(diào)整子索引序列的順序，子索引的局部編號(hào)是以0為基數(shù)的，因此可以選擇任意子索引進(jìn)行合并，僅需要在合并前調(diào)整bi的值，使各個(gè)待合并的子索引全局編號(hào)連續(xù)，而不必遵循創(chuàng)建順序合并。我們可以任意選擇多個(gè)子索引進(jìn)行合并。每個(gè)子索引包含詞一部分posting-list，相當(dāng)于將詞的posting-list分割成多個(gè)子posting-list，分布在各個(gè)子索引中且連續(xù)存放。檢索需要一次讀入這些posting-list，并依照子索引序列的順序?qū)⑵涫孜蚕嘟印?/p>

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

動(dòng)態(tài)平衡樹是一棵m叉樹，樹的節(jié)點(diǎn)是一個(gè)數(shù)據(jù)容器。從離根最遠(yuǎn)的葉子節(jié)點(diǎn)到樹的根節(jié)點(diǎn)，該樹被分為h層，同時(shí)滿足下述要求：

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

2）第i 層節(jié)點(diǎn)個(gè)數(shù)要么為0，要么小于m；

3）第i層合并新節(jié)點(diǎn)進(jìn)入第i + 1層，出現(xiàn)碰撞合并時(shí)，將兩次合并合成一次進(jìn)行。

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

三、實(shí)驗(yàn)與分析

3.1實(shí)驗(yàn)分析

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

3.2試驗(yàn)結(jié)論

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

參 考 文 獻(xiàn)

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