[發明專利]文件數據庫多級索引技術

無效

• 申請號: 200910015103.4
• 申請日: 2009-05-07
• 公開（公告）號: CN101551807A
• 公開（公告）日: 2009-10-07
• 發明（設計）人: 王進;劉毅楓;石磊;黃三偉;劉宗福;劉春
• 申請（專利權）人: 山東中創軟件商用中間件股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 濟南舜源專利事務所有限公司
• 代理人: 苗 峻

技術領域

本發明涉及一種文件數據庫多級索引技術，即InforGuard水印模塊采用的水印存取機制。

背景技術

在功能上，InforGuard為驗證網頁文件的合法性，必須存儲網頁文件的原始水印(水印即文件的摘要信息)，以便比對。每個網頁都對應自己的水印，水印總數量與網站上網頁的總數量成正比，網站規模很大時，就必須存儲大量的水印數據。為保證水印存儲和查詢的高效率，InforGuard產品中設計了一個基于多級索引技術的文件數據庫來存儲水印信息。

文件數據庫區別于各種商業數據庫(如Oracle等)，特點是輕便、專用性強，許多產品都會實現自己的文件數據庫來存儲數據。

目前，在此領域采用的方案為：

存儲數據的文件由定長的記錄組成，記錄是固定結構，包含key和data兩部分，key即數據的鍵信息，而data存儲數據內容信息。記錄之間緊湊存儲。查詢記錄時，需要遍歷整個文件對key進行匹配，找到需要的data。

該方法的特點是實現簡單，易于控制，穩定性和可靠性較高。但是查詢效率是該項技術使用的主要限制。雖然通過內存緩沖技術(即cache技術)可以提高查詢的效率，但是受實際環境的限制，當需要存儲大量數據時，仍然很難滿足效率上的要求。

發明內容

本發明的目的就是針對上述的不足，提供了一種基于文件數據庫的多級索引技術，能夠有效提高文件數據庫的查詢性能，從而擴展文件數據庫的可用范圍。

多級索引技術，主要采用了以下技術手段：

1.建立獨立的索引文件

當在數據文件中存儲數據記錄(包含key和data)時，將key和該記錄的存儲偏移值作為索引另存在一個獨立的文件中，稱為索引文件。當根據key查詢數據時，先從索引文件中找到索引，然后再依據其中包含的偏移值，直接從數據文件中定位到目標記錄。

2.按照HASH算法存儲索引

索引文件中對索引的存儲不是按照順序緊湊的方法，而是通過HASH算法把記錄的key轉化為數值，作為存儲該索引的位置偏移量。任何HASH算法都存在沖突的問題，即不同的key可能會轉化出相同的位置偏移量，因此本次索引要存儲的位置可能已被以前的索引占據。可以采取最簡單的策略解決，即從該沖突位置向后查找第一個空白位置，進行存儲。實現時不限于該策略。

根據上述技術，本發明提供的文件數據庫多級索引技術包括數據存儲和數據查詢兩個步驟，其中，

數據存儲包括如下步驟：

1-1)查找數據文件空白位置存儲數據，數據包括鍵(key)和值(data)兩部分，鍵是查詢數據的關鍵字，將鍵和值組成名值對結構，作為存儲記錄，將記錄存入數據文件中的空白位置，該位置標記為data_position；

1-2)HASH轉換產生索引存儲位置，以數據的鍵(key)為參數，調用HASH函數，轉換為一個數值，作為索引存儲位置，該位置標記為index_position；

1-3)在索引文件中存儲索引，索引包括兩部分：，數據的鍵(key)以及1-1)步中獲得的data_position，打開索引文件，以1-2)步產生的index_position為偏移量，將索引存儲到該位置；如果該位置已經被占用，則從該位置起向后查找第一個空白位置進行存儲；

數據查詢包括如下步驟：

2-1)HASH轉換計算出索引的存儲位置，以數據的鍵(key)為參數，調用HASH函數，轉換結果即為索引存儲位置；

2-2)從索引文件取出索引，打開索引文件，從2-1)步獲得的存儲位置開始，向后逐個匹配key，查找目標索引(多數情況下，首個就是匹配的索引)；

2-3)從數據文件中取出數據，2-2)步獲得的索引信息，包含查詢數據在數據文件中的存儲位置，故打開數據文件，按上述位置直接取出數據。

本發明提供的文件數據庫多級索引技術具有如下優點：

1.顯著提高查詢性能

通過HASH算法，可以從索引文件中快速定位到索引信息，進而通過索引信息直接獲得數據的存儲位置。因此，相對于傳統的文件數據庫的遍歷查找機制，本機制定位目標數據的速度明顯提高。

2.保證數據文件存儲空間的利用率