千萬級ＦＴＰ搜索引擎數據庫索引的設計方法探討

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

關鍵詞：FTP 搜索引擎 數據庫 索引

引言

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

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

1. FTP搜索引擎的框架結構

Sparrow Search采用的是獨立型搜索引擎，即擁有自己的索引數據庫，檢索在本地數據庫中進行，并根據數據庫的內容提供相關信息或站點鏈接。圖1是FTP搜索引擎的框架結構圖。

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

2.數據庫索引數據庫的設計

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

2.1 建立原始索引

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

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

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

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

2.2 索引的壓縮存儲

增加索引的字符數量會使索引文件的大小成比例增加，即便是只對文件名本身索引，海量的原始信息量仍對索引文件的存儲空間構成了極大的威脅。經過實驗，在不壓縮并對文件相鄰外層目錄編入索引的情況下，1千萬條記錄所生成的索引文件的大小超過600MB。考慮在數據庫中的數據有這樣的規律：大量名字相仿的文件記錄會集中在一起，因為它們都被放在服務器的同一個目錄下，這意味著文件名中字符或漢字會重復編入索引。

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

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

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

2.3 索引的整合存儲

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

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

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

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

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

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

3. 緩沖區技術

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

4. 結束語

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

參考文獻：

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

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

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

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