千萬級ＦＴＰ搜索引擎數(shù)據(jù)庫索引的設(shè)計方法探討

摘 要： 本文介紹了基于LINUX操作系統(tǒng)的千萬級FTP搜索引擎(Sparrow Search)的框架結(jié)構(gòu)，著重探討了數(shù)據(jù)庫索引的設(shè)計方法，針對提高索引檢索效率和壓縮比率的問題，本文提出了具體方案并給出了實驗結(jié)果。

關(guān)鍵詞：FTP 搜索引擎 數(shù)據(jù)庫 索引

引言

FTP搜索引擎是對因特網(wǎng)上FTP服務(wù)器的信息資源進行檢索和管理的一類檢索系統(tǒng)機制［１］，數(shù)據(jù)的檢索過程并不需要搜索整個因特網(wǎng)，只需處理預(yù)先整理好的FTP目錄信息數(shù)據(jù)庫。FTP搜索引擎的功能是搜集匿名FTP服務(wù)器提供的目錄列表，對用戶提供文件信息的查詢服務(wù)［２］。與相對眾多的WWW搜索引擎相比，功能強大的FTP搜索器并不常見，由此限制了人們對具有大量信息與資源的FTP站點的訪問。實現(xiàn)一個高速、海量、功能強大而又基于Web的FTP搜索引擎將為網(wǎng)絡(luò)用戶提供極大方便［３］。

根據(jù)搜索引擎的工作原理，可將搜索引擎的實現(xiàn)過程分為三步：在因特網(wǎng)上抓取FTP目錄信息 → 建立索引數(shù)據(jù)庫→在索引數(shù)據(jù)庫中搜索排序［４］。本文著重討論建立索引數(shù)據(jù)庫過程中索引的設(shè)計與實現(xiàn)方案。

1. FTP搜索引擎的框架結(jié)構(gòu)

Sparrow Search采用的是獨立型搜索引擎，即擁有自己的索引數(shù)據(jù)庫，檢索在本地數(shù)據(jù)庫中進行，并根據(jù)數(shù)據(jù)庫的內(nèi)容提供相關(guān)信息或站點鏈接。圖1是FTP搜索引擎的框架結(jié)構(gòu)圖。

用戶在客戶端使用網(wǎng)頁瀏覽器進行數(shù)據(jù)查詢，當(dāng)用戶鍵入查找關(guān)鍵字并提交時，Web服務(wù)器通過調(diào)用CGI程序在索引數(shù)據(jù)庫中進行搜索。數(shù)據(jù)采集機器人(spider)自動提取各個FTP站點的文件和目錄信息并按照一定格式和策略進行存儲，從而生成索引數(shù)據(jù)庫。

2.數(shù)據(jù)庫索引數(shù)據(jù)庫的設(shè)計

FTP搜索引擎數(shù)據(jù)庫索引設(shè)計由三部分組成：原始索引、壓縮索引、整合索引。

2.1 建立原始索引

建立索引的方法采用倒排表技術(shù)，即數(shù)據(jù)庫的索引被設(shè)計成基于單字符(漢字)的倒排表的形式，字符種類的個數(shù)決定有多少倒排表文件。每個倒排表文件以某個字符(英文字母或漢字)命名，保存的是該字符(英文字母或漢字) 在數(shù)據(jù)庫中每次出現(xiàn)的位置信息，由于有些字符無法在操作系統(tǒng)中作為文件名，如星號、冒號等，Sparrow Search中規(guī)定了只有漢字和特定字符，如:0－9、a－z、A－Z可以被索引。雖然在支持中文的LINUX 操作系統(tǒng)上漢字可以作為文件名，但考慮到兼容性問題，沒有直接用漢字作為文件名，而是把漢字的16位編碼轉(zhuǎn)換成為4位16進制無符號數(shù)來作為文件名。這樣在不支持漢字的LINUX 操作系統(tǒng)上也能夠處理漢字的索引問題。

索引結(jié)構(gòu)如圖2所示。每條索引由32位(4字節(jié))構(gòu)成，其中高24位用于表示該字符所在的記錄編號ID，低7位用于表示該字符在記錄內(nèi)的位置偏移量，中間一位暫時保留，以備后用。

當(dāng)用戶檢索FTP目錄信息時，希望得到一類文件，而不是一種文件。如用戶希望查找所有圖像文件，需要用戶輸入圖像文件的擴展名并不方便，因此可在服務(wù)端對文件進行分類，將FTP中的文件名分為為圖像、視頻、音樂、文檔、程序等，將其分別進行索引，有利于提高檢索效率。

大多數(shù)FTP服務(wù)器上文件名（不含擴展名）或目錄名會采用過于簡單的字符表示，但用戶檢索時無法從信息量較小的字符中檢索希望得到的信息。如目錄結(jié)構(gòu)/office2000/a/b.exe，僅僅對a和b.exe做索引沒有太大意義。在Sparrow Search中，除了文件名本身以外，對其若干外層目錄名也編上索引。但增加索引量又會使數(shù)據(jù)庫索引文件劇烈增大。經(jīng)過實驗，每增加一層目錄名的索引量，索引文件的大小會增加60%甚至更多。Sparrow Searc采用的方法是：一旦發(fā)現(xiàn)文件名的長度過短就將其外層目錄名編入索引。同樣，若外層目錄名仍過短，再將其外層目錄名編入索引，……極端情況下，對文件的全路徑編制索引。

