[發明專利]稀疏索引的建立方法和裝置、稀疏索引及查詢方法和裝置

在審

• 申請號: 201110347637.4
• 申請日: 2011-11-07
• 公開（公告）號: CN103092885A
• 公開（公告）日: 2013-05-08
• 發明（設計）人: 周大;錢嶺;郭磊濤;齊驥
• 申請（專利權）人: 中國移動通信集團公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 謝安昆;宋志強

1.一種稀疏索引的建立方法，其特征在于，包括：

針對每個待處理的數據記錄，分別利用同一散列函數計算其鍵值的散列值，并根據計算出的散列值將該數據記錄保存到對應的分區中，保存到同一分區中的數據記錄具有相同的散列值；

對于任一分區，初始階段，其中的內容為空，當所保存的數據記錄達到預定要求時，利用所保存的數據記錄組成一個文件塊，當所保存的未組成文件塊的數據記錄再次達到預定要求時，利用未組成文件塊的數據記錄組成另一個文件塊，依次類推；每組成一個文件塊，則為該文件塊建立一個索引項。

2.根據權利要求1所述的方法，其特征在于，該方法進一步包括：對于任一分區，當不再有新的數據記錄需要保存，但所保存的未組成文件塊的數據記錄未達到預定要求時，利用未組成文件塊的數據記錄組成一個文件塊。

3.根據權利要求1或2所述的方法，其特征在于，所述達到預定要求包括：達到預定個數。

4.根據權利要求1所述的方法，其特征在于，

每個分區分別具有一個不同于其它分區的編號，每個文件塊分別具有一個不同于同一分區中的其它文件塊的編號；

每個索引項中分別包括：最大鍵值、最小鍵值、分區號、文件塊號和散列函數名；其中，

最大鍵值是指該索引項對應的文件塊中的各數據記錄的鍵值中的最大值；

最小鍵值是指該索引項對應的文件塊中的各數據記錄的鍵值中的最小值；

分區號是指該索引項對應的文件塊所屬的分區的編號；

文件塊號是指該索引項對應的文件塊的編號；

散列函數名是指計算散列值時所使用的散列函數的名稱。

5.根據權利要求4所述的方法，其特征在于，當所述稀疏索引建立完畢之后，進一步包括：

接收待查詢鍵值，并從各索引項中查找出最小鍵值小于或等于待查詢鍵值且最大鍵值大于或等于待查詢鍵值的索引項，將查找出的索引項作為候選索引項；

針對每個候選索引項，分別利用其中的散列函數名對應的散列函數計算待查詢鍵值的散列值以及該候選索引項中的最小鍵值或最大鍵值的散列值，如果待查詢鍵值的散列值等于該候選索引項中的最小鍵值或最大鍵值的散列值，則將該候選索引項作為結果索引項；

遍歷各結果索引項對應的文件塊中的各數據記錄，得到待查詢鍵值對應的數據記錄。

6.一種稀疏索引的建立裝置，其特征在于，包括：

計算模塊，用于針對每個待處理的數據記錄，分別利用同一散列函數計算其鍵值的散列值，并將該數據記錄及計算出的散列值發送給建立模塊；

所述建立模塊，用于根據接收到的散列值將接收到的數據記錄保存到對應的分區中，保存到同一分區中的數據記錄具有相同的散列值；對于任一分區，初始階段，其中的內容為空，當所保存的數據記錄達到預定要求時，利用所保存的數據記錄組成一個文件塊，當所保存的未組成文件塊的數據記錄再次達到預定要求時，利用未組成文件塊的數據記錄組成另一個文件塊，依次類推；每組成一個文件塊，則為該文件塊建立一個索引項。

7.根據權利要求6所述的裝置，其特征在于，所述建立模塊進一步用于，對于任一分區，當不再有新的數據記錄需要保存，但所保存的未組成文件塊的數據記錄未達到預定要求時，利用未組成文件塊的數據記錄組成一個文件塊。

8.根據權利要求6或7所述的裝置，其特征在于，所述達到預定要求包括：達到預定個數。

9.根據權利要求6所述的裝置，其特征在于，

每個分區分別具有一個不同于其它分區的編號，每個文件塊分別具有一個不同于同一分區中的其它文件塊的編號；

每個索引項中分別包括：最大鍵值、最小鍵值、分區號、文件塊號和散列函數名；其中，

最大鍵值是指該索引項對應的文件塊中的各數據記錄的鍵值中的最大值；

最小鍵值是指該索引項對應的文件塊中的各數據記錄的鍵值中的最小值；

分區號是指該索引項對應的文件塊所屬的分區的編號；

文件塊號是指該索引項對應的文件塊的編號；

散列函數名是指計算散列值時所使用的散列函數的名稱。