[發明專利]一種大容量緩存及其快速檢索方法、構建方法

在審

• 申請號: 201410495963.3
• 申請日: 2014-09-24
• 公開（公告）號: CN104317810A
• 公開（公告）日: 2015-01-28
• 發明（設計）人: 楊耀敏;易樂天;曲維杰
• 申請（專利權）人: 北京云巢動脈科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市盛峰律師事務所 11337
• 代理人: 于國富

技術領域

本發明涉及數據檢索領域，尤其涉及一種大容量緩存及其快速檢索方法、構建方法。

背景技術

在處理大量數據時，數據的檢索時間是影響程序性能的一個重要因素。

目前，對于大量數據的檢索，一般利用“樹”這種數據結構，比如：red-black?tree、radix?tree等。

radix?tree是一種比較常用的樹，可以實現數據的有效存儲，并且可以實現數據的快速查詢。

但是，使用radix?tree這種數據結構，實際數據都只能保存在葉子節點。在處理大量數據的時候，需要創建大量管理節點來管理葉子節點，會造成大量內存空間的浪費。

發明內容

本發明的目的在于提供一種大容量緩存及其快速檢索方法、構建方法，從而解決現有技術中存在的前述問題。

為了實現上述目的，本發明采用的技術方案如下：

一種大容量緩存，所述大容量緩存的數據結構包括鏈表和radix?tree；數據保存在所述鏈表中，所述鏈表設置于所述radix?tree的葉子節點上；所述數據的key包括第一key和第二key，所述第一key用于檢索所述radix?tree，查找所述key對應的所述鏈表；所述第二key用于檢索所述key對應的所述鏈表，查找所述數據。

具體地，所述radix?tree的節點槽數量設置為16～128，且所述radix?tree的高度設置為3～8。

優選地，所述radix?tree的節點槽數量設置為64，且所述radix?tree的高度設置為5。

上述大容量緩存的快速檢索方法，包括如下步驟:

S1，接收key；

S2，根據第一key檢索radix?tree，查找所述key對應的鏈表；如果沒有查找到所述key對應的鏈表，則返回處理結果；如果查找到了所述key對應的鏈表，則之行步驟S3；

S3，根據第二key檢索所述key對應的鏈表，查找所述key對應的數據；

S4，找到所述數據后，更新所述數據的訪問時間和訪問次數；

S5，返回查找到的所述數據。

進一步地，在步驟S4和S5之間，還包括步驟，

根據所述數據的訪問時間和訪問次數，判斷所述數據在所述key對應的鏈表中的位置是否需要調整，如果不需要調整，則執行步驟S5；如果需要調整，則調整所述數據在所述key對應的鏈表中的位置。

其中，所述調整所述數據在所述key對應的鏈表中的位置，具體為，如果所述數據的訪問優先級高于所述鏈表中的對比數據的訪問優先級，則將所述數據移動到該對比數據的前面；如果所述數據的訪問優先級低于所述鏈表中的對比數據的訪問優先級，則將所述數據移動到該對比數據的后面。

上述大容量緩存的構建方法，包括如下步驟:

S1，接收數據和key；

S2，根據第一key檢索radix?tree，查找所述key對應的鏈表；

S3，根據第二key檢索所述key對應的鏈表，查找所述key對應的數據；如果查找到了所述數據，則放棄所述數據和key；如果沒有查找到所述數據，則執行步驟S4-S5；

S4，將所述數據插入到所述key對應的鏈表中；

S5，更新所述數據的訪問時間和訪問次數。

進一步地，步驟S5之后，還包括步驟，

根據所述數據的訪問時間和訪問次數，判斷所述數據在所述key對應的鏈表中的位置是否需要調整，如果不需要調整，則結束；如果需要調整，則調整所述數據在所述key對應的鏈表中的位置。

其中，所述調整所述數據在所述key對應的鏈表中的位置，具體為，具體為，如果所述數據的訪問優先級高于所述鏈表中的對比數據的訪問優先級，則將所述數據移動到該對比數據的前面；如果所述數據的訪問優先級低于所述鏈表中的對比數據的訪問優先級，則將所述數據移動到該對比數據的后面。

本發明的有益效果是：

本發明結合了鏈表和radix?tree這兩種數據結構的特點，通過在radix?tree的葉子節點上用鏈表來保存需要檢索的實際數據，并將數據的key拆分成兩部分：第一部分用于檢索radix?tree，找到key對應的鏈表，第二部分用于檢索key對應的鏈表，找到需要檢索的實際數據。從而實現了在處理大量數據的時候，既可以快速的檢索到數據，又不需要創建大量的管理節點來管理葉子節點，節約了內存空間，提高了內存空間的利用率。

附圖說明