[發明專利]基于Hbase散列概要森林對時序數據進行索引的方法

有效

• 申請號: 201710154614.9
• 申請日: 2017-03-15
• 公開（公告）號: CN106991137B
• 公開（公告）日: 2019-10-18
• 發明（設計）人: 尹建偉;馮詩淳;鄧水光;李瑩;吳健;吳朝暉;易崢
• 申請（專利權）人: 浙江大學;浙江核新同花順網絡信息股份有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

1.一種基于Hbase散列概要森林對時序數據進行索引的方法，包括以下步驟：

(1)根據樹高、葉子節點包含的時間范圍建立包含固定時間粒度的每棵時間單元樹；

(2)求取每棵時間單元樹的散列碼，并將帶有散列碼的時間單元樹組成基于Hbase的散列概要森林；

(3)將采集的時序數據根據散列碼插入到散列概要森林中；

(4)根據時間范圍查詢讀取存儲的時序數據；

每棵時間單元樹是一棵線段樹，線段樹節點存儲該節點范圍的概要信息，包括：LBound、RBound、LNode、LNode以及Data；其中，LBound、RBound分別表示該節點包含時間范圍的起始時間點和終止時間點；LNode、LNode分別表示該節點左孩子和右孩子節點包含時間范圍的中點；Data表示該節點存放的概要數據值，此時建立的時間單元樹的每個節點的Data是空的；

每棵時間單元樹的散列碼Hash的求取公式為：

Hash＝md5(tree Info+tree low bound)

tree info為數據標識簡要信息；tree low bound為時間單元樹的起始時間點；md5為一種轉碼方式；

所述的基于Hbase的散列概要森林由tree-hash和tree-node兩個Hbase表組成，其中，tree-hash表用于存儲所有時間單元樹對應的散列碼，每個tree-node表存有對應時間單元樹的所有葉子節點，且tree-hash表與tree-node表是單獨存儲，并且將擁有相同散列碼的時間單元樹載有的時序數據集中存儲。

2.根據權利要求1所述基于Hbase散列概要森林對時序數據進行索引的方法，其特征在于：將時序數據插入到散列概要森林的具體過程為：

(3-1)通過時序數據的所屬于的時間在tree-hash表中找到此時序數據所在的時間單元樹的散列碼；

(3-2)找到該散列碼所對應的tree-node表，將時序數據遞歸插入到此tree-node表中，具體過程為：

根據散列碼找到所處時間單元樹的根節點開始遞歸，然后進行時序數據的時間點與當前查詢節點的時間范圍對比，當時序數據的時間點小于該節點的時間范圍的中間時間點時，向該節點的左孩子節點的Data中遞歸插入時序數據，當時序數據的時間點大于該節點的時間范圍的中間時間點時，則該節點的右孩子節點的Data中遞歸插入時序數據；直到插入到時間單元樹的葉子節點為止。

3.根據權利要求1所述基于Hbase散列概要森林對時序數據進行索引的方法，其特征在于：進行數據查詢的過程為：

(a)判斷查詢時間范圍(t1,t2)是否屬于同一個時間單元樹范圍，若是，執行步驟(b)，若否，執行步驟(c)；

(b)執行查詢操作Query(t1,t2)

(c)執行查詢操作Query(t1,EndUnitTime(t1))、Query(midUnitTime)以及Query(StartUnitTime(t2),t2)；

其中，StartUnitTime(t2)為時間點t2所處的時間單元樹包含的時間范圍的起始時間點；

EndUnitTime(t1)為時間點t1所處的時間單元樹包含的時間范圍的的結束時間點；

midUnitTime為t1與t2所處的時間單元樹的時間范圍之間的時間范圍；

Query(t1,t2)表示為在查詢范圍t1～t2所屬同一棵時間單元樹中執行查詢操作；

Query(t1,EndUnitTime(t1))表示在查詢范圍t1～EndUnitTime(t1)中的第一棵單元樹中執行查詢操作；

Query(midUnitTime)表示在查詢范圍midUnitTime中的第二棵到第倒數第二棵單元樹中執行查詢操作；

Query(StartUnitTime(t2),t2)表示在查詢范圍StartUnitTime(t2)～t2中的最后一棵單元樹中執行查詢操作。

4.根據權利要求3所述基于Hbase散列概要森林對時序數據進行索引的方法，其特征在于：Query(t1,t2)的具體過程為：

(a)通過查找項的時間推算出其所屬時間單元樹的散列碼并定位到此時間單元樹，并將此時間單元樹的根節點作為當前根節點；

(b)從當前根節點開始遞歸查詢，查詢任務從(t1,t2)開始；

(c)遞歸查詢到當前節點時，解析出該節點包含的時間范圍的起始時間點LBound、中間時間點midTime以及終止時間點RBound；

(d)判斷t1與t2是否滿足t1＝LBound且t2＝RBound，若是，記錄該節點結果并退出遞歸，若否，執行步驟(e)；

(e)判斷t1與t2是否滿足t1≤midTime且t2≤midTime，若是，將該節點的左孩子節點作為當前根節點，跳轉執行步驟(b)～步驟(d)，若否，執行步驟(f)；

(f)判斷t1與t2是否滿足t1≥midTime且t2≥midTime，若是，將該節點的右孩子節點作為當前根節點，執行步驟(b)～步驟(d)；若否，執行步驟(g)；

(g)判斷時間t2是否滿足LBound<t2<midTime，若是，將左孩子作為當前節點，將midTime作為t2，執行步驟(b)～步驟(d)；將右孩子節點作為當前節點，將midTime作為t1，執行步驟(b)～步驟(d)。