2.2 索引的壓縮存儲

增加索引的字符數(shù)量會使索引文件的大小成比例增加，即便是只對文件名本身索引，海量的原始信息量仍對索引文件的存儲空間構(gòu)成了極大的威脅。經(jīng)過實驗，在不壓縮并對文件相鄰?fù)鈱幽夸浘幦胨饕那闆r下，1千萬條記錄所生成的索引文件的大小超過600MB。考慮在數(shù)據(jù)庫中的數(shù)據(jù)有這樣的規(guī)律：大量名字相仿的文件記錄會集中在一起，因為它們都被放在服務(wù)器的同一個目錄下，這意味著文件名中字符或漢字會重復(fù)編入索引。

對比原有索引結(jié)構(gòu)，可以將高16位相同的索引編在一起，用2個字節(jié)保存，稱為基底Base；再用2字節(jié)保存高16位相同的索引的個數(shù)，即偏移總數(shù)N；用2個字節(jié)保存原索引結(jié)構(gòu)中的后兩個字節(jié)的內(nèi)容，即偏移。索引壓縮方法示例如圖3所示。

假設(shè)用四個數(shù)字表示索引的四個字節(jié)，則存儲圖3左邊的索引信息需要32個字節(jié)（8*4Bytes=32Bytes）；用上述壓縮算法進行存儲則只需要24個字節(jié)。

從例中不難看出，當(dāng)索引文件越大，壓縮比就越高。當(dāng)數(shù)據(jù)庫規(guī)模超過萬條記錄時，壓縮比一般就能維持在50%以上，在測試中最高達(dá)到60%。這樣存儲一千萬條索引記錄需要約300MB空間。

2.3 索引的整合存儲

出于對檢索性能的考慮，把眾多的倒排表索引文件整合成一個大的索引文件，再將這個文件放入內(nèi)存中，這個過程就是索引的整合存儲。

整合索引需要解決兩個問題：

（1）怎樣在整合后的文件中定位某個倒排表文件。針對該問題可以另外設(shè)置一張表格，稱為索引表頭，索引表頭中指明了每個字符或漢字對應(yīng)的索引文件大小和在整合后的文件中的起始位置即偏移。

（2）如何解決索引表頭的存儲問題。有三種方法：其一是存放在整合后的索引文件頭部，其二是存放在整合后的索引文件尾部，第三是另外單獨存放在一個文件中。Sparrow Search采用了第三種方法。

Sparrow Search索引文件的表頭實際上是一個數(shù)組，長度為64K，每個元素由8個字節(jié)組成(即兩個無符號長整型數(shù))，前4個字節(jié)指出該元素代表的索引文件的大小，后4個字節(jié)指出其偏移量。所以索引表頭永遠(yuǎn)是512KB大小。

索引字符或漢字編碼(最高16位)被用做下標(biāo)在數(shù)組中索引定位，即把數(shù)組當(dāng)成一個無沖突的哈希（HASH）表。雖然所有字符或漢字不會都被索引并且會造成存儲空間浪費，但卻可極大地提高索引訪問速度。

3. 緩沖區(qū)技術(shù)

數(shù)據(jù)庫索引生成器包括索引生成、壓縮、整合三部分，程序?qū)τ诖疟P操作全部采用“預(yù)讀取+延遲寫”的策略，即在程序中開辟讀、寫緩沖區(qū)。緩沖區(qū)一旦發(fā)生欠載，立即讀盤；發(fā)生過載，立即寫盤。這使得整個數(shù)據(jù)庫的建庫、壓縮及整合過程的速度比直接寫盤的策略提高了幾十倍：在未采用緩沖區(qū)技術(shù)以前，處理7萬條記錄就要耗費1分鐘20秒以上，而采用緩沖區(qū)技術(shù)以后，7萬條記錄的處理時間小于3秒鐘。

4. 結(jié)束語

本文介紹了Sparrow Search引擎數(shù)據(jù)庫索引的生成方法，討論了遇到的各種問題，并給出了解決方法和實現(xiàn)方式。Sparrow Search已在我校校園網(wǎng)上使用，搜索速度快，準(zhǔn)確率較高，范圍較廣，既方便了校園中廣大用戶的檢索，又節(jié)省了費用，是廣大師生較喜愛的一種引擎。

參考文獻(xiàn)：

［１］印鑒，鄒勝.一種分布式搜索引擎設(shè)計.計算機科學(xué)，2001，28(10):74-77.

［２］陳華，王繼民， 韓近強等.互聯(lián)網(wǎng)上FTP文件的分布特征及啟示.計算機工程與應(yīng)用，2004，1:129-137.

［３］陳華，羅昶，王建勇等.基于Web的百萬級FTP搜索引擎的設(shè)計與實現(xiàn). 計算機應(yīng)用，2000，20(9):68-71.

［４］沈賀丹，潘亞楠，邵良杉.關(guān)于搜索引擎的研究綜述.計算機技術(shù)與發(fā)展， 2006，16(4):147-149，152.