[發(fā)明專利]一種網(wǎng)絡(luò)流量數(shù)據(jù)索引方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201310698101.6
• 申請日: 2013-12-18
• 公開（公告）號: CN103714134B
• 公開（公告）日: 2017-01-18
• 發(fā)明（設(shè)計）人: 賀泰華;張廣興;謝高崗;董尚文;付喬賓
• 申請（專利權(quán)）人: 中國科學(xué)院計算技術(shù)研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司11006
• 代理人: 祁建國,梁揮

1.一種網(wǎng)絡(luò)流量數(shù)據(jù)索引方法，其特征在于，包括下列步驟：

步驟1，實時捕獲網(wǎng)絡(luò)流量數(shù)據(jù)；

步驟2，所述網(wǎng)絡(luò)流量數(shù)據(jù)具有多個索引字段，在內(nèi)存中通過使所述索引字段維護(hù)位圖-字典樹來建立并存儲所述網(wǎng)絡(luò)流量數(shù)據(jù)的索引結(jié)構(gòu)，對于所述索引字段按字節(jié)來劃分鍵值，通過使所述鍵值在所述位圖-字典樹的位圖結(jié)構(gòu)中所對應(yīng)的非葉子節(jié)點的指針具有孩子節(jié)點、葉子節(jié)點的指針指向存儲位置鏈表來更新所述網(wǎng)絡(luò)流量數(shù)據(jù)的索引結(jié)構(gòu)；

步驟3，根據(jù)用戶的查詢請求查詢所述索引結(jié)構(gòu)從而獲得網(wǎng)絡(luò)流量數(shù)據(jù)的存儲位置信息，將該存儲位置信息返回給用戶，用戶根據(jù)該存儲位置信息獲取響應(yīng)的數(shù)據(jù)。

2.如權(quán)利要求1所述的網(wǎng)絡(luò)流量數(shù)據(jù)索引方法，其特征在于，在所述步驟2中，所述位圖-字典樹的高度等于所述索引字段的字節(jié)大小，對于所述索引字段按照每個字節(jié)一個鍵值來劃分，更新所述網(wǎng)絡(luò)流量數(shù)據(jù)的索引結(jié)構(gòu)的方法具體為：

依次獲取所述索引字段對應(yīng)的鍵值，通過檢測所述鍵值在所述位圖-字典樹的非葉子節(jié)點的位圖結(jié)構(gòu)中所對應(yīng)的比特值為1，來判斷所述非葉子節(jié)點的指針具有孩子節(jié)點，若不具有孩子節(jié)點，則分配一個新節(jié)點，并使所述鍵值對應(yīng)的指針指向該新節(jié)點，同時將該比特值置為1，以使所述非葉子節(jié)點的指針具有孩子節(jié)點，到達(dá)所述位圖-字典樹的葉子節(jié)點時，使所述葉子節(jié)點對應(yīng)指針指向存儲位置鏈表，在該存儲位置鏈表中新增所述索引字段的存儲位置信息。

3.如權(quán)利要求1所述的網(wǎng)絡(luò)流量數(shù)據(jù)索引方法，其特征在于，當(dāng)內(nèi)存中的所述索引結(jié)構(gòu)大于內(nèi)存閾值時，將所述索引結(jié)構(gòu)存入磁盤，并在所述索引結(jié)構(gòu)中增加一條記錄并指向磁盤存儲的位置，同時在內(nèi)存中建立一個新的索引結(jié)構(gòu)，用于處理后續(xù)的網(wǎng)絡(luò)流量數(shù)據(jù)。

4.如權(quán)利要求3所述的網(wǎng)絡(luò)流量數(shù)據(jù)索引方法，其特征在于，將所述索引結(jié)構(gòu)存入磁盤的具體方式為，在磁盤中按照所述位圖-字典樹的層來存儲所述索引結(jié)構(gòu)，且各層采用連續(xù)存儲方式。

5.如權(quán)利要求3或4所述的網(wǎng)絡(luò)流量數(shù)據(jù)索引方法，其特征在于，將所述索引結(jié)構(gòu)存入磁盤的方法具體為，

對于所述位圖-字典樹的每個節(jié)點，先存儲位圖結(jié)構(gòu)，然后存儲一個文件偏移位置的數(shù)組，該數(shù)組示出所述位圖-字典樹的每個節(jié)點的各孩子節(jié)點在磁盤中的存儲位置，而對于所述位圖-字典樹的每個葉子節(jié)點，該數(shù)組示出每個葉子節(jié)點對應(yīng)鏈表的存儲位置。

6.如權(quán)利要求1或2所述的網(wǎng)絡(luò)流量數(shù)據(jù)索引方法，其特征在于，所述步驟3的查詢所述索引結(jié)構(gòu)的查詢過程為，

將查詢條件按照每個字節(jié)一個鍵值來劃分，其中最后一個鍵值為未知鍵值，依此獲取所述查詢條件的鍵值，通過讀取所述鍵值在所述位圖-字典樹的非葉子節(jié)點的位圖結(jié)構(gòu)中所對應(yīng)的比特值為1來獲取該根節(jié)點對應(yīng)孩子節(jié)點在磁盤中的存儲位置，并讀取該位置上的位圖-字典樹節(jié)點，否則返回查詢結(jié)果為空，到達(dá)最后一個鍵值的前一個鍵值時，獲取其在位圖-字典樹的位圖結(jié)構(gòu)中所對應(yīng)的所有比特值為1的位，然后獲取該所有比特值為1的位的偏移位置，最后讀取這些偏移位置的葉子節(jié)點和其對應(yīng)的鏈表元素，并將鏈表元素進(jìn)行合并返回。

7.一種網(wǎng)絡(luò)流量數(shù)據(jù)索引系統(tǒng)，其特征在于，包括下列模塊：

網(wǎng)絡(luò)流量數(shù)據(jù)獲取模塊，用于通過網(wǎng)卡或板卡來實時捕獲網(wǎng)絡(luò)流量數(shù)據(jù)；

索引結(jié)構(gòu)維護(hù)模塊，所述網(wǎng)絡(luò)流量數(shù)據(jù)具有多個索引字段，該模塊用于在內(nèi)存中通過使所述索引字段維護(hù)位圖-字典樹來建立并存儲所述網(wǎng)絡(luò)流量數(shù)據(jù)的索引結(jié)構(gòu)，對于所述索引字段按字節(jié)來劃分鍵值，通過使所述鍵值在所述位圖-字典樹的位圖結(jié)構(gòu)中所對應(yīng)的非葉子節(jié)點的指針具有孩子節(jié)點、葉子節(jié)點的指針指向存儲位置鏈表來更新所述網(wǎng)絡(luò)流量數(shù)據(jù)的索引結(jié)構(gòu)；

查詢響應(yīng)模塊，用于根據(jù)用戶的查詢請求查詢所述索引結(jié)構(gòu)從而獲得網(wǎng)絡(luò)流量數(shù)據(jù)的存儲位置信息，將該存儲位置信息返回給用戶，用戶根據(jù)該存儲位置信息獲取響應(yīng)的數(shù)據(jù)。