【畢業(yè)學(xué)位論文】（Word原稿）“天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)-計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)

北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 1 1 序言 信息檢索 (計(jì)算機(jī)科學(xué)與工程領(lǐng)域長久以來被廣泛研究的技術(shù)，有很多專門討論它的期刊和學(xué)術(shù)會(huì)議，例如美國國家標(biāo)準(zhǔn)局 (文本信息檢索會(huì)議 (1美國計(jì)算機(jī)協(xié)會(huì) (有自己的會(huì)議 究信息檢索。同時(shí)信息檢索還和數(shù)據(jù)管理技術(shù) (比如數(shù)據(jù)庫 )的研究交叉在一起，可以說，自從人類使用計(jì)算機(jī)管理數(shù)據(jù)等信息，就產(chǎn)生了信息檢索的需求。計(jì)算機(jī) 在人類社會(huì)的廣泛應(yīng)用，促使我們進(jìn)入了所謂的“信息化時(shí)代”，以計(jì)算機(jī)作為強(qiáng)有力的工具人類才有能力處理、存儲(chǔ)大量電子化的信息，信息規(guī)模與日俱增，也使人類面臨“信息爆炸”的威脅。如果不能有效的使用這些信息，我們就會(huì)被淹沒在信息的海洋里，造成“信息過?！焙汀靶畔⒗?。信息檢索的目的就是幫助用戶找到自己感興趣的信息，過程可以簡(jiǎn)單描述為：用戶提交查詢請(qǐng)求 (通常是關(guān)鍵字 )，系統(tǒng)返回與用戶查詢相關(guān)的信息。信息檢索要解決的問題不是一成不變，它必須跟上人類信息爆炸式增長的現(xiàn)實(shí)。 九十年代以來，獲得了飛速發(fā)展，徹底的 改變著人類的工作和生活。據(jù)計(jì)算機(jī)世界網(wǎng) ()報(bào)道，美國網(wǎng)址專家凱利研究后指出：“ 自網(wǎng)景公司于 1995 年申請(qǐng)上市以來的 2000 天中，人類居然創(chuàng)寫了 30 億網(wǎng)頁，建立了 2000 萬個(gè)網(wǎng)址，而傳送的電 子 郵 件 就達(dá) 3 兆 5 億則之多 。 網(wǎng)址還將繼續(xù)擴(kuò)張多元發(fā)展，但只有少部分是為了營利賺錢，而其他部分則是啟發(fā)自熱情、熱心及公共責(zé)任，亦即是一種對(duì)未來也許可用于經(jīng)濟(jì)用途的信心。在這 30 億網(wǎng)頁中，事實(shí)上只有 30%是由公司企業(yè)所創(chuàng)寫，其他 70%都是由非營利機(jī)構(gòu)與一般民眾所創(chuàng)作，顯現(xiàn)網(wǎng)址人所要的是相 互分享。 ”總之，互聯(lián)網(wǎng) (漸成為了信息時(shí)代人類發(fā)布、交流和共享信息的載體，極大地促進(jìn)了人類知識(shí)的增長和傳播。 中國也獲得驚人的發(fā)展。根據(jù) 國互聯(lián)網(wǎng)絡(luò)信息中心 )在 2002 年1 月的統(tǒng)計(jì)信息表明 1，我國上網(wǎng)計(jì)算機(jī)數(shù)約 1254 萬臺(tái)，其中專線上網(wǎng)計(jì)算機(jī)數(shù)為 234萬臺(tái)，撥號(hào)上網(wǎng)計(jì)算機(jī)數(shù)為 1020 萬臺(tái)；我國上網(wǎng)用戶人數(shù)約 3370 萬人，其中專線上網(wǎng)的用戶人數(shù)為 672 萬，撥號(hào)上網(wǎng)的用戶人數(shù)為 2133 萬，同時(shí)使用專線與撥號(hào)的用戶人數(shù)為 565 萬。除計(jì)算機(jī)外同時(shí)使用其它設(shè)備（移動(dòng) 終端、信息家電）上網(wǎng)的用戶人數(shù)為 118萬。我們北京大學(xué)計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室開發(fā)的“天網(wǎng)”系統(tǒng)在對(duì)中國國內(nèi)互聯(lián)網(wǎng)的一次搜集結(jié)果顯示 2，共收集到網(wǎng)頁 47,707,998 個(gè)，涉及到 46,669 個(gè) 中不重復(fù)的網(wǎng)頁為 22,382,623 個(gè)，平均每個(gè)站點(diǎn)有 不重復(fù)的網(wǎng)頁。 不斷增長形成了人類歷史上最大規(guī)模的分布式海量信息系統(tǒng)，如何幫助人們有效的利用這些信息就成為當(dāng)務(wù)之急，而首要的任務(wù)便是發(fā)現(xiàn)信息 人們迫切需要有效的 航工具，協(xié)助用戶找到所需的信息。信息檢索和 術(shù)二者結(jié)合，就催生了 的搜索引擎 (它代替原始的人工目錄系統(tǒng)，成為人們?cè)诨ケ本┐髮W(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 2 聯(lián)網(wǎng)上查找信息的有效工具，被認(rèn)為是在 除電子郵件、瀏覽器之外使用最多的服務(wù)。 提供良好的搜索引擎服務(wù)，是各類大型門戶網(wǎng)站的一個(gè)基本配置，而且對(duì)任何一個(gè)網(wǎng)站，提供對(duì)站內(nèi)網(wǎng)頁信息的搜索服務(wù)也是方便訪問者必不可少的部分。 許多商業(yè)化搜索引擎伴隨著 潮被開發(fā)出來，代表性的是 。 在提供對(duì) 30 億文檔 (其中包括 2,073,418,204 張網(wǎng)頁 )的訪問，利用高效的算法和龐大的機(jī)器資源，可以幫助用戶準(zhǔn)確地找到所需信息。 2001年調(diào)查報(bào)告顯示， 借純粹的搜索服務(wù)，在全球互聯(lián)網(wǎng)絡(luò)市場(chǎng)中取得 市場(chǎng)份額，名列第二，排名在雅虎之后，成為最成功的互聯(lián)網(wǎng)絡(luò)公司之一。與此同時(shí)，搜索引擎也成為各科研機(jī)構(gòu)和大學(xué)學(xué)術(shù)研究的熱點(diǎn)，每年的 術(shù)會(huì)議上和搜索引擎有關(guān)的研究題目都占很大比例， 是 學(xué)研究成果的商業(yè)化。如何有效的獲取互聯(lián)網(wǎng)上的信息，其重要性不言而喻。北京大學(xué)計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室研究開發(fā)的“天網(wǎng) ” (索引擎自 1997 年 10 月正式在 提供查詢服務(wù)以來，受到學(xué)術(shù)界和用戶的廣泛好評(píng)。我們一直致力于研制更高性能的搜索引擎，有效地開發(fā)利用 息資源。 在當(dāng)今的信息社會(huì)，往往信息不是不足，而是太多，從大量無關(guān)、冗余和紛亂的信息海洋中方便快捷地找到對(duì)用戶有價(jià)值的信息，就是信息檢索 (解決的問題。不僅僅是 息資源，信息化的發(fā)展使得社會(huì)中的每個(gè)組織都有大量公開和非公開的信息資源，它們是社會(huì)組織自身擁有的寶貴財(cái)富，如何有效利用這些財(cái)富就是必須面臨的問題。辦公自動(dòng)化系統(tǒng) (文檔數(shù)據(jù)庫 (以及數(shù)字圖書館 (數(shù)字化資源的建立和使用，都需要一個(gè)高效的信息檢索系統(tǒng)。信息檢索被認(rèn)為是解決信息過剩 (有效途徑，可以說是信息社會(huì)的一項(xiàng)核心技術(shù)。 人類的數(shù)字化信息不僅有文本 (還包括圖形、圖像、電影和音樂等多媒體信息，但是文字信息是最基本和最重要的形式，也比較容易被檢索和識(shí)別，相對(duì)其他多媒體信息有比較成熟的技術(shù)。本文 研究的對(duì)象限制在對(duì)文本數(shù)據(jù)庫的檢索，對(duì)于非純文本文檔通常要轉(zhuǎn)換成文本信息，這并不降低我們所研究問題的重要意義。以“天網(wǎng)”搜索引擎為背景，通過對(duì)信息檢索相關(guān)問題的研究、分析和實(shí)驗(yàn)，我們給出如何建立一個(gè)大規(guī)模文檔數(shù)據(jù)庫 (達(dá)到 )的信息檢索系統(tǒng)，它首先是分布式（ 和具備很高的可擴(kuò)展性（ 而且在并發(fā)查詢負(fù)載下滿足一定的性能要求 響應(yīng)時(shí)間 (系統(tǒng)吞吐量 (以及由于系統(tǒng)硬件所產(chǎn)生的種種限制。最后，我們?cè)噲D 分析在運(yùn)行“天網(wǎng)”這類大規(guī)模系統(tǒng)中具體遇到的管理難題，結(jié)合學(xué)術(shù)界和工業(yè)界在系統(tǒng)管理研究領(lǐng)域的最新成果和方向，討論了解決這個(gè)問題誘人的技術(shù)前景，并且對(duì)“天網(wǎng)”系統(tǒng)管理提出了自己試探性的研究建議。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 3 2 基本問題 信息檢索的目的是從大量的信息資源庫中找出用戶所需要的信息，所以它涉及兩個(gè)基本的方面。首先是如何表示、存儲(chǔ)和組織所擁有的海量信息資源，使它可以被迅速訪問；其次，我們?nèi)绾伪碚饔脩舻男畔⑿枨?，如何確定哪些信息是用戶所需要。前者是從計(jì)算機(jī)系統(tǒng)的角度看問題，后者是從人 用戶的角度看問題，二者決定了信息檢索的復(fù)雜性和研究的困難。廣泛使用數(shù)據(jù)庫 (術(shù)處理結(jié)構(gòu)化信息，操作的數(shù)據(jù)對(duì)象是固定的，用戶的每個(gè)操作執(zhí)行的結(jié)果是確定的；信息檢索處理的對(duì)象包羅萬象，可以是半結(jié)構(gòu)化、非結(jié)構(gòu)化的信息，這決定了它們的本質(zhì)區(qū)別。由于要處理任何可能的文檔，高質(zhì)量的信息檢索系統(tǒng)需要擁有對(duì)自然語言內(nèi)涵的理解能力，即獲取信息 (不只是數(shù)據(jù) (自然語言往往是模糊的和有隱含意義的，因此信息檢索對(duì)用戶查詢生成的結(jié)果是非精確的，往往也無法精確化。 因此，衡量一個(gè) 統(tǒng)，必須從兩個(gè)方面考慮：效率 (和效果(“效率”幾乎存在于所有計(jì)算機(jī)領(lǐng)域，任何算法都需要從時(shí)間和空間上考慮取舍，比如響應(yīng)時(shí)間、內(nèi)存和磁盤空間需求。對(duì)于聯(lián)機(jī)運(yùn)行的信息檢索系統(tǒng)，最重要的效率指標(biāo)就是系統(tǒng)的查詢響應(yīng)時(shí)間和系統(tǒng)的查詢吞吐量，沒有它，系統(tǒng)就不可能被用戶使用?！靶Ч敝笝z索返回結(jié)果集的準(zhǔn)確性，通常有兩個(gè)指標(biāo)：查準(zhǔn)率 (查全率 (查準(zhǔn)率定義為檢索結(jié)果集中與用戶查詢相關(guān)的文檔所占的百分比，查全率則是檢索結(jié)果集中的相關(guān)文檔占整個(gè)文檔集合中的相關(guān)文檔的百分比。由 于一個(gè)文檔是否和用戶查詢相關(guān)很難精確判定，實(shí)際運(yùn)行的系統(tǒng)并不大可能用這兩個(gè)指標(biāo)準(zhǔn)確評(píng)價(jià)，但是它對(duì)研究仍然有很大參考價(jià)值。這兩個(gè)指標(biāo)可以被形式定義如下：假設(shè)整個(gè)文檔集合是 D， D 的文檔數(shù)是 N=|D|，用戶查詢是 Q， Q 的返回文檔集合是 S(Q)，用函數(shù) R(x , y)表示文檔集合 x 中與查詢 y 相關(guān)的部分。則查詢 Q 的查準(zhǔn)率是 |R(S(Q),Q)|/|S(Q)|,查全率是 |R(S(Q),Q)|/|R(D,Q)|。 信息檢索的基礎(chǔ)是數(shù)據(jù)管理和自然語言處理 (接限制著信息檢索的方式和效果。用戶需求可以用自然語言表達(dá)出來，但是計(jì)算機(jī)系統(tǒng)還無法準(zhǔn)確的理解其內(nèi)涵。因此，用戶的意圖必須首先被翻譯成 統(tǒng)可以處理的形式。通常用戶查詢被表示成一系列關(guān)鍵字 (系統(tǒng)依據(jù)給出的關(guān)鍵字判定文檔是否和查詢相關(guān)。為了使得信息檢索有較好的效果， 統(tǒng)必須利用 技術(shù)，從語義上理解信息資源，評(píng)價(jià)它和用戶查詢的相關(guān)度 (并依據(jù)相關(guān)度的排序后將結(jié)果返回給用戶。 排文件 通過將用戶查詢和文檔資源分解成獨(dú)立的信息單元 (關(guān)鍵字 )，信息檢索的問題 被簡(jiǎn)化 以關(guān)鍵字為信息單位檢索。在數(shù)據(jù)的組織與管理上，對(duì)文檔按照分解后的關(guān)鍵字建立索引，可以加快查詢?cè)L問的速度。信息檢索中建索引的技術(shù)有三種：倒排文件(下標(biāo)數(shù)組 (簽名文件 ( 4比較后得出結(jié)論：北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 4 無論從時(shí)間和空間上，倒排文件都明顯優(yōu)于簽名文件。下標(biāo)數(shù)組空間需求太大，可是說是倒排文件的一種擴(kuò)充形式。倒排文件則靈活而高效，可以根據(jù)需要做不同的變通，成為最廣泛使用的索引方法。 倒排文件分兩部分：第一部分是由詞匯組成的索引 (第二部分是記錄對(duì)應(yīng)的每個(gè)詞的所有出現(xiàn)的文檔集合，稱為記錄文件 (每個(gè)詞的對(duì)應(yīng)部分稱為引文件的每個(gè)數(shù)據(jù)項(xiàng)是由詞（關(guān)鍵字）和指向記錄文件的指針組成。記錄文件的每個(gè)數(shù)據(jù)項(xiàng)記錄和一個(gè)詞對(duì)應(yīng)出現(xiàn)文檔的列表。設(shè) 示第 j 個(gè)單詞（關(guān)鍵字），示第 i 個(gè)文檔， 第 l 次出現(xiàn)表示為 ( 示此次出現(xiàn)的屬性 ,它除了包含出現(xiàn)的位置 l,在非純文本中還可以有其它被賦予的屬性，比如此次 可 以根據(jù)單詞出現(xiàn)處字體的大小計(jì)算。一個(gè)文檔按照單詞切分后，相同的單詞出現(xiàn)合并在一起，形成 ( , 表示 所有文檔的 ( )按照前面所述兩級(jí)結(jié)構(gòu)組織成根據(jù)單詞的索引后，倒排文件就建立起來了，如圖 示，單詞 應(yīng)的 ( a*)+( di+k , fi+k, a*)+ ， 示 出現(xiàn)次數(shù)，也是后面 a 的數(shù)量。這是倒排文件的全文本索引 (式 ,它記錄了每次出現(xiàn)的位置等信息，要占用較多的存儲(chǔ)空間。簡(jiǎn)化的形式是 ( 可以設(shè)定的權(quán)值函數(shù) f( , 更簡(jiǎn)單的方法是 于 現(xiàn)的頻率 n。 圖 2 . 1 倒排文件 長記錄 短記錄 索引文件 記錄文件 索引文件項(xiàng)格式： w o r d + p o i n t e r ( 指向記錄文件 ) 記錄文件項(xiàng)格式： ( ) + ( k, )+ 記錄項(xiàng)內(nèi)部按文檔號(hào)成增序排列 利用倒排文件，系統(tǒng)可以根據(jù)用戶提交查詢中的關(guān)鍵詞快速找到相關(guān)文檔。當(dāng)對(duì)大量文檔索引時(shí)，會(huì)出現(xiàn)一些關(guān)鍵字對(duì)應(yīng)的記錄項(xiàng)很大，嚴(yán)重 影響檢索的性能，后面我們會(huì)詳細(xì)討論。信息檢索中用戶的查詢有兩種基本的形式： I. 布爾 (詢，用邏輯操作 (接關(guān)鍵字。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 5 位置鄰近查詢 (要求關(guān)鍵字在相鄰的范圍內(nèi)。這對(duì)查詢?cè)~組(重要，可以提高檢索的準(zhǔn)確度，但是要求必須在索引中保留關(guān)鍵字的位置信息，增大了對(duì)磁盤空間的需求和查詢時(shí)的 I/O 操作。 倒排文件可以有效的支持這兩種查詢操作，由于每個(gè)關(guān)鍵詞的記錄項(xiàng)內(nèi)按文檔升序排列，只要順序掃描數(shù)據(jù)就能過濾不相關(guān)文檔，在內(nèi)存中的運(yùn)算很快。 為優(yōu)化查詢速度，可以不支持“或”，使每次操作的結(jié)果集始終不斷縮小。操作應(yīng)該從對(duì)應(yīng)文檔集合最少的關(guān)鍵詞開始，能降低算法復(fù)雜度。假設(shè)關(guān)鍵詞 應(yīng)的文檔記錄集合為 P(則兩個(gè)關(guān)鍵詞 作的復(fù)雜度是 P(, |P()。每次操作的結(jié)果會(huì)成為下次操作的輸入，影響后面操作的復(fù)雜度。在內(nèi)存允許下，使多個(gè)關(guān)鍵詞一次同時(shí)參與運(yùn)算，會(huì)大大提高執(zhí)行速度。 關(guān)度評(píng)價(jià) 信息檢索的一個(gè)核心算法是如何在用戶查詢 (文檔 (間做相關(guān)度評(píng)價(jià) (這直接關(guān)系到查詢“效果”。最基本的評(píng)價(jià)方法是利用向量空間模型 (概念 ,查詢和文檔都被認(rèn)為是由所有關(guān)鍵詞組成的 關(guān)度可以根據(jù)它們的向量計(jì)算出來。這種方法重要的改進(jìn)是注意到每個(gè)單詞在向量中應(yīng)該被賦予不同的權(quán)重參與計(jì)算相關(guān)度。自然語言中信息單位出現(xiàn)的頻度是不一樣的，甚至相差很大。信息論原理告訴我們：事物出現(xiàn)頻率越大，攜帶的信息量越小。 s 0表示為： (2這意味著語言的信息項(xiàng) 出現(xiàn)的頻率和它的權(quán)值成反比，出現(xiàn)頻率很高的單詞攜帶的意義非常少，比如英語中的“ ,漢語中的“的”，這些高頻詞在信息檢索中可能需要特殊處理。著名的 此得出，它可以被表示成： d lo g（ 2 N 是所有文檔的總數(shù)， 示單詞 t 的文檔頻率 (由于 單詞在語言中的統(tǒng)計(jì)特性，新文檔的加入對(duì)它影響很小，可以在一次計(jì)算出后作為單詞的屬性使用。單詞 文檔 的出現(xiàn)頻率表示為 ，那么它的復(fù)合權(quán)值是： = * (25提出了一個(gè)經(jīng)驗(yàn)公式，用文檔的長度修正復(fù)合權(quán)值，消除因文檔大小不同帶來的誤差。文檔向量 d 和查詢向量 q 的相關(guān)度比較通過兩個(gè)向量的夾角計(jì)算： c o s (2n 是向量的維數(shù)， 向量 q 和 d 的分量。結(jié)果越大，兩者的相關(guān)度就越高。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 6 我們考慮另一個(gè)語言統(tǒng)計(jì)特性 語言信息單位的 TF( 單詞在語言中出現(xiàn)的概率。設(shè)文檔 分后的單詞數(shù)是 DL(它可以作為文檔的長度。所有文檔切分后的單詞總數(shù) ： )( (2那么，單詞 TF(： 1) di t j,()( (2語言中單 詞的 TF(信息檢索的效率 (效果 (個(gè)方面都有很大影響。一種語言的詞匯可以分為兩部分 基本詞匯和專業(yè)詞匯，它們表現(xiàn)出不同的 TF(專業(yè)詞匯具有高的 較低 TF(可以區(qū)分不同領(lǐng)域的文檔，在信息檢索中更具意義。然而，語言中單個(gè)的“詞”的含義往往沒有足夠的含義，要用多個(gè)單詞組合成的詞組 (示更確切的意思 6。比如英語中的“ 屬于計(jì)算機(jī)中的專業(yè)詞匯， 切分以后的任何單字都不能表示這種含義。所以，詞組的 TF(能由它的各組成部分計(jì)算出來（例如相加得出）。如果對(duì)詞組索引匹配，檢索的準(zhǔn)確度將大大提高。 這種情況對(duì)漢語尤為重要。漢語的造詞功能很強(qiáng)，通過字的組合創(chuàng)造概念，英語更多的是造單詞。比如漢語中“激光”用“激”和“光”組合，在英語中則創(chuàng)造新詞“ 漢語中用詞組表達(dá)確切的含義，在單獨(dú)一個(gè)“字”的意義很弱。漢語文檔的索引可以是基于“字”或者基于“詞組”，基于“字”的索引會(huì)造成詞組的整體語義的丟失，比如查詢“華人”會(huì)檢索出“中華人民 共和國”。根據(jù)單個(gè)的字統(tǒng)計(jì)規(guī)律得出的 漢語中的有效性也大大降低。在英語檢索中，通常將高頻的“ a, 單詞視為“ 忽略詞），不會(huì)對(duì)檢索的效果有太大影響。漢語中，高頻詞（比如“的，中，在，大，有”等）可能參與組成詞組，如果這些字被忽略會(huì)嚴(yán)重影響某些查詢，例如“美的”（作為商品的商標(biāo)）和“王大中”（人名），“的”“大”“中”字是不能被忽略的?？傊捎跐h語和英語的差別，漢語傾向于使用基于詞組的索引，后面我們將詳細(xì)討論這對(duì)檢索效率的影響。 統(tǒng)運(yùn)行模型 一個(gè)完整 的現(xiàn)代信息檢索系統(tǒng)不僅要對(duì)用戶提供檢索 (能，還要同時(shí)支持瀏覽 (檔 7，如圖 示，這兩個(gè)功能現(xiàn)在都可以通過 術(shù)實(shí)現(xiàn)統(tǒng)一的用戶接口。檢索系統(tǒng)可以由用戶和文檔數(shù)據(jù)庫分成兩部分，和用戶交互的部分視為系統(tǒng)前端，數(shù)據(jù)庫相關(guān)部分視為系統(tǒng)后臺(tái)，它們通過中間的檢索和瀏覽兩大功能子系統(tǒng)連接起來。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 7 圖 2 . 2 用戶和檢索系統(tǒng)的交互（取自 7 ） R e t r i e v a l B r o w s i n g 數(shù)據(jù)庫 ( D a t a b a s e ) 后臺(tái)部分完成系統(tǒng)中文檔資源的維護(hù)功能，可以設(shè)想它是整個(gè)系統(tǒng)的起點(diǎn)，原始的文檔信息由此才能進(jìn)入系統(tǒng)內(nèi)部。在后臺(tái)操作員 的控制下，數(shù)據(jù)庫的文檔可能不斷變化，如文檔增加和刪除。根據(jù)具體的應(yīng)用不同，這種變化會(huì)定期或不定期導(dǎo)致檢索和瀏覽兩個(gè)子系統(tǒng)數(shù)據(jù)的更新，雖然大部分信息檢索系統(tǒng)并不需要這種變化被實(shí)時(shí)處理。檢索子系統(tǒng)中索引必須重建，根據(jù)需要可以采取不同的策略（動(dòng)態(tài)的、增量的、實(shí)時(shí)的、批量的），由于重建索引的代價(jià)巨大，必須盡可能減少它發(fā)生的頻度。 前端負(fù)責(zé)和用戶接口，它不僅向用戶提供信息（返回查詢結(jié)果，讓用戶瀏覽文檔），還可以通過和用戶交互獲得有用的信息 8。系統(tǒng)應(yīng)該可以全程跟蹤用戶使用系統(tǒng)的行為，比如在某段時(shí)間內(nèi)查詢的內(nèi)容（用戶 感興趣的主題和事物），瀏覽的文檔。這種信息包括用戶的個(gè)體行為和用戶的整體行為（統(tǒng)計(jì)結(jié)果），它可反饋回系統(tǒng)，改進(jìn)系統(tǒng)的檢索質(zhì)量，比如根據(jù)用戶的查詢?cè)~學(xué)習(xí)新詞，對(duì)用戶經(jīng)常查詢的關(guān)鍵字做緩存，甚至可以根據(jù)用戶瀏覽文檔的行為改變文檔的重要性，以此影響查詢結(jié)果的排序。我們對(duì)信息檢索系統(tǒng)中用戶的行為模型做出如下推斷： 1) 信息檢索系統(tǒng)中的個(gè)體活動(dòng)模型。每個(gè)用戶的活動(dòng)是帶有目的性的 查找某一方面的信息，檢索和瀏覽兩種行為交替進(jìn)行，相鄰的查詢相關(guān)度很大，后面的查詢可能是前面查詢的優(yōu)化（ 即： 查詢 瀏覽 優(yōu)化的查詢 。這里的瀏覽包括用戶閱讀查詢結(jié)果集合和閱讀文檔，它可能是一個(gè)很長的時(shí)間間隔，甚至用戶可能終止進(jìn)一步查詢，稱它為思考時(shí)間（ 2) 信息檢索系統(tǒng)中的用戶統(tǒng)計(jì)模型。單個(gè)用戶和系統(tǒng)的長時(shí)間交互中，檢索內(nèi)容呈現(xiàn)出個(gè)人的偏好，這與他的本身的工作、學(xué)習(xí)和興趣有關(guān)。大量用戶在某段時(shí)間的檢索內(nèi)容表現(xiàn)出相關(guān)性，同一主題被許多人感興趣，這就是所謂的“熱門檢索詞”。 由此可見，檢索系統(tǒng)和數(shù)據(jù)庫系統(tǒng)的用戶活動(dòng)的巨大差別，認(rèn)識(shí)到這一點(diǎn)很重要。根據(jù)這兩個(gè)推斷，我們可以采取一系列措施優(yōu)化檢索系統(tǒng) 的性能和質(zhì)量，分析系統(tǒng)真實(shí)的工作負(fù)載和用戶查詢的并發(fā)度。 檢索和瀏覽子系統(tǒng)對(duì)前端服務(wù)接口可以被抽象成如下的基本命令： 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 8 I. 查詢命令（ 輸入?yún)?shù)為用戶的查詢字符串和其它信息字段，返回查詢結(jié)果集合。 讀取文檔命令（ 輸入?yún)?shù)為文檔標(biāo)識(shí)，返回該文檔的內(nèi)容本身供用戶閱讀。 讀取摘要命令（ 輸入?yún)?shù)為文檔標(biāo)識(shí)，返回該文檔的摘要信息。 提供讀取文檔摘要命令，使用戶可以快速了解文檔的內(nèi)容。用戶在瀏覽查詢結(jié)果時(shí)，系統(tǒng)顯示文檔的摘要部分， 這是信息檢索系統(tǒng)必要的功能。 圖 2 . 3 信息檢索系統(tǒng)運(yùn)行模型 前端交互系統(tǒng) 文檔瀏覽系統(tǒng) 查詢處理 文檔數(shù)據(jù)庫 索引數(shù)據(jù)庫 數(shù)據(jù)管理系統(tǒng) 索引系統(tǒng) 查找 相關(guān)度評(píng)定 索引重建系統(tǒng) 后臺(tái)維護(hù)系統(tǒng) 用 戶 反 饋用戶反饋 檢索和瀏覽子系統(tǒng)對(duì)后臺(tái)的維護(hù)服務(wù)接口很簡(jiǎn)單，輸入?yún)?shù)是要被刪除的文檔和增加的文檔，它由后臺(tái)維護(hù)系統(tǒng)選擇時(shí)機(jī)調(diào)用。實(shí)現(xiàn)這部分功能的困難在于，如何降低索引重建的代價(jià)（對(duì)大規(guī)模數(shù)據(jù)重建索引需要執(zhí)行幾個(gè)小時(shí)）和在系統(tǒng)提供正常檢索服務(wù)的情況下執(zhí)行重建，同時(shí)要保持系統(tǒng)中索引、文檔和摘要三部分的一致性和進(jìn)行失敗恢復(fù)。如果將此功能當(dāng)作“事務(wù)”執(zhí)行，應(yīng)該歸為“長事務(wù)”（ 9，不能用傳統(tǒng)的事務(wù)很好描 述。 11描述在一定資源限制下大規(guī)模文本的索引創(chuàng)建問題， 1213北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 9 討論動(dòng)態(tài)和增量方式更新索引中的不同方法和會(huì)遇到的各種問題，雖然具體實(shí)現(xiàn)和底層的數(shù)據(jù)管理系統(tǒng)有很大關(guān)系，前面所指出的困難卻是普遍的，必須根據(jù)不同方面的要求做出一定取舍。 根據(jù)以上對(duì)各系統(tǒng)部分的分析，我們得出如圖 系統(tǒng)工作模型。數(shù)據(jù)管理系統(tǒng)在底層提供文檔及索引的存儲(chǔ)管理功能，前端交互系統(tǒng)和后臺(tái)維護(hù)系統(tǒng)是系統(tǒng)和外界交互的窗口，檢索、文檔瀏覽和索引重建是系統(tǒng)運(yùn)行的核心（關(guān)于索引重建的詳細(xì)流程并沒有在模型圖中表示出來）。這個(gè)系統(tǒng)模型，作為 一個(gè)通用框架，有助于我們?cè)诰唧w應(yīng)用中對(duì)問題的分析、理解和設(shè)計(jì)。 用案例 現(xiàn)代信息檢索最重要同時(shí)也是使用最廣泛的應(yīng)用毫無疑問當(dāng)屬 的信息檢索服務(wù)（ 搜索引擎，如前所述，這是和互聯(lián)網(wǎng)一起飛速發(fā)展的技術(shù)。搜索引擎的特殊性表現(xiàn)在： 要索引海量數(shù)據(jù)。平均每個(gè)網(wǎng)頁的大小是 10K 字節(jié)， 20 億網(wǎng)頁就是 20T 字節(jié)的數(shù)據(jù)，并且網(wǎng)頁的數(shù)量每天都在增加。 信息通過搜集系統(tǒng)從互聯(lián)網(wǎng)上獲取，由于網(wǎng)頁處于不斷更新狀態(tài)，如何建立高效的搜集器和動(dòng)態(tài)更新索引，就非常關(guān)鍵。 信息的 異構(gòu)性很強(qiáng)，沒有任何前提限定，有多種語言存在。 信息存在形式主要是 內(nèi)部包含豐富的格式信息，以超級(jí)鏈接相互引用，這決定了它有獨(dú)特的相關(guān)度評(píng)價(jià)（ 術(shù)。 圖 14給出的一個(gè)搜索引擎通用結(jié)構(gòu)，相對(duì)一般的信息檢索系統(tǒng)增加了從 搜集網(wǎng)頁的功能，更大的差別在于系統(tǒng)內(nèi)部對(duì)網(wǎng)頁的分析技術(shù)，它對(duì)提高搜索引擎質(zhì)量至關(guān)重要。 的網(wǎng)頁通常比較短小，缺乏足夠的自我描述信息，而它們之間的相互鏈接正好在全局對(duì)網(wǎng)頁作了補(bǔ)充說明。超鏈分析（ 以挖 掘 的隱含信息，改進(jìn)查詢的準(zhǔn)確度，比較典型的技術(shù)是 14有較為詳盡的描述。 具體的索引數(shù)據(jù)結(jié)構(gòu)和系統(tǒng)實(shí)現(xiàn)，可參閱 15，它是 一個(gè)原型系統(tǒng)。搜索引擎在擴(kuò)大數(shù)據(jù)規(guī)模的同時(shí)，必須滿足互聯(lián)網(wǎng)上大量用戶查詢產(chǎn)生的系統(tǒng)負(fù)載，所以“效率”也是商業(yè)搜索引擎系統(tǒng)成敗的關(guān)鍵。 信息檢索另一個(gè)重要的應(yīng)用是“數(shù)字圖書館”（ 它利用數(shù)字化技術(shù)擴(kuò)充和增強(qiáng)傳統(tǒng)的圖書館業(yè)務(wù)。所以，數(shù)字圖書館不單是一個(gè)信息訪問的工具，而是要支持各種數(shù)字圖書業(yè)務(wù)的 環(huán)境。和 息搜索不同，圖書館的信息是要經(jīng)過“整理”后的，比如目錄分類。 16提出一個(gè)被廣泛接受的數(shù)字圖書館構(gòu)架，它包括用戶界面（ 文檔庫（ , 句柄系統(tǒng)（ 查找系統(tǒng)（ ,如圖 示。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 10 圖 2 . 4 搜索引擎的通用結(jié)構(gòu)（摘自 1 4 ） 圖 2 . 5 數(shù)字圖書館的主要構(gòu)成（摘自 1 6 ） 用戶界面包括兩個(gè)部分，一個(gè)是對(duì)圖書館的用戶，一個(gè)是對(duì)圖書管理員和管理信息資源 (系統(tǒng)管理員。每個(gè)界面都是由兩部分組成 標(biāo)準(zhǔn)的瀏覽器（ 京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 11 和客戶端服務(wù)系統(tǒng)（ 后者是前者與系統(tǒng)交互的中介。文檔庫管理和存儲(chǔ)數(shù)字化對(duì)象， 議（ 是它的統(tǒng)一訪問接口。 來識(shí)別各種資源的全局標(biāo)識(shí)符，可以很長時(shí)間存在，是資源的元數(shù)據(jù)（ 查找系統(tǒng)發(fā)現(xiàn)文檔庫中的信息，屬于很典型的信息檢索。從計(jì)算機(jī)系統(tǒng)看，這個(gè)結(jié)構(gòu)和前面的信息檢索模型本質(zhì)相同，現(xiàn)實(shí)中，數(shù)字圖書館還 涉及到法律的問題。 以上我們較為詳細(xì)介紹了信息檢索系統(tǒng)的原理和應(yīng)用實(shí)例，顯示出它的具體應(yīng)用實(shí)際上是由多個(gè)部分相互協(xié)作組成的有機(jī)整體，復(fù)雜的結(jié)構(gòu)和運(yùn)行環(huán)境決定整個(gè)系統(tǒng)必須以分布式實(shí)現(xiàn)，搜索引擎和數(shù)字圖書館都證明了這一點(diǎn)。系統(tǒng)數(shù)據(jù)規(guī)模的不斷擴(kuò)大，使得“效率”始終是必須考慮的問題。我們開發(fā)的新一代“天網(wǎng)”搜索引擎，要求規(guī)模從原來的索引幾百萬網(wǎng)頁擴(kuò)大到可以支持上億篇網(wǎng)頁，同時(shí)必須保證良好的性能，為此，搜集系統(tǒng)和檢索系統(tǒng)都分別被分布式化。下面根據(jù)我們?cè)凇疤炀W(wǎng)”系統(tǒng)開發(fā)中的實(shí)踐，討論實(shí)現(xiàn)分布式檢索系統(tǒng)中如何解決規(guī)模和 效率這兩個(gè)問題，其方法對(duì)于任何信息檢索應(yīng)用都有普遍意義。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 12 3 單機(jī)系統(tǒng)的檢索性能分析 單機(jī)系統(tǒng)的檢索性能是分布式系統(tǒng)的基礎(chǔ)，為了預(yù)測(cè)在分布式環(huán)境下的系統(tǒng)整體性能，必須確定單機(jī)系統(tǒng)中數(shù)據(jù)規(guī)模和性能的相互關(guān)系。我們的問題是利用當(dāng)前水平計(jì)算能力的商用機(jī)器（ ，工作站），在一定性能（ 求下，可能支持的數(shù)據(jù)規(guī)模（ 并且討論系統(tǒng)的瓶頸和提高系統(tǒng)性能的各種方法。 用計(jì)算機(jī)性能分析 由于集成電路和計(jì)算機(jī)體系結(jié)構(gòu)等方面的發(fā)展，計(jì)算機(jī)的性能獲 得長足的進(jìn)步。但是，計(jì)算機(jī)系統(tǒng)不同組成部分之間的增長是不均衡的，使得系統(tǒng)在實(shí)際應(yīng)用中性能下降。在過去二十年中， 性能幾乎增長了 10， 000 倍；單機(jī)系統(tǒng)的內(nèi)存容量也從少于 1B 的量級(jí) ,大約增長了 1， 000 倍，存取時(shí)間達(dá)到 ；磁盤容量也從幾百 加到現(xiàn)在的 30是， I/O 的訪問速度卻僅提高了不到一百倍（從 00在應(yīng)用領(lǐng)域，大量信息處理的快速增長和多媒體信息普遍應(yīng)用，增加了對(duì)數(shù)據(jù)存取的需求，使 I/O 系統(tǒng)和外部存儲(chǔ)設(shè)備訪問愈發(fā)成為計(jì)算 機(jī)系統(tǒng)的瓶頸。信息檢索作為一個(gè)數(shù)據(jù)密集應(yīng)用（ I/O 乃是系統(tǒng)性能的關(guān)鍵，在 三個(gè)因素中，我們重點(diǎn)討論磁盤 I/O 對(duì)系統(tǒng)產(chǎn)生的限制。 表 族樹 us us 5 MB/s 0 10 MB/s 0 6 20 MB/s 0 20 MB/s 0 6 40 MB/s 0 6 80 MB/s 0 6 160 MB/s ， 相對(duì)于 面用的 線 ( 較高的速度，可以接多個(gè)設(shè)備，在 I/O 高負(fù)載下消耗 間少（ 耗 間 5%,0。其各種標(biāo)準(zhǔn)的性能如表 示，從最初的 5MB/s）到即將出現(xiàn)的 320MB/s） ,性能提升很快。實(shí)際可用的帶寬要小于標(biāo)準(zhǔn)值，比如現(xiàn)在用的 際帶寬是 150MB/s。 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 13 磁盤容量的雖然不斷擴(kuò)大，訪問速度卻改進(jìn)很少，這由磁盤本身的特性決定（包含機(jī)械部分）。磁盤包含度多個(gè)盤片（ 1盤片表面分成多個(gè)磁道（ 所有盤面在同一垂直位置的磁道組成柱面（ 每個(gè)磁道被分成固定大小的扇區(qū)（ ,它是磁盤最小的尋址單位，又稱作塊（ 磁盤訪問（讀、寫）某個(gè)塊，必須首先將磁頭轉(zhuǎn)到所在磁道（尋道時(shí)間， 然后等待所在扇區(qū)到磁頭下面（旋轉(zhuǎn)延遲，最后是讀取扇區(qū)上的數(shù)據(jù)塊（傳輸時(shí)間， ,總的磁盤訪問時(shí)間還要加上磁盤控制器執(zhí)行 I/O 的代價(jià)，稱為控制器時(shí)間（ 尋道時(shí)間取決于當(dāng)前磁頭位置和目的磁道的距離，通常取平均值表示性能，現(xiàn)在高性能磁盤的平均尋道時(shí)間大約在 10下，是 I/O 訪問延遲的主要部分。旋轉(zhuǎn)延遲取決于磁盤轉(zhuǎn)速，10000磁盤平均旋轉(zhuǎn)延遲（轉(zhuǎn)半圈）是 3據(jù)的傳輸時(shí)間是數(shù)據(jù)大小除以內(nèi)部傳輸速率，較高性能磁盤的內(nèi)部傳輸速率可以達(dá)到 20s。表 一些磁盤的性能數(shù)據(jù)， 表示磁盤每秒鐘可以執(zhí)行的隨機(jī) I/O 操作，它可以根據(jù)平均訪問時(shí)間計(jì)算得到?？偟膩碚f，磁盤的響應(yīng)時(shí)間在毫秒級(jí)以上（平均 10每秒鐘可 以完成的I/O 操作也很有限（ 均是 100，即達(dá)到平均每秒種 100 次 I/O 訪問）。而且，具體的性能受數(shù)據(jù)存儲(chǔ)的位置和應(yīng)用訪問的模式影響，不良的數(shù)據(jù)存儲(chǔ)管理將使性能嚴(yán)重下降。 表 一些磁盤的性能數(shù)據(jù) MB/s) 6 36 0,000 119 15 0,000 715 5,000 83 0,000 116 2655 ,200 9前單個(gè)磁盤的平均數(shù)據(jù)傳輸速率 僅 25MB/s，不能完全利用 線的全部帶寬，進(jìn)一步提高性能的方法之一是采用并行磁盤技術(shù) N 個(gè)磁盤組成的陣列可以使數(shù)據(jù)傳輸速率獲得接近 N 倍的提升，并且可以提高 I/O 請(qǐng)求的響應(yīng)時(shí)間（同時(shí)也增加了 這是以增加系統(tǒng)硬件成本為代價(jià)的。為解決 I/O 產(chǎn)生的瓶頸，工業(yè)界開發(fā)出了更加先進(jìn)的外部存儲(chǔ)技術(shù)，如光纖通道（ 存儲(chǔ)區(qū)域網(wǎng)絡(luò)（ （的 15 就是一種 光纖通道，其性能指標(biāo)要高出普通硬盤很多）。可以認(rèn)為，隨著磁盤的平均數(shù) 據(jù)傳輸速率從 10MB/s 到 100MB/s 甚至更高的提升，成本北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 14 也會(huì)隨之上升。應(yīng)用中要根據(jù)實(shí)際需求，在成本和性能之間做出選擇。 引數(shù)據(jù)管理 存儲(chǔ)設(shè)備性能可否充分利用，還要受操作系統(tǒng)、應(yīng)用程序（存儲(chǔ)管理、緩存管理）的影響。 應(yīng)用程序要調(diào)用操作系統(tǒng)提供的 I/O 服務(wù)功能 ,它有幾種不同的方式，如圖 文件系統(tǒng)的調(diào)用接口或 I/O 庫函數(shù)，優(yōu)點(diǎn)是可以利用文件系統(tǒng)的緩存和預(yù)讀機(jī)制，缺點(diǎn)是數(shù)據(jù)要經(jīng)過多次拷貝。原始 I/O 不通過文件系統(tǒng)，直接讀寫磁盤。一些操作系統(tǒng)提供直接 I/O（ ），它在文件系統(tǒng)支持 下實(shí)現(xiàn)和原始 I/O 類似的功能，沒有系統(tǒng)緩存、多次拷貝等開銷。另一種減少 I/O 開銷的方法是用文件映射（ 統(tǒng)調(diào)用），將數(shù)據(jù)映射到內(nèi)存空間，直接讀寫內(nèi)存，不存在多次拷貝的問題。文件映射的缺點(diǎn)是失去了 I/O 操作的原子性語義，在并發(fā)讀寫中要實(shí)現(xiàn)互斥操作。 圖 3 . 1 L I N U X 操作系統(tǒng)的 I / O I / O 類型： 原始（ R a w ） I / O ，在數(shù)據(jù)庫中使用。 其它是通過內(nèi)存映像訪問數(shù)據(jù)。 U s e r U s e r b u f f e r S y s t e m c a c h e M e m o r y m a p p e d D e v i c e 1 2 3 4 5 1 不通過文件系統(tǒng)的原始 I/O 。 2 用 r e a d / w r i t e 系統(tǒng)調(diào)用的 I/O 。 3 用 f r e a d / f w r i t e 標(biāo)準(zhǔn)庫函數(shù)調(diào)用的 I/O 。 4 文件系統(tǒng)的元數(shù)據(jù)。 5 文件系統(tǒng)元數(shù)據(jù)更 新。 使用文件系統(tǒng)的另一個(gè)缺點(diǎn)是文件系統(tǒng)的數(shù)據(jù)組織往往不能提供應(yīng)用程序最好的性能。 文件空間分配是直接索引、一級(jí)索引、二級(jí)索引和三級(jí)索引的組合，最壞情況下訪問數(shù)據(jù)要讀四次塊（大文件）。文件系統(tǒng)一 般的預(yù)讀策略是提前讀，數(shù)據(jù)塊緩存用 法，這些都是對(duì)應(yīng)用程序透明的，不能做到應(yīng)用級(jí)優(yōu)化（ 數(shù)據(jù)庫一般繞過文件系統(tǒng)，使用自己的存儲(chǔ)管理和緩存，優(yōu)化應(yīng)用的性能。 倒排文件本質(zhì)上是關(guān)鍵字到它對(duì)應(yīng)項(xiàng)的索引，一般地，關(guān)鍵字通過字典（ 找，轉(zhuǎn)換成整數(shù)作為關(guān)鍵字的標(biāo)識(shí)（ ,索引管理實(shí)現(xiàn)從 對(duì)應(yīng)項(xiàng)的訪北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 15 問。在“天網(wǎng)”中，用兩級(jí)文件模擬這種結(jié)構(gòu)，如圖 示的，第一級(jí)文件中每個(gè)結(jié)構(gòu)項(xiàng)是 ( 向二級(jí)文件的指針（ 應(yīng)項(xiàng)的開始） , 應(yīng)項(xiàng)大小。每次建索引，關(guān)鍵字的 是重新生成，是連續(xù)的整數(shù)，數(shù)量大約 200 萬個(gè)。由于一級(jí)文件并不大（可以讀入內(nèi)存），每次只讀取幾個(gè)字節(jié)，其代價(jià)可以不考慮。二級(jí)文件中，一些關(guān)鍵詞的對(duì)應(yīng)項(xiàng)很大，才是影響倒排表查詢性能的關(guān)鍵。用文件實(shí)現(xiàn)的缺點(diǎn)如前所述，好處是簡(jiǎn)單易于實(shí)現(xiàn)。 如果系統(tǒng)維護(hù)統(tǒng)一的字典，關(guān)鍵字和標(biāo)識(shí)（ 映射不變，每次創(chuàng)建倒排文件產(chǎn)生的 不是連續(xù)的，二級(jí)索引將不再適合，更一般的方法是用 B+樹 組織倒排文件。 17討論在關(guān)系數(shù)據(jù)庫之上實(shí)現(xiàn)倒排文件，利用成熟產(chǎn)品提供的高性能數(shù)據(jù)管理，缺點(diǎn)是增加了不必要的開銷，比如 詢接口。面向?qū)ο蟮母拍罡芎?jiǎn)潔地描述倒排文件的結(jié)構(gòu)，采用面向?qū)ο髷?shù)據(jù)庫系統(tǒng)（ 更好的選擇。 1819用持久對(duì)象存儲(chǔ)（ 理倒排文件， 但提供基于對(duì)象的數(shù)據(jù)緩存和良好的磁盤空間分配策略，還可以用它高度的可擴(kuò)展性，根據(jù)數(shù)據(jù)的特性定制存儲(chǔ)。 021是商業(yè)上最成功的面向?qū)ο髷?shù)據(jù) 庫 系統(tǒng)（ 之一，它用內(nèi)存映射技術(shù)實(shí)現(xiàn) 持久對(duì)象存儲(chǔ)，和程序語言（ C,C+,全集成，既有程序設(shè)計(jì)語言的靈活，又可以高效的存儲(chǔ)數(shù)據(jù)，是另一個(gè)很好的索引管理工具。 嵌入式數(shù)據(jù)庫系統(tǒng) B） 22,是一個(gè)開放源代碼產(chǎn)品，它提供簡(jiǎn)單高效的功能（三種訪問方法 B+，實(shí)現(xiàn) 存取，這已完全能滿足索引管理的需求。 B 以庫的形式存在，在多種程序設(shè)計(jì)語言（ C, C+, 中支持顯式的數(shù)據(jù)庫訪問編程接口。 23討論了在 目中用B 管理倒排文件的具體實(shí)現(xiàn)細(xì)節(jié)，由于它的開放源碼特點(diǎn)，也是一個(gè)不錯(cuò)的選擇。 由于前面所述的磁盤結(jié)構(gòu)特點(diǎn)，提高訪問效率的存儲(chǔ)分配策略可歸結(jié)為：將同時(shí)訪問的數(shù)據(jù)塊分配在磁盤相鄰的扇區(qū)，稱“簇集”（ 如果系統(tǒng)存在多個(gè)磁盤（ ,可以將同時(shí)訪問的數(shù)據(jù)塊分配在不同的物理磁盤上，稱“解簇” （ 在查詢處理時(shí)，倒排文件中 應(yīng)的 被順序掃描（ ,過濾后得到滿足條件的文檔集合，這種順序訪問模式要求每個(gè) 好存放在連續(xù)的扇區(qū)， 面向?qū)ο髷?shù)據(jù)庫 系統(tǒng)通?？梢蕴峁┐朔N能力（比如 用戶可以定制對(duì)象的存儲(chǔ)分配管理 ）。 倒排文件中 度差別很大，為提高效率可以區(qū)別對(duì)待。高頻詞（ 度通常 1上（隨著文檔數(shù)據(jù)庫規(guī)模增大，它會(huì)快速增長），稱作“ 如果對(duì)它作順序訪問，從磁盤讀入內(nèi)存會(huì)耗費(fèi)很長時(shí)間，同時(shí)占用系統(tǒng)大量的 I/O 帶寬，從而降低整個(gè)系統(tǒng)的吞吐量。解決的方法是將對(duì) 順序訪問變成隨機(jī)訪問（ 24， 25, 按照“文檔號(hào)”分割成長度較小的數(shù)據(jù)塊，在“ “ 作時(shí)可以有選擇地訪問部分?jǐn)?shù)據(jù)，不可能相關(guān)的文檔所在數(shù)據(jù)塊被“跳過”（ 它增加了按照“文檔號(hào)”索引數(shù)據(jù)，以空間換取時(shí) 間。假設(shè)關(guān)鍵詞 應(yīng)的 ( |P(表示 P(文檔的數(shù)量，兩個(gè)詞 “ “ 北京大學(xué)碩士學(xué)位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 16 |P( 遠(yuǎn)遠(yuǎn)小于 |P( ，讀 P(內(nèi)存中，程序只需根據(jù) P(文檔號(hào)，讀取 P(包含該文檔的數(shù)據(jù)塊。算法的效率提高取決于 |P( 要遠(yuǎn)遠(yuǎn)小于 |P(，即至少有一個(gè)運(yùn)算項(xiàng)的 高（關(guān)鍵詞只在以一小部分文檔中出現(xiàn)），這對(duì)多個(gè)運(yùn)算項(xiàng)的同時(shí)操作一樣適用。 自索引倒排文件（ 24表明， 以大幅度降低查詢所用時(shí)間。然而，此算法要求 以被定制存儲(chǔ)和組織，必須使用 面向?qū)ο髷?shù)據(jù)庫 系統(tǒng)管理倒排文件，或者從頭開發(fā)全新的索引管理系統(tǒng)。 另一個(gè)改善性能的技術(shù)是緩沖區(qū)管理，利用文件系統(tǒng)的緩存往往不能得到最佳的性能。前面得出的個(gè)體用戶行為模型表明，在一段時(shí)間內(nèi)相同的關(guān)鍵詞可能被同一個(gè)用戶反復(fù)查詢。根據(jù) 順序訪問模式，可以采用基于對(duì)象 的緩存，對(duì)象持久存儲(chǔ)中的雙向緩沖區(qū) 27將對(duì)象和分頁緩存結(jié)合起來，是一種更佳的策略。在信息檢索中，低頻詞的 度小于一頁，被檢索的頻度也很低（很少在短時(shí)間被不同的用戶查詢），應(yīng)該將多個(gè)小對(duì)象合并緩存在同一頁中。對(duì)很高頻的單詞，由于它對(duì)查詢準(zhǔn)確度的提高很有限（有些系統(tǒng)將它們作為 略，不建索引），緩存整個(gè)它的 占用大量內(nèi)存，少量的高頻詞就可以耗盡所有的內(nèi)存 ，所以緩存高頻詞的 得