[發明專利]搜索目標鍵的方法、系統和非暫時性計算機可讀介質

在審

• 申請號: 202010766145.8
• 申請日: 2020-08-03
• 公開（公告）號: CN112540981A
• 公開（公告）日: 2021-03-23
• 發明（設計）人: 樸熙權;洪一九;李好彬;奇亮奭
• 申請（專利權）人: 三星電子株式會社
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2455
• 代理公司: 北京銘碩知識產權代理有限公司 11286
• 代理人: 王兆賡;尹淑梅

提供了搜索目標鍵的方法、系統和非暫時性計算機可讀介質，所述方法包括：使用哈希偏移表條目填充排序鍵表的哈希偏移表，哈希偏移表條目具有與相應的鍵對應的哈希值和哈希偏移；基于哈希值對哈希偏移表條目進行排序；在哈希偏移表中搜索哈希值中的與目標鍵對應的目標哈希值；基于目標哈希值定位與目標鍵對應的目標鍵值對；以及保存目標鍵值對的位置。

技術領域

本公開的實施例的一個或多個方面總體上涉及在數據庫中搜索目標鍵的方法、系統和非暫時性計算機可讀介質。

背景技術

在鍵值(KV)存儲的表中搜索和檢索隨機鍵會導致嚴重的開銷。這樣的開銷通常由于利用多鍵比較的搜索所引起。因此，一些鍵搜索技術通常會使用與各種鍵比較相關聯的大量的CPU周期。因此，更高效地且更有效地定義表的數據結構可以是有用的。

發明內容

在此描述的實施例提供用于通過將哈希偏移表映射到鍵值表而改善數據存儲的在數據庫中搜索目標鍵的方法。

根據本公開的一個實施例，提供了一種在數據庫中搜索目標鍵的方法，所述方法包括：使用哈希偏移表條目填充排序鍵表的哈希偏移表，哈希偏移表條目具有哈希偏移和與相應的鍵對應的哈希值；基于哈希值對哈希偏移表條目進行排序；在哈希偏移表中搜索哈希值中的與目標鍵對應的目標哈希值；基于目標哈希值定位與目標鍵對應的目標鍵值對；以及保存目標鍵值對的位置。

搜索目標哈希值的操作可以包括執行二分搜索。

所述方法還可以包括從目標鍵計算目標哈希值。

保存目標鍵值對的位置的操作可以包括將目標哈希值映射到目標鍵值對。

定位目標鍵值對的操作可以包括基于哈希偏移定位目標鍵值對。

排序鍵表還可以包括鍵值表，鍵值表包括多個鍵值表條目，鍵值表條目包括目標鍵值對。

鍵值表條目的數量可以與哈希偏移表條目的數量相同。

根據本公開的另一實施例，提供了一種用于在數據庫中搜索目標鍵的系統，所述系統包括存儲器上數據結構、存儲格式數據結構和存儲裝置，其中，所述系統被配置為：在存儲格式數據結構中使用哈希偏移表條目填充排序鍵表的哈希偏移表，哈希偏移表條目具有哈希偏移和與相應的鍵對應的哈希值；根據存儲器上數據結構的存儲器上排序結構，基于哈希值對哈希偏移表條目進行排序；搜索存儲器上數據結構或存儲格式數據結構以在哈希偏移表中獲取哈希值中的與目標鍵對應的目標哈希值；在存儲器上數據結構或存儲格式數據結構中基于目標哈希值定位與目標鍵對應的目標鍵值對；以及將目標鍵值對的位置保存到存儲器上數據結構或存儲格式數據結構。

所述系統還可以被配置為通過執行二分搜索來搜索目標哈希值。

所述系統還可以被配置為從目標鍵計算目標哈希值。

所述系統還可以被配置為通過將目標哈希值映射到目標鍵值對來保存目標鍵值對的位置。

所述系統還可以被配置為基于哈希偏移定位目標鍵值對。

排序鍵表還可以包括鍵值表，鍵值表包括多個鍵值表條目，鍵值表條目包括目標鍵值對。

根據本公開的又一實施例，提供了一種非暫時性計算機可讀介質，所述非暫時性計算機可讀介質被實現在用于在數據庫中搜索目標鍵的系統上，所述非暫時性計算機可讀介質具有當在處理器上執行時實現數據存儲的方法的計算機代碼，所述方法包括：使用哈希偏移表條目填充排序鍵表的哈希偏移表，哈希偏移表條目具有哈希偏移和與相應的鍵對應的哈希值；基于哈希值對哈希偏移表條目進行排序；在哈希偏移表中搜索哈希值中的與目標鍵對應的目標哈希值；基于目標哈希值定位與目標鍵對應的目標鍵值對；以及保存目標鍵值對的位置。

計算機代碼在被處理器執行時還可以通過經由執行二分搜索對目標哈希值進行搜索來實現所述數據存儲的方法。