淺析數(shù)據(jù)庫(kù)中的索引

劉彩利

【摘 要】 數(shù)據(jù)庫(kù)中的索引可使數(shù)據(jù)庫(kù)程序無(wú)須對(duì)整個(gè)表進(jìn)行掃描，就可查詢到所需數(shù)據(jù)。本文主要討論了索引的建立過(guò)程和基于分類(lèi)的索引查詢的過(guò)程，并給出了對(duì)檢索結(jié)果進(jìn)行排序的算法。最后通過(guò)實(shí)驗(yàn)對(duì)比了該檢索方法與常規(guī)檢索方法的檢索效率和檢索準(zhǔn)確率。

【關(guān)鍵詞】 索引 索引器 分類(lèi)索引

1 索引的建立

（1）索引器簡(jiǎn)介

影響搜索引擎檢索效率和查準(zhǔn)率的最大的因素就是索引的質(zhì)量。索引是一個(gè)搜索引擎最為核心的部分。通常情況下為了提高檢索的效率、檢索的查詢準(zhǔn)確率和良好的存儲(chǔ)系統(tǒng)的利用率，都需要對(duì)信息本身建立高效的索引。而索引器就是搜索引擎與信息采集軟件之間的“橋梁”。索引器就是建立索引數(shù)據(jù)庫(kù)的工具，目前搜索引擎建立索引主要采用全文索引的形式。

（2）倒排索引

目前中文全文檢索系統(tǒng)使用的索引方法主要有倒排索引和正排索引兩種。

正排索引的索引表結(jié)構(gòu)主要包含三部分：文檔的編號(hào)、文檔中的字和該字的位置信息，其中以文檔編號(hào)作為關(guān)鍵字。這種索引的優(yōu)點(diǎn)就是結(jié)構(gòu)簡(jiǎn)單和容易維護(hù)，但是它也有很大的局限性：每次檢索時(shí)都要掃描所有的文檔。

倒排索引則采用文檔中的字或者詞作為關(guān)鍵字來(lái)進(jìn)行索引，它的索引表結(jié)構(gòu)中還包含文檔編號(hào)和關(guān)鍵字在文檔中的出現(xiàn)位置。倒排索引的優(yōu)點(diǎn)就是一次能夠查詢到關(guān)鍵詞在所有文檔中的位置信息，因而相對(duì)于正排索引而言，它具有更高的效率，它的缺點(diǎn)就是索引表的建立比較復(fù)雜。

（3）基于單字的索引構(gòu)造

字表索引的構(gòu)建方法有很多種，下面介紹其中一種字表法索引庫(kù)的構(gòu)造方法。字表索引庫(kù)的數(shù)據(jù)結(jié)構(gòu)一般都采用字表，其中Pix表示字符i在源文檔出現(xiàn)的位置，它的值為該字符相對(duì)于文檔頭部的偏移字符的數(shù)目。字表索引的建立過(guò)程就是先掃描整個(gè)源文檔，然后將每個(gè)有效字符在源文檔中的出現(xiàn)位置加入到對(duì)應(yīng)的字表中。

字表倒排文檔的字表包含字符在源文檔中的所有出現(xiàn)位置，并為了區(qū)分位置與文檔的對(duì)應(yīng)關(guān)系，對(duì)該字符的字表進(jìn)行了分段的處理方式，段和源文檔之間有一個(gè)對(duì)應(yīng)關(guān)系，段是表示字符出現(xiàn)在源文檔中的位置。每個(gè)段包含三個(gè)部分：第一部分記錄文檔的編號(hào)，第二部分記錄該字符出現(xiàn)在源文檔中的頻率，最后一部分記錄字符出現(xiàn)在文檔中的所有位置。

2分類(lèi)索引查詢

分類(lèi)索引查詢的過(guò)程是用戶首先在Web窗口中輸入關(guān)鍵字，然后提交到Web服務(wù)器上，Web服務(wù)器接受用戶發(fā)送過(guò)來(lái)的關(guān)鍵字信息，然后在索引服務(wù)器中檢索相關(guān)信息，并對(duì)檢索的結(jié)果信息進(jìn)行排序，最后將結(jié)果返回給用戶的過(guò)程。分類(lèi)索引查詢的步驟如下所示：

Step1：用戶在輸入關(guān)鍵字并提交以后，服務(wù)器端相應(yīng)地會(huì)收到一個(gè)六元組。六元組的內(nèi)容包括：關(guān)鍵詞、區(qū)域、時(shí)間范圍、類(lèi)別標(biāo)識(shí)、分類(lèi)體系標(biāo)識(shí)和檢索范圍，其中檢索范圍是標(biāo)識(shí)此次檢索是基于標(biāo)題的檢索還是全文檢索。

