[發明專利]一種基于LSM高效查詢流數據的分布式索引方法及系統

有效

• 申請號: 202110636679.3
• 申請日: 2021-06-08
• 公開（公告）號: CN113312312B
• 公開（公告）日: 2022-08-05
• 發明（設計）人: 鄒承明;馮丹
• 申請（專利權）人: 武漢理工大學
• 主分類號: G06F16/13
• 分類號: G06F16/13;G06F16/182;G06F16/22;G06F16/23;G06F3/06
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 肖明洲

1.一種基于LSM高效查詢流數據的分布式索引方法，其特征在于，包括以下步驟：

步驟1：對數據進行批量更新；

內存中數據為增量數據，磁盤中數據為基線數據，當內存中的數據量達到一定閾值后，增量數據會不斷合并到磁盤，生成新的基線數據并劃分區間；

步驟2：對步驟1中的基線數據進行充分隨機采樣，然后對該采樣數據塊進行排序；

步驟3：對每個數據分區采用改進后的R樹生成算法建立局部索引；

插入數據的過程中，如果該節點為非飽和節點，則直接插入數據；如果該節點為飽和節點，則檢查節點溢出表中是否包含該節點，如果包含且該節點的溢出節點為非飽和狀態，則可以直接將數據插入到該節點的溢出節點中；如果該節點為飽和節點，且節點溢出表中包含該節點，但該節點的溢出節點為飽和狀態，則對該節點及其溢出節點進行歸并分裂操作，并寫回到R樹中，重新進行數據插入；如果該節點為飽和節點，但節點溢出表中不包含該節點，則在節點溢出表中為該節點創建一個溢出節點，并直接將數據插入到此溢出節點中；

步驟4：各個數據分區中的數據及其局部索引由主節點分配到各個子節點中進行存儲，主節點根據各個局部索引的根節點建立全局索引，全局索引直接存儲在主節點中。

2.根據權利要求1所述的基于LSM高效查詢流數據的分布式索引方法，其特征在于：步驟1中，基于LSM-Tree方法對數據進行批量更新，由一個存放在內存中的樹結構和多個存放在磁盤中的樹結構組成，將數據的存儲分為兩部分，一部分是內存中的增量數據，相當于LSM-Tree中的C0 Tree，另一部分是磁盤中的基線數據，相當于LSM-Tree中的C1 Tree、C2Tree和C3 Tree，其中C1 Tree和C2 Tree分別設定最大值和最小值這兩個閾值，而C3Tree存放數值異常的數據；數據的更新只發生在內存中，內存中的數據量達到臨界值就會順序寫入磁盤中，其中順序寫入的過程中，會根據數值做一步判斷，該數據應該放在C1Tree、C2 Tree還是C3 Tree中，從而進一步添加到對應的磁盤空間中。

3.根據權利要求1或2所述的基于LSM高效查詢流數據的分布式索引方法，其特征在于：步驟2中，首先分別對C1 Tree、C2 Tree和C3 Tree中的數據做一個由一維數據向二維數據的轉化，多余的地方用無窮補齊，對這些二維數據首先進行橫坐標軸X的排序，再對縱坐標軸Y進行排序，得到一個從左到右、從下到上遞增的二維數組，對于后續進行數據節點插入的時候，對該二維數組進行順時針旋轉135度，此時可以看作一個多叉排序樹，按照先左子樹后右子樹的順序進行插入。

4.一種基于LSM高效查詢流數據的分布式索引系統，其特征在于，包括以下模塊：

模塊一，用于對數據進行批量更新；

內存中數據為增量數據，磁盤中數據為基線數據，當內存中的數據量達到一定閾值后，增量數據會不斷合并到磁盤，生成新的基線數據并劃分區間；

模塊二，用于對模塊一中的基線數據進行充分隨機采樣，然后對該采樣數據塊進行排序；

模塊三，用于對每個數據分區采用改進后的R樹生成算法建立局部索引；

插入數據的過程中，如果該節點為非飽和節點，則直接插入數據；如果該節點為飽和節點，則檢查節點溢出表中是否包含該節點，如果包含且該節點的溢出節點為非飽和狀態，則可以直接將數據插入到該節點的溢出節點中；如果該節點為飽和節點，且節點溢出表中包含該節點，但該節點的溢出節點為飽和狀態，則對該節點及其溢出節點進行歸并分裂操作，并寫回到R樹中 ，重新進行數據插入；如果該節點為飽和節點，但節點溢出表中不包含該節點，則在節點溢出表中為該節點創建一個溢出節點，并直接將數據插入到此溢出節點中；

模塊四，用于各個數據分區中的數據及其局部索引由主節點分配到各個子節點中進行存儲，主節點根據各個局部索引的根節點建立全局索引，全局索引直接存儲在主節點中。