[發明專利]一種HASH索引數據的存儲、讀取方法與系統

在審

• 申請號: 202010581485.3
• 申請日: 2020-06-23
• 公開（公告）號: CN111767436A
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 王金山
• 申請（專利權）人: 北京思特奇信息技術股份有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京匯信合知識產權代理有限公司 11335
• 代理人: 林聰源

本發明公開了一種HASH索引數據的存儲、讀取方法與系統，所述HASH索引數據對應的內存值中儲存有索引記錄；索引記錄的條數由擁有多少HASH值重復的數據決定；索引數據格式為依次排列的索引標志、索引值、下一條指針和下一條被刪除的記錄指針。HASH索引數據的存儲方法為：將多條HASH值重復的數據記錄，存儲在同一個鏈表中；插入索引記錄時，當鏈表頭部索引記錄的“索引標志”為在用狀態，則直接復用頭部索引記錄；當鏈表頭部索引記錄的“索引標志”為已刪除狀態，則取出頭部索引記錄的下一條指針所指向的記錄。解決了當前采用HASH索引的某些值重復度非常高時不能夠快速的插入和刪除的問題。

技術領域

本發明涉及內存數據庫索引數據技術領域，具體涉及一種HASH索引數據的存儲、讀取方法與系統。

背景技術

為了能夠快速的從海量內存記錄中查找特定的記錄，需要為頻繁訪問的字段創建索引。針對等值查找，一般使用HASH索引。

傳統的HASH索引，當HASH值重復時，一般采用鏈表存儲，也就是將重復的值都存儲在同一個鏈表上。如果某個索引值的重復度很高，那么其對應的鏈表就會特別長。針對內存數據庫的使用場景，一般會對索引記錄做頻繁的插入刪除操作，出于高性能的考慮，刪除操作不是真的的刪除，而是在對應記錄處打上刪除標志，以便后續的插入操作可以復用這塊內存。因此在插入一條索引記錄時，由于需要復用之前已刪除的內存空間，就需要順序遍歷整個鏈表，以便找到某個被刪除的位置，然后把新記錄放入。

在表數據量很大的情況下，比如重復數據超過100萬條記錄時，插入會變得非常慢。

發明內容

針對當前采用HASH索引的某些值重復度非常高時不能夠快速的插入和刪除的問題，本發明提供一種HASH索引數據的存儲、讀取方法與系統。

本發明公開了一種HASH索引數據的存儲、讀取方法，所述HASH索引數據對應的內存值中儲存有索引記錄；

所述索引記錄的條數由擁有多少HASH值重復的數據決定；

所述索引數據格式為依次排列的索引標志、索引值、下一條指針和下一條被刪除的記錄指針。

優選地，上述HASH索引數據的存儲方法為：

將多條HASH值重復的數據記錄，存儲在同一個鏈表中；

插入索引記錄時，當鏈表頭部索引記錄的“索引標志”為1，則直接復用頭部索引記錄；當鏈表頭部索引記錄的“索引標志”為0，則取出頭部索引記錄的下一條指針所指向的記錄，若頭部索引記錄的下一條指針所指向的記錄為空，則表示沒有可復用記錄，直接在頭部插入一條新記錄即可；如果頭部索引記錄的下一條指針所指向的記錄不為空，則復用頭部索引記錄的下一條指針所指向的那條記錄。

優選地，上述索引記錄的“索引標志”為1表示當前索引記錄狀態為在用，所述索引記錄的“索引標志”為0表示當前索引記錄狀態為已刪除。

優選地，上述HASH索引數據的讀取方法為根據HASH值、索引標志和索引值進行查詢及數據讀取；具體過程如下：

先根據HASH值進行索引，然后在對應HASH值的索引記錄中進行查詢，查詢過程為先讀取索引標志，讀取索引標志為1的索引記錄中的索引值，與查詢的索引值進行比較，直到找到對應索引記錄。

優選地，上述HASH索引數據的刪除方法為:

索引記錄被刪除時，不釋放索引空間，也不從索引鏈表中刪除，只是修改索引標志為0；

在刪除其中一條索引記錄時，如果它不在鏈表頭部，則將頭部記錄的下一條指針所指向的記錄指向當前刪除的索引記錄，當前刪除的索引記錄的下一條被刪除的記錄指針指向原先鏈表頭部記錄的下一條指針所指向的記錄。