[發(fā)明專利]一種基于緩存機制的實時數(shù)據(jù)索引快速動態(tài)更新方法

有效

• 申請?zhí)枺?/td>: 201910650034.8
• 申請日: 2019-07-18
• 公開（公告）號: CN110489601B
• 公開（公告）日: 2022-09-16
• 發(fā)明（設(shè)計）人: 戴則梅;孫世明;房俊華;蘇標(biāo)龍;趙朋朋;唐元合;周福;馬潔;于雷;張怡然;魏學(xué)云
• 申請（專利權(quán)）人: 國電南瑞科技股份有限公司;國網(wǎng)山東省電力公司電力科學(xué)研究院;國電南瑞南京控制系統(tǒng)有限公司;南瑞集團有限公司;國家電網(wǎng)有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 張弛

本發(fā)明提供一種基于緩存機制的實時數(shù)據(jù)索引快速動態(tài)更新方法，通過在索引樹中維護一個插入元素集IS和一個刪除元素集DS作為索引元素的輔助處理元素集，實現(xiàn)索引數(shù)據(jù)的緩存機制；該緩存機制可以有效降低樹形索引在動態(tài)更新時樹結(jié)構(gòu)的調(diào)整次數(shù)，從而提升樹形索引的更新性能。這種緩存機制應(yīng)用在實時處理系統(tǒng)中，可以同時滿足實時處理系統(tǒng)對索引的查詢和更新性能的要求。

技術(shù)領(lǐng)域

本發(fā)明屬于計算機數(shù)據(jù)處理的技術(shù)領(lǐng)域。

背景技術(shù)

數(shù)據(jù)的實時處理已經(jīng)成為數(shù)據(jù)分析的主流方式。很多系統(tǒng)都會產(chǎn)生大量的實時數(shù)據(jù)，比如工業(yè)傳感器檢測到的電氣信號、移動設(shè)備發(fā)出的GPS信息、電子商務(wù)網(wǎng)站上的用戶瀏覽信息、系統(tǒng)運行日志等。如果對這些實時數(shù)據(jù)能做出的反應(yīng)越快，從中獲取的好處就越大。畢竟越新鮮的數(shù)據(jù)才越有價值。在電網(wǎng)系統(tǒng)中更是如此，越早檢測或預(yù)測出設(shè)備故障，就能越快地采取保護措施避免產(chǎn)生更大的損失。比如下面一個例子：一個設(shè)備的故障會產(chǎn)生一系列的動作，故障導(dǎo)致線路短路；短路的過流電流導(dǎo)致線路上的開關(guān)斷開；然后設(shè)備會產(chǎn)生一個緊急保護動作。整個過程中的開關(guān)斷開信號和緊急保護動作信號會上傳到實時處理系統(tǒng)中。實時系統(tǒng)根據(jù)這個兩個信號判斷出某個設(shè)備發(fā)生了故障，然后傳遞給下游系統(tǒng)處理這個故障。一次故障的開關(guān)斷開信號的保護動作信號并不是按時有序到達系統(tǒng)的，這期間會有網(wǎng)絡(luò)延遲。所以這兩個信號是亂序到達的，兩者之間的間隔可能高達十幾秒。系統(tǒng)每秒接收的數(shù)據(jù)量高達百萬，如果再緩存十幾秒的歷史數(shù)據(jù)，那么系統(tǒng)處理的數(shù)據(jù)量就高達千萬。從千萬級別的數(shù)據(jù)中檢測出所有的設(shè)備故障信息并且要求低延遲，這是一件有挑戰(zhàn)的事情。

然而，在實時處理系統(tǒng)中不僅要求索引有良好的查詢性能，還要求索引有快速的更新能力。因為實時處理系統(tǒng)中要求數(shù)據(jù)具有實時性，所以需要頻繁地從索引中刪除舊數(shù)據(jù)和插入新數(shù)據(jù)。

索引樹通常是一棵平衡樹。如果不保證樹的平衡性，在極端情況下索引樹就會變成一個鏈表。在這種情況下，索引的查詢就變成對鏈表的窮舉掃描。索引也就失去了意義。但保證樹形索引的平衡性也是索引更新性能低下的原因。因為在動態(tài)更新索引的情景下，樹會經(jīng)常失衡，這就使得索引樹需要經(jīng)常調(diào)整樹結(jié)構(gòu)。

接下來介紹在動態(tài)更新時索引樹是如何調(diào)樹結(jié)構(gòu)的。

a)R樹

R樹是B樹在高維數(shù)據(jù)上的拓展。它廣泛應(yīng)用在地理信息系統(tǒng)，地圖應(yīng)用和軌跡處理等領(lǐng)域中。R樹的每個節(jié)點的數(shù)據(jù)結(jié)構(gòu)可以用如下的方式表達。

MBR,Level,Data,Parent

在R樹中所有的索引對象存儲在葉節(jié)點中，即葉節(jié)點的索引項都是R樹的索引對象。非葉節(jié)點的索引項是該節(jié)點的子節(jié)點。在R樹中每個索引項被表示成它的MBR(最小外包矩形)。非葉節(jié)點的MBR是它所有索引項的MBR的最小外包矩形，即MBR的MBR。Level指的是當(dāng)前節(jié)點在樹中的高度。Data是每個節(jié)點的索引項。每個節(jié)點的索引項的數(shù)量有一個上界M和一個下屆m。m是M的兩倍，但葉節(jié)點的索引項的下界是2。Parent是當(dāng)前節(jié)點的父節(jié)點。另外，R樹是一顆完全平衡的樹，即所有葉子節(jié)點都在樹的最低層。

在R樹上執(zhí)行的查詢有兩種，一種是范圍查詢，另一種是K臨近查詢。范圍查詢指的是查找在一個指定空間區(qū)域內(nèi)所有的對象。K臨近查詢指的是查找距指定對象距離最近的K的對象。K臨近查詢可以轉(zhuǎn)換為范圍查詢。范圍查詢調(diào)用一個遞歸算法，這個算法的大致過程如下：第一，把根節(jié)點作為當(dāng)前節(jié)點；第二，當(dāng)前節(jié)點是非葉節(jié)點，把所有子節(jié)點的MBR與查詢區(qū)域的MBR相交的子節(jié)點先后作為下一個當(dāng)前節(jié)點繼續(xù)遞歸算法；第三，當(dāng)前節(jié)點是葉節(jié)點，若某個索引對象的MBR被包含在查詢區(qū)域的MBR中，就將這個索引對象添加到結(jié)果集中。

接下來介紹一下R樹的插入算法。插入算法的任務(wù)就是將一個索引對象插入到R樹中。它可以被表示成下面三個步驟：