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

有效

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

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

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

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

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

所述數據查詢包括以下步驟：

步驟2.1：首先根據標簽ID定位紅黑樹根節點；

步驟2.2：再根據時間段獲取相應紅黑樹節點，返回文件ID和數據塊ID，得到相應數據。

2.根據權利要求1所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

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

3.根據權利要求2所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

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

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

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

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

4.根據權利要求3所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

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

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

5.根據權利要求3所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

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

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

6.根據權利要求3所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

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

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

7.根據權利要求1所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

通過對查詢語句進行解析，得到待查詢數據的查詢參數；

根據查詢參數中指定的標簽ID，定位到哈希表中相應紅黑樹根節點，從而找到根節點對應的紅黑樹；

然后根據查詢參數中的時間，對紅黑樹節點進行二分查找，從而找到相應樹節點，得到文件ID和數據塊ID，獲取相應數據。

8.根據權利要求7所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

根據查詢參數中指定的單個標簽ID和時間段，查詢獲取單個標簽點相應時間段數據。

9.根據權利要求7所述的一種基于哈希表和紅黑樹的實時數據存儲與查詢方法，其特征在于，

根據查詢參數中指定的多個標簽ID和時刻，查詢獲取多個標簽點相應時刻斷面數據。