[發明專利]一種結構緊湊的鍵值對存儲結構及快速鍵值對查找方法

有效

• 申請號: 201711287661.7
• 申請日: 2017-12-07
• 公開（公告）號: CN108021678B
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 嵩天;魏煜
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/242;G06F16/2455
• 代理公司: 北京正陽理工知識產權代理事務所(普通合伙) 11639
• 代理人: 鮑文娟

本發明涉及一種結構緊湊的鍵值對存儲結構及快速鍵值對查找方法，屬于實時大數據處理及鍵值查詢技術領域。基于分層哈希表和布魯姆過濾器相結合的結構，通過首層使用2?left hashing哈希結構存儲，每層哈希表都作為輔助表保存在上層表中發生存儲沖突的數據，并結合布魯姆過濾器進行沖突數據的保存，將“布魯姆過濾器判斷所查找的鍵是否存在當前集合中的結果”作為索引提高查找速度，從而提高存儲空間利用率使結構緊湊并實現快速查找的軟件平臺要求。本發明可高速有效地解決當前大規模鍵值對存儲和查找時間不確定、查找速度不恒定、軟件實現運行速度較慢達不到應用要求等問題。

技術領域

本發明涉及一種結構緊湊的鍵值對存儲結構及快速鍵值(key-value)對查找方法，特別涉及一種基于多層次哈希表(hash table)和布魯姆過濾器(bloom filter，BF)的鍵值對存儲和查找方法，屬于實時大數據處理及鍵值查詢技術領域。

背景技術

隨著互聯網規模的日益擴大，網絡流量日益增長，計算機技術領域對大數據存儲和查找速率的要求越來越高。鍵值對查找問題在計算機領域的各個方向如大數據處理和高速網絡中應用頗廣。

然而，鍵值對查找方法的性能嚴重受限于硬件資源，因此，在網絡功能虛擬化的趨勢下，適應軟件平臺更為重要且更加適應互聯網發展。在一個軟件平臺中會同時處理多種任務，存儲和查找方法不能獨自占用一整個高速緩存(cache)，因此，該方法要謹慎地控制放入cache中的結構大小，且避免頻繁替換。然而，現有方法大多數更適應硬件平臺，且在查找速度和cache使用效率方面不夠高。

現在已有的鍵值對查找方法主要分為哈希表查找，樹形查找，以及基于布魯姆過濾器的查找方法。哈希表方法是較為傳統的方法，可以通過確定的時間復雜度O(1)執行鍵值對的插入，刪除，查找，但是哈希表的重要缺點是它需要處理哈希沖突，以至于無法每次都在O(1)復雜度完成。因此，單純使用哈希表進行方法的基礎數據結構設計無法滿足當前對鍵值對查找速度的要求，而減少哈希沖突又需要更大的存儲空間，從而導致空間利用率較低。

基于布魯姆過濾器數據結構的方法主要依賴于布魯姆過濾器結構簡單、緊湊的特性。主要方法有多個布魯姆過濾器組合的方法，布魯姆過濾器結合數據編碼的方法，基于布魯姆過濾器變形后的數據結構等。這些結構改變了原有布魯姆過濾器的結構，提升了一定的空間使用率，但是破壞了布魯姆過濾器原有的簡單、緊湊的特性，因此并沒有發揮出Bloom filter應有的效果。

本發明涉及一種具有緊湊且快速特點的鍵值對查找方法，提供了一種結構緊湊的鍵值對存儲結構，提高了傳統哈希表方法的空間利用率，通過確定的時間復雜度完成鍵值對的查找，所提出的結構緊湊的鍵值對存儲結構和快速鍵值對查找方法主要涉及以下兩個問題：

(1)基于多層哈希表設計，使用2-left hashing哈希結構為多層次哈希表的首層，保證結構的緊密和空間的高利用率，同時減少哈希沖突；

(2)通過多層的布魯姆過濾器存儲對應層哈希表中沖突數據，及提供被查找鍵是否存在當前層沖突數據集的結果作為查找索引，提高查找速度，減少內存訪問次數。

發明內容

本發明的目的是為了克服現有方法的鍵值對存儲結構不夠緊湊的缺陷以及為了解決當前大規模鍵值對存儲和查找時間不確定性，軟件實現運行速度過慢達不到應用要求等問題，滿足合理利用高速緩存爭取更少地進行數據替換的要求，提出一種結構緊湊的鍵值對存儲結構及快速鍵值對查找方法。

本發明的思想是基于分層哈希表和布魯姆過濾器相結合的結構，通過首層使用2-left hashing哈希結構存儲，每層哈希表都作為輔助表保存在上層表中發生存儲沖突的數據，并結合布魯姆過濾器進行沖突數據的保存，將“布魯姆過濾器判斷所查找的鍵是否存在當前集合中的結果”作為索引提高查找速度，從而提高存儲空間利用率使結構緊湊并實現快速查找的軟件平臺要求。一種結構緊湊的鍵值對存儲結構及快速鍵值對查找方法，包括一種結構緊湊的鍵值對存儲結構及一種快速鍵值對查找方法；