[發明專利]一種時序數據亂序操作處理方法和裝置

有效

• 申請號: 201711322396.1
• 申請日: 2017-12-12
• 公開（公告）號: CN107943519B
• 公開（公告）日: 2018-12-11
• 發明（設計）人: 王建民;黃向東;曹高飛;龍明盛;王晨
• 申請（專利權）人: 清華大學
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

1.一種時序數據亂序操作處理方法，其特征在于，包括：

獲取亂序操作TP的操作類型op、起始時間戳s、結束時間戳e、亂序操作值v，同時獲取二叉樹的根節點ROOT狀態；

若判斷獲知所述根節點ROOT為空，則在所述ROOT中存儲所述op、s、e、v；

若判斷獲知所述ROOT不為空，且滿足第一預設條件，則令ROOT.v＝TP.v，其中，若ROOT.op為插入INSERT且TP.op為更新UPDATE，則令ROOT.op＝TP.op，ROOT.v＝TP.v；

所述第一預設條件為：TP.s＝ROOT.s，TP.e＝ROOT.e，且不滿足R OOT.op為刪除DELETE時，TP.op為更新UPDATE；

所述ROOT.op為所述根節點存儲的操作類型，所述ROOT.s為所述根節點存儲的起始時間戳，ROOT.e為所述根節點存儲的結束時間戳；TP.op為所述亂序操作的操作類型；所述TP.s為所述亂序操作的起始時間戳，TP.e為所述亂序操作的結束時間戳。

2.根據權利要求1所述的時序數據亂序操作處理方法，其特征在于，若判斷獲知所述根節點ROOT為空，則在所述ROOT中存儲所述op、s、e、v；具體包括：

所述亂序操作寫入根節點時，所述根節點隨機生成一個fix值；

若所述亂序操作為插入INSERT，在時間點t插入新值v，則在所述ROOT中存儲：ROOT.s＝ROOT.e＝t，ROOT.v＝v，ROOT.op＝INSERT，ROOT.fix＝fix，ROOT.left＝ROOT.right＝NULL；

若所述亂序操作為更新UPDATE，將時間段[s，e]內已存在的數據值更新為新值v，則在所述ROOT中存儲：ROOT.s＝s，ROOT.e＝e，ROOT.v＝v，ROOT.op＝UPDATE，ROOT.fix＝fix，ROOT.left＝ROOT.rig ht＝NULL；

若所述亂序操作為刪除DELETE，將時間點t之前的數據刪除，則在所述ROOT中存儲：ROOT.s＝ROOT.e＝t，ROOT.v＝NULL，ROOT.o p＝DELETE，ROOT.fix＝fix，ROOT.left＝NULL，ROOT.right＝NULL；

其中，ROOT.v為所述根節點存儲的時間段的值，所述ROOT.left為所述根節點的左孩子節點，所述ROOT.right為所述根節點的右孩子節點，NULL表示空。

3.根據權利要求2所述的時序數據亂序操作處理方法，其特征在于，還包括若判斷獲知所述ROOT不為空，且TP.s＝ROOT.s，TP.e＝R OOT.e，ROOT.op＝DELETE，TP.op＝UPDATE；則進行存儲判決：

判斷亂序操作集合INSERT_LIST是否為空，若不為空，則遍歷I NSERT_LIST中存儲的操作I，并更新TP＝I，將更新后的TP存儲至根列表；若為空，則判斷當前亂序操作序列已存儲至二叉樹中。

4.根據權利要求2所述的時序數據亂序操作處理方法，其特征在于，還包括：

若TP.e＜ROOT.s，則更新ROOT＝ROOT.left，將所述左孩子節點作為新的根節點，將所述亂序操作存入所述左孩子節點中。

5.根據權利要求2所述的時序數據亂序操作處理方法，其特征在于，還包括：

若ROOT.e＜TP.s，則更新ROOT＝ROOT.right，將所述右孩子節點作為新的根節點，將所述亂序操作存入所述右孩子節點中。