[發明專利]一種基于哈希表和紅黑樹的實時數據存儲與查詢方法

有效

• 申請號: 202110080862.X
• 申請日: 2021-01-21
• 公開（公告）號: CN112417227B
• 公開（公告）日: 2021-06-01
• 發明（設計）人: 沈陽麗;程睿君;劉曙元;李志強;薛尚君
• 申請（專利權）人: 國能信控互聯技術有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京智繪未來專利代理事務所(普通合伙) 11689
• 代理人: 王萍;肖繼軍

一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，包括數據存儲和數據查詢，數據存儲，數據文件按照數據塊來組織數據內容，數據塊的鍵包括標簽ID和數據時間段；當數據塊滿了就會歸入存檔文件，每個文件對應一個索引，當往文件中寫入數據塊時，同時會創建一條索引記錄，將標簽ID和數據時間段作為兩個鍵，以標簽ID為鍵的數據塊存儲在哈希表結構中，以數據時間段為鍵的數據塊存儲在紅黑樹結構中，標簽ID對應紅黑樹的根，數據時間段對應數據文件ID與數據塊ID；數據查詢，根據標簽ID定位紅黑樹根節點，再根據時間段獲取相應紅黑樹節點，返回文件ID和數據塊ID，得到相應數據。本發明提供的索引結構新穎高效，能極大程度地提高實時數據的查詢效率。

技術領域

本發明屬于實時數據庫技術領域，涉及一種基于哈希表和紅黑樹的實時數據存儲與查詢方法。

背景技術

近年來，隨著物聯網和大數據的迅猛發展，實時數據庫應用范圍越來越廣，如：火力、電網、交通、航空、環保等等，故大規模實時數據的存儲和查詢已成為人們日益關注的問題。

在實時數據的存儲和查詢方面，傳統方法通常利用日志記錄或者B樹等形式，存在查詢耗時長的弊端，難以滿足理想的性能需求，故本發明提出基于哈希表和紅黑樹的實時數據存儲與查詢方法。

發明內容

為了解決現有技術存在的問題，本發明的目的在于，提供了一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，以哈希表為一級索引，紅黑樹為二級索引，通過哈希表和紅黑樹的協同合作，大大提高了數據存儲和查詢的效率，滿足了實時數據的性能需求。

本發明采用如下的技術方案：

一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，包括數據存儲和數據查詢，

所述數據存儲包括以下步驟：

步驟1.1：首先數據文件按照數據塊組織數據內容，數據塊的鍵包括標簽ID和數據時間段；

步驟1.2：將標簽ID和數據時間段作為兩個鍵，以標簽ID為鍵的數據塊存儲在哈希表結構中，以數據時間段為鍵的數據塊存儲在紅黑樹結構中，標簽ID對應紅黑樹的根，數據時間段對應數據文件ID與數據塊ID，

在所述數據存儲步驟1.2中，當數據塊填滿時則歸入存檔文件，其中，每個存檔文件對應一個索引，當往存檔文件中寫入數據塊時，同時會創建一條索引記錄。

所述索引記錄和數據塊的歸檔一同創建，索引記錄同時創建一級索引和二級索引；

其中，所述一級索引以標簽ID為鍵，紅黑樹根節點為值，根據求余運算進行散列；

所述二級索引以時間段為鍵，文件ID、數據塊ID和數據塊中的數值個數為值；

所述一級索引為哈希表結構或哈希表節點，二級索引為紅黑樹結構或紅黑樹節點。

所述哈希表包括節點數組和表本身，內存頭部存放表項內容，剩下的部分存放節點內容；

將所有哈希表節點放在連續內存中，使用數組下標來訪問哈希表節點，使用一個結構體類型來引用哈希表節點。

通過對哈希表結構進行標簽點總容量的半數的求余運算，平均只有2個標簽會落入同一個表項中，用于達到所需的散列；

在對哈希表進行求余運算，出現散列沖突時，采用外部拉鏈法，將位于同一個表項中的元素通過一個單鏈表串聯起來。

所述紅黑樹節點包含父親節點、左孩子節點與右孩子節點，另外一個字段是節點顏色，此外還包含一個以數據時間段為鍵的鍵值結構。

將所有紅黑樹節點分配在連續內存中，紅黑樹節點間不留空隙，即相當于一個紅黑樹節點的數組，使用數組下標來訪問紅黑樹節點，使用一個結構體類型來引用紅黑樹節點。