Step2：服務(wù)器首先查詢分類(lèi)-服務(wù)器的映射表，然后根據(jù)該分類(lèi)-服務(wù)器映射表找到存放該用戶所要檢索的資源的索引信息的服務(wù)器IP，然后將查詢的任務(wù)分發(fā)給具體的其他幾個(gè)索引服務(wù)器來(lái)執(zhí)行相應(yīng)的具體查詢工作。

Step3：索引服務(wù)器在索引庫(kù)中檢索該關(guān)鍵字，取出符合條件的檢索結(jié)果，并對(duì)資源進(jìn)行打分，打分后按資源的得分情況對(duì)資源按由高到低的順序進(jìn)行排序，并將排序結(jié)果返回給前端的Web服務(wù)器。

Step4：Web服務(wù)器收到來(lái)自于各個(gè)索引服務(wù)器已經(jīng)排過(guò)序的檢索結(jié)果，然后利用歸并算法的思想對(duì)結(jié)果重新排序，并將最終的檢索結(jié)果反饋給用戶。

3 結(jié)果排序

本平臺(tái)對(duì)資源的打分算法采用經(jīng)典的BM2500 公式（該公式由Robertson和Sparck Jones提出，見(jiàn)公式3.1），并在這個(gè)公式計(jì)算的結(jié)果上，增加了對(duì)平臺(tái)資源權(quán)重的考慮，綜合考慮這兩種因素后，得到了本平臺(tái)的資源打分算法。

式（3.1）中的tf表示查詢?cè)~T在觀察文檔中出現(xiàn)的位置，qtf表示查詢?cè)~T在查詢中出現(xiàn)的次數(shù)，dl表示觀察文檔的長(zhǎng)度，avdl表示文檔的平均長(zhǎng)度，通常以詞或者詞組作為單元來(lái)表示。w（1）表示查詢項(xiàng)本身的權(quán)重，一般被稱(chēng)作Robertson/Sparck Jones（RSJ）權(quán)重因子，計(jì)算公式如式3.2所示：

其中N表示集合中的所有文檔的數(shù)目，R表示與該查詢項(xiàng)相關(guān)的文檔數(shù)，n表示該查詢項(xiàng)所查詢出來(lái)的文檔數(shù)，r表示相關(guān)文檔中含有該檢索項(xiàng)的文檔數(shù)。通常在進(jìn)行首次檢索時(shí)，由于缺少相關(guān)性的信息，R和r取值為0，此時(shí)查詢項(xiàng)的權(quán)重因子就簡(jiǎn)化為文檔訪問(wèn)頻度權(quán)重，如公式3.3所示：

本文提出的結(jié)果文檔排序算法與傳統(tǒng)的文檔打分算法不同，傳統(tǒng)的文檔打分算法缺少與用戶的互動(dòng)，顯然傳統(tǒng)的算法不夠人性化。本文提出的文檔排序算法結(jié)合了用戶對(duì)文檔權(quán)重的打分值，最后與傳統(tǒng)算法的得分值進(jìn)行綜合考慮得出結(jié)果。

先假設(shè)有一個(gè)文檔 d，Q為查詢?cè)~，Result（Q）為執(zhí)行查詢結(jié)果以后返回給用戶的結(jié)果數(shù)目，Score（d）為資源的得分值，W（d）為資源的權(quán)重，C（d）表示總記錄中包含資源d的個(gè)數(shù)，sum為查詢結(jié)果總記錄數(shù)。則此算法的步驟如下：

Step1：輸入集合T={T1，T2，……，Tn}；

Step2：對(duì)T中每個(gè)元素 執(zhí)行sum+=Result（Q）；

Step3：如果sum為零，則表示沒(méi)有查到結(jié)果，轉(zhuǎn)到Step5，否則執(zhí)行Step4；

Step4：對(duì)結(jié)果中的每個(gè)文檔d，返回文檔得分C（d）*Score（d）+W（d）。

Step5：返回結(jié)果，程序退出。

4 本章小結(jié)

本文淺談了索引的建立過(guò)程和基于分類(lèi)的索引查詢的過(guò)程，并對(duì)比論述了索引的一些算法。總之，有效的索引是影響數(shù)據(jù)庫(kù)性能的因素中最重要的一項(xiàng)，一個(gè)良好、完善的索引可以顯著提高數(shù)據(jù)庫(kù)的性能。