[發明專利]一種超大規模數據的時序檢索索引系統及方法

有效

• 申請號: 201611160429.2
• 申請日: 2016-12-15
• 公開（公告）號: CN106777111B
• 公開（公告）日: 2020-08-11
• 發明（設計）人: 趙淦森;李振宇;王欣明;張海明;莊序填;唐華;李卓越;林成創;劉創輝;馬朝輝;廖智銳
• 申請（專利權）人: 華南師范大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 胡輝

本發明公開了一種超大規模數據的時序檢索索引系統及方法，該系統包括垂直層級索引模塊，包括有多層索引，每層索引均包括哈希函數和多個數據集，所述數據集中數據通過下一層級索引哈希函數映射至下一層級數據集中；還包括有對應的時間軸索引模塊，用于建立事件列表和時間列表。本發明通過層級索引模塊將原始的大數據集經過層層的哈希映射，最終會被分配到若干個相對較小的數據集中去，使每一個小數據集上可以獨立執行查詢處理、數據加載、存儲優化等操作，從而結合時間軸索引模塊避免了時序檢索操作的過程中進行全表掃描操作的風險，極大地提高了時序檢索的速度。本發明作為一種超大規模數據的時序檢索索引系統及方法可廣泛應用于數據處理領域。

技術領域

本發明涉及數據處理領域，尤其是一種超大規模數據的時序檢索索引系統及方法。

背景技術

時序數據庫的時序數據管理領域也涉及了對數據庫中的數據的時序檢索操作。時序數據庫內部也是通過對時序數據建立數據索引從而高效地實現各種時序數據管理的功能。總的來說，時序數據庫中的這些數據索引主要分成兩大類，一類是基于B+樹結構的索引，另外一類是基于R樹的結構的索引。比如Time Index,Snapshot Index,CheckpointIndex,Archivable Time Index,Overlapping B+樹等等幾類比較具體的索引結構。

Timeline Index是由Martin Kaufman等人在2013年提出的一種索引結構，它主要服務于時序數據庫里的時序數據管理，能夠極大地提升時序數據庫各種時序檢索的效率。

如圖1所示為時序數據庫中數據格式，參數Start和End表示數據記錄的有效時間的起止點，參數Name和Balance分別表示姓名和賬目。

如圖2所示，Timeline Index主要由圖中左邊的Version Map和圖中右邊的EventList兩個部分組成。圖1中的每條數據記錄可以拆分為兩個事件：在Start時刻記錄被激活；在End時刻記錄被撤銷。Event List記錄了所有的被激活和被撤銷的事件(1為激活，0為撤銷)。而Version Map記錄了所有事件發生的順序。通過對這兩個列表的操作，TimelineIndex能夠實現高效的時序檢索性能。

對于每張數據表，都需要建立一個對應的Timeline Index。Timeline index比原始的數據表要小很多，尤其是當原始數據表具有很多列屬性的時候。

上述提到了各種時序數據庫的時序索引都能夠有效地解決時序數據庫中的各種時序數據管理的問題，但是，它們有個共同的特點是它們都是為傳統的關系型時序數據庫而設計的，它們所面向處理的是常規規模的數據量，通常為幾百萬級別的數據，它們無法應對當前大數據時代10億以上級別的超大規模數據所帶來的技術挑戰。當待處理的數據集的數據總量越來越大，上述的時序數據庫的時序索引就會出現嚴重的性能和效率問題，導致無法在可接受的時間內返回有效的時序檢索的結果。

術語解釋

標準化時序數據：R＝(ID,A,T,(S,E))是一條標準化時序數據；其中ID表示記錄R在數據表中的行號，A表示時序數據本身的靜態屬性，T表示時序數據的時間點屬性，(S,E)表示時序數據的真實有效時間范圍[Start,End)。

靜態屬性：靜態屬性是指在時序數據中所有與時間無關的屬性。

時序檢索：在原始標準化時序數據集中檢索滿足特定時間約束的數據記錄。時序檢索主要包含三類：基于時間點條件的檢索操作，基于時間段包含關系條件的檢索操作和基于時間段相交關系條件的檢索操作。

基于時間點條件的檢索操作：給定具體的時間點M，找出全集U中的最大子集合D，使得D滿足，且

基于時間段包含關系條件的檢索操作：給定具體的時間范圍[Start,End)，找出全集U中的最大子集合D，使得D滿足，且