一種基于Spark的分布式時態索引方法

鄭曉東 王 梅 陳德華 張碧瑩

(東華大學計算機科學與技術學院 上海 201620)

0 引 言

大數據時代已然來臨。時間作為客觀事物的固有屬性，幾乎所有信息都顯式或隱式地具備時態特征。大數據的產生往往也是經過時間累積形成，因此大數據也被理解為針對某個對象在時空兩個維度上的“全息”數據。若對數據進行時態的關聯分析，有望挖掘出數據的巨大價值，從而使得研究和使用數據的“時態”信息意義日顯突出，對時態數據管理查詢技術的研究十分迫切。

在考慮數據的時態信息時，被打上時間標簽的數據，會伴隨著時間的延伸而生效或失效。因此，對于一個實體來說，它會擁有多個數據記錄，很明顯傳統默認時間點的靜態“快照”式數據存儲模式難以滿足時態查詢需求。一些時態數據庫模型被相繼提出，如TimeDB[1]等。與此同時，Oracle、IBM DB2[2]、SAP HANA[3]等知名的商業數據庫也開始支持一些簡單的時態查詢功能，包括時間旅行，時態聚合以及時態連接等。以時態連接為例，檢索“在相同時間點中，兩個銀行賬戶數據表中存款相同的客戶存款額度”，需要在時間以及對象兩個維度上進行雙向篩選，如何在龐大的數據集進行快速、高效的時態操作執行成為一個十分有挑戰性的問題。

索引是數據庫中加速查詢的有效技術。為此，研究者從不同角度為時態數據模型提出了多種時態索引技術。文獻[4]提出的基于B+樹Time Index索引以及文獻[5]中提出的Historical R樹索引對傳統樹型索引進行擴展已支持時態數據，文獻[6]針對時態XML數據，構建不同的時態索引模型以支持時態查詢。近來，SAP HANA提出的Timeline索引[7]以及雙時態索引技術[8]采用順序結構實現高效的時態查詢。然而，目前所設計的大部分索引均在單機環境下實現，當數據集規模較大時，上述方法將花費較高的代價在遍歷龐大的索引樹或索引隊列上。同時，其索引結構和查詢算法的執行效率對機器性能的要求極高，以支持SAP HANA的Timeline時態索引為例，其執行默認的機器內存達192 GB[7]。上述問題極大地限制了索引技術的普遍應用和查詢效率的提升。

在數據規模不斷增長的今天，越來越多的應用都是基于存儲在分布式系統中的大規模數據。Spark分布式處理框架通過將海量數據分發至各個計算節點，并基于彈性數據集RDD及MapReduce技術極大地加快了數據的處理速度[9]。然而該框架中并沒有對hdfs中文件的行級記錄進行索引，本文基于Spark分布式計算平臺設計并實現了一種分布式時態索引方法。該方法首先提出時態數據集的分段索引構造策略，進一步設計基于Spark的時態索引構建方法及基于Spark RDD的并行查詢策略。本文主要內容如下：

1) 以Timeline索引為例，提出時態索引在Spark集群上的構建方法，設計分布式時態索引的并行查詢框架。根據時態查詢所涉及的Spark RDD分區模式的不同，將其分為分區獨立查詢，跨區查詢以及跨段查詢，并對不同模式的時態查詢提出了優化的分布式查詢算法，提高查詢效率。

2) 優化輔助索引結構，加快“給定時間點查詢”這一原子操作的效率，從而極大地提升時態聚合，時態旅行等分區獨立查詢的查詢效率。進一步針對跨RDD分區及跨段的時態連接復雜查詢，分別設計復合索引結構輔助查詢，確保本文方法對數據規模的有效自擴展性同時降低集群硬件配置需求。

3) 在基準數據上，進行本文所提方法的有效性驗證，證明了本文提出的索引策略的實用性和高效性。

1 相關工作

1.1 時態索引

傳統數據庫中索引技術是提高查詢效率的關鍵技術之一，同樣對于時態數據，合適的索引結構將有效地支持時態操作。時態數據索引大致可歸為兩類：樹索引和隊列索引。最早提出的時態數據索引結構Time Index就是基于B+樹構建的，該索引針對每個時間間隔的結束時刻作為索引值建立B+樹，每個葉子結點記錄該時間點各事件的生效失效狀態[4]。但是該索引在時間跨度較大的情況下會引起較大的空間開銷，同時這種基于B樹的時態索引在構建時依賴于數據的時間有序性。另一種樹形結構R樹雖然最初的設計思想是為了索引空間數據，但是它被用來存儲時間同樣適合。文獻[5]提出了Historical R樹，每個時間戳都建立一個R樹，且一個Historical R樹中未發生變化的記錄對應的結點只保存一個以節省空間。同時，除了這種以單一一個數據結構來索引全部數據外，還有以樹形結構為基礎，為每一個時間版本構建一個樹來索引時態數據的方法，如MVBT索引[10]和MV3D-RT索引[11]。相對于樹形時態索引，基于隊列的時態索引研究較少，文獻[7]提出了Timeline時間線索引，該索引應用于HANA，在內存中為時態數據建立一張時態表，每一個時態表對應一個Timeline時間線索引，在時間線上保存著各個數據的生效失效時間，該索引支持多種時態操作。

目前對于時態數據的操作主要分為時間旅行，時態聚合和時態連接。時間旅行是查詢數據在過去或未來某個時間點或時間段所具有的狀態，可以通過時間旅行回溯到某個時間版本的數據庫狀態。時態聚合和時態連接都是基于時間旅行所進行的操作，時態聚合是指對某個時間點或時間區間的有效記錄進行聚合操作。時態連接是指對指定時間點下的有效記錄進行連接操作。如今對于時態索引的研究還處于一個發展階段，現階段已提出的時態索引大多數僅僅支持有限的時態操作，部分更是僅支持時間旅行，無法有效地支持時態聚合和時態連接等復雜查詢操作。

1.2 分布式索引

分布式計算框架如Spark、Hadoop，采用的是分布式的文件系統，通過將大文件進行分片，切分成多個分片文件存儲在多個存儲節點上。平臺在需要對該文件數據進行計算時，各個分片文件加載至多個計算節點上進行獨立計算，計算子結果將返回主節點進行后續操作。這種存儲計算模式雖然解決了大數據計算處理的效率問題，但是在對數據文件進行行級訪問時，盡管數據文件的切分且分布式的讀取加快了讀取速度，其大量的時間浪費在了文件的尋道遍歷上。Haojun Liao提出了應用在Hadoop的分布式文件系統上的多維索引，考慮到HDFS中塊大小、索引節點大小、網絡中的數據通信等影響查詢速度的因素，通過構建類似于R樹的層次結構索引，避免查詢時無意義的窮舉減少查詢響應時間[12]。Gankidi等[13]提出通過構建B+樹管理HDFS數據，索引維持在SqlSever中，用戶可以通過SQL查詢HDFS數據。Xie等[14]提出建立在Spark平臺上用于管理空間數據的兩級索引結構，該索引維持在RDD中，區域索引保存空間區域中的數據信息，而全局索引管理著每個區域索引的邊界信息。

總的來說，現有的時態索引技術尚處于研究階段，大多數索引結構無法有效地支持時態操作，并且在面對大規模時態數據時，索引空間代價較大，效率變低，而傳統的分布式索引大多是面向隱性時間屬性數據，無法有效地支持對歷史信息的相關操作。

2 基于Spark的時態索引

2.1 定義和符號

定義1時態表(Temporal Table)。包含具有時態屬性的數據的表。

定義2時間區間(Period)。表示一個數據合法持續的時間，包括它的開始和結束。本文使用包含-排除方法來建模時間區間，使用[start, end)來表示。在實現過程中分別通過時態表的兩列來分別表示記錄的開始時間和結束時間。

定義3時間版本(versionID)。指時間區間內離散的時間點，這些時間點是單調遞增的，本文將這些時間點稱之為versionID。

表1給出了一個時態表的例子。該實例模擬了一個銀行系統，Alice在101時間點在銀行存入＄100，Alice在銀行的存款為＄100這個狀態在數據庫中維持到了103時間點，即103時間點后(包含103時間點)第一條記錄失效，第四條記錄生效，表明Alice在103時間點在銀行存入＄500使銀行的存款到達＄600。同理，Ann在102時間點在銀行存入＄500，第二條記錄在102時間點到107時間點有效，第三條記錄表示Grace在103時間點在銀行存入＄300，直到目前為止，Grace在銀行的存款都為＄300。

表1 時態表

2.2 索引結構

不論是基于樹結構或是順序結構的時態索引，均需在其索引結點中記錄各時間點下事件的生效失效狀態。以圖1(a)給出的Timeline索引結構為例，其中“+”表示該數據在對應時間版本下開始生效，“-”表示數據失效。上述索引可以有效地支持多種時態操作，然而其也存在著明顯的缺陷。在執行時態操作時，由于索引只保存了各個記錄的生效失效狀態，如果要獲取到某一時間版本下的有效數據，如查詢“106時間版本下的有效數據”，系統無法避免地需要從頭遍歷事務層至查詢時間版本，以得到“106時間版本下第二條記錄及第五條記錄有效”的信息。每一次的時態操作都會重復性的遍歷索引，這種低效的重復性工作造成了極大的時間代價。

圖1 checkpoint結構

因此，在Timeline時態索引中，同時維護檢查點(checkpoint)輔助索引結構。checkpoint中保存了當前時間下所有記錄的有效狀態，這種類似于快照的設計結構省去了在每次時態操作時需要從頭遍歷時間線索引所引起的大量開銷，可以較為快速地獲取指定時間版本下的有效記錄，對于優化索引的檢索效率至關重要。由于checkpoint的創建代價較大，一般在一個較大的時間間隔下創建一個新的checkpoint結構。

2.3 基于Spark的分段時態索引框架

Spark上的所有數據操作都依賴于彈性分布式數據集(RDD)，RDD被分布式的存儲在集群的各個節點上，程序方能分布式的執行。給定當前時態表T，由于時態表中數據是以時間特性排序的，為了保證各分區中數據的時態均衡性，應用Spark自帶Hash Partition方法針對ROW_ID列進行哈希劃分，從而得到RDD的各個分區。各RDD迭代本分區數據并行創建索引，因此RDD類型為一個二元組(TT，TI)，其中TT即Temporal Table是本數據分區中的時態表，TI即Temporal Index是針對于本分區時態數據構建的時態索引。很明顯，隨著時間推移，時態表T中的數據不斷累積。為保證本文方法對數據規模的有效自擴展性。同時，為了避免當數據增大，RDD在進行迭代計算時產生的內存溢出問題，首先將數據進行切分。給定當前時態表T={t1,t2,tn}，n為數據記錄條數，將其切分為T={T1,T2,Tm}，m為數據段個數。對每個數據段Ti按如上所述方法構建索引，通過設定m的大小以控制各段RDD的大小。同時，在Spark集群中維持全局索引來調度對應查詢時段所涉及的各數據段索引RDD進行相關查詢操作。

3 基于索引的時態查詢執行

時態數據的查詢操作可分為時間旅行、時態聚合、時態連接三種時態操作。根據操作所涉及的Spark RDD數據對象，本文將查詢分為分區獨立，跨區查詢，跨段查詢，如圖2所示。并且對于每類查詢，本文均針對性地提出優化的輔助索引結構及查詢算法，以充分發揮分布式的優點，提高時態檢索效率。

圖2 構建在Spark集群上的時態查詢分類

3.1 分區獨立查詢

本文將時態索引構建在Spark集群中的RDD上，當集群讀取至RDD上后，各個分區根據分區數據構建本分區索引。分區獨立查詢即指各個分區數據之間不必進行通信，各個分區在檢索完本分區索引后直接返回結果集。

在幾種時態操作中，時間旅行屬于典型的分區獨立型查詢。時間旅行是查詢某一時間版本versionID下數據庫記錄的狀態信息，也就是得到該時間版本數據庫的有效數據集。以時間旅行為例，詳細描述分區獨立查詢在Spark集群的執行流程：在獲取到待查versionID后，IndexRDD各分區索引先檢索本分區的checkpoint集合，獲取到最鄰近且早于查詢時間版本的checkpoint，根據checkpoint中的標志位查詢對應行向量分段數據，獲取到該時間版本下的有效數據。若checkpoint的時間版本和查詢時間相同，該分區即可返回結果集；若與查詢時間不等，則根據checkpoint的時間版本在時態索引中的位置信息接著向下遍歷時態索引，直到遍歷至查詢時間在時態索引中的位置，整合計算得到該分區的有效數據集后返回給驅動節點。

傳統的checkpoint結構需要遍歷行向量來查看對應時間版本的數據庫狀態，由于checkpoint中會存儲和時態表同等大小的行向量，若設時態表大小為n，其遍歷次數為n。然而由于數據的時效性，在給定時間版本下同一對象的時態數據只有一條是生效的，且有效數據具有區域性(即一個時間版本下的有效數據大多會集中在行向量的一個分段內)，造成大量的無效遍歷。為此，本文首先利用Spark 分布式和并行處理特點，對checkpoint結構進行優化，即對checkpoint中行向量進行固定長度的分段，并添加記錄各分區有無有效記錄的標記flag結構。如圖3所示，checkpoint分為標志位和有效數據位兩部分，在有效數據部分按行號分段，并在標志位增設標志，記錄該分段在指定時間版本下是否存在有效的行號。在具體查找時，即可根據標志位大量過濾無效記錄。

圖3 優化checkpoint

優化checkpoint中的分段標志位簡化了遍歷復雜度，分段標志位為真再去遍歷對應分段數據的有效性，若為假則直接跳過該分段。假定分段步長為l，則時間復雜度近乎簡化為(n/l+l)，且各個分段可并行遍歷，極大地降低獲取checkpoint下有效數據的時間開銷。同時，由于數據記錄隨時間的累計特性，在下一個時刻點對checkpoint創建時，僅需追加新增段，原有分段可重用，大大降低了checkpoint的創建復雜度。

3.2 跨區查詢

跨區查詢涉及到存儲索引信息的RDD各分區數據間的通信，各分區間需要進行聯合計算。時態連接就是最為典型的跨區查詢，時態連接在時態操作中是一種較為復雜的操作，同時涉及到時間維度和對象維度的連接操作，如查詢“在相同時間點中，兩個銀行賬戶數據表中存款相同的客戶存款額度”。上述時態連接可以劃分成兩個階段，第一個階段利用時態索引以及checkpoint得到每個時間版本下兩個數據集各分區的有效記錄集合；第二個階段是在相同查詢點的有效記錄集合中，根據查詢條件以一定的連接規則對兩個數據集的有效記錄進行連接以得到查詢結果。通過改進checkpoint結構雖然加快了第一階段獲取當前時間版本下有效記錄的速度，但第二階段低效的兩兩條件匹配付出了O(n2)的時間開銷，盡管將索引應用在Spark集群，采用分布式的計算方法加快了匹配速度，但是存在集群中節點相互通信、數據拉取等問題，Spark集群上的時態連接速度并不理想。

針對于時態連接過程中出現的低效的兩兩匹配以及大量p的數據通信問題，本文采用面向對象維度的輔助索引來優化時態連接效率。如圖4所示，在通過第一階段獲取到有效記錄后，在時態連接的第二階段，各個數據節點不再進行數據廣播，而是采用將全部有效數據進行混洗重分區，以各個記錄的對象維度字段為key值進行hash混洗重分區，因此新的數據分區具有封閉性。即將連接的記錄限制在本地分區，不用再進行數據通信來進行連接，這樣的輔助索引結構不僅減少了數據通信引起的極大開銷，而且縮減連接次數，提高了時態連接效率。具體的連接算法如算法1所示。

圖4 優化后的時態連接查詢過程

算法1時態連接

輸入：versionIDRange時間版本范圍，joinCondition連接條件；

輸出：Result查詢結果集；

1．for versionID_i in versionIDRange

2．RA,RA←temporalTravel(versionID_i);

/*時間旅行獲取數據表的有效記錄*/

3．Repartition(RA) and Repartition(RB);

/*以對象維度對RA和RB重分區*/

4．for partitionA in RA

5．for partition in RB

6．if partitionA.partitionNum==partition.partitionNum

7．Result←Join(partitionA,partitonB)；

/*擁有分區號相同的RDD進行連接*/

8．end if

9．end for

10．end for

11．end for

3.3 跨段查詢

Spark集群的一切操作都是基于RDD的。在根據數據集構建索引時，RDD需要將所有數據都讀進內存進行迭代計算，由于集群節點可以申請到的內存是有限的，當分區數據的計算量到達節點上限時就會內存溢出導致計算失敗，為了避免這種情況，我們采用跨段的查詢方式。

跨段查詢就是對大數據進行分段處理，各個分段獨立構建索引，將分段數據集及索引打包存儲至HDFS?？紤]到時態數據具有時效性，每一個數據集同樣有一個時效性，數據集中記錄最早的有效時間以及最晚的失效時間即為該數據集的時間跨度。將時間跨度的相關信息設計到索引結構中將有效地加快查詢速度，避免遍歷過多的時間相錯的數據集。因此，本文設計雙hash結構來索引HDFS中的相關的索引文件，當執行時態操作時，由全局索引調配符合時間跨度的數據集及索引至Spark集群進行后續操作。

如圖5所示，全局索引包括索引表和索引矩陣兩部分，索引表保存各個索引結構的存儲號、時間跨度，以及HDFS中的存儲地址。索引矩陣將各個索引結構的存儲號保存到對應時間跨度的塊中，索引矩陣的橫縱坐標為索引文件跨度的對應的hash值，橫坐標為開始時間，縱坐標為失效時間。

圖5 全局索引

當進行時態操作時，先訪問全局索引的索引矩陣，根據時態操作的時間字段查詢矩陣的對應區域，獲取到與操作時間有交錯的索引的存儲號。再根據存儲號在索引表中查詢到其數據及索引在HDFS中的儲存地址，Spark集群逐一加載涉及到的數據集和索引至內存中執行時態操作，最后將結果集進行合并即為查詢結果。如“查詢時間為2 005至3 078各個時間點的數據庫信息”，索引矩陣以1 000個時間版本為步長，邊長6為例，則計算其開始結束的hash值為2和3，根據hash值訪問索引矩陣的對應區域(即藍色陰影標注區域)得到有時間交錯索引的存儲號，即可檢索對應索引表找到其HDFS地址。

跨段查詢算法如算法2所示，其中getHashCode(versionID)為計算時間的哈希值；serachIndexMartix(hashCode,indexMartix)為掃描索引矩陣，獲取對應位置的索引塊號。judgeTimeRegion(item,querytime,indexTable)為檢索索引表，獲取時間區域有重疊的索引塊號。之后調用readIndexFromHDFS(path)從HDFS中讀取時態索引，進而進行時間旅行temporalTravel(temporalIndex,versionID)得到查詢結果。

算法2跨段查詢

輸入：versionID時間版本，indexMartix索引矩陣，indexTable索引表；

輸出：Result查詢結果集；

1．hashCode←getHashCode(versionID);

2．I←searchIndexMartix(hashCode);

3．For otem in I

4．P←judgeTimeRegion(item,versionID,indexTable);

5．End for

6．For path in P

7．temporalIndex←readIndexFromHDFS(path);

8．Result←temporalTravel(temporalIndex,versionID);

9．End for

3.4 索引更新

時態數據是帶有時間屬性的，這種特性也預示著時態數據會隨著時間不斷地增加，集群需要在新數據上添加索引以加快訪問速度，并且集群無法將不斷增大的數據及索引都維護在Spark集群中，需要一個索引的更新管理策略來控制Spark讀取對應時間點或時間段所涉及的索引結構。時態數據的時效性特點導致了時態記錄存在時間跨度且這種時間跨度是無法預料的，集群無法預知同一個對象所產生的下條記錄的時間跨度長短。如果將新產生的時態記錄索引到原有的索引結構中，需要在索引結構中進行頻繁的隊列移動，將新的索引節點插入到對應位置，并且這種插入式的方法無法批量操作，索引只允許逐一的進行插入，這種低效的更新策略是無法滿足當今的查詢需要的。

由于將新的時態數據索引到原有索引結構上這種索引更新策略所引起的時間開銷要大于直接重構索引，本文擬采用滯后更新的索引更新策略。原有索引不去索引新的數據，而是當新的數據積累到一定量時，對新數據單獨構建索引結構。

4 實驗與結果

為了證明在Spark集群上構建時態索引的高效性，本節進行了以下幾個方面的實驗：(1) 在Spark集群環境下利用優化的checkpoint和原始checkpoint性能對比；(2) 在Spark環境下時態連接的性能效率；(3) 在Spark環境下分段索引性能分析。

4.1 實驗環境

本次實驗中Spark部分試驗是在是由5臺機器構成的Spark on standalone集群系統上完成的，1個master節點和4個slave節點，各節點CPU為Intel(R) Core(TM) i7-3770 CPU @ 3.40 GHz，6 GB內存空間，采用CentOS 6.8系統，Scala版本為2.11.8，Spark版本為2.0.0。

4.2 實驗數據集

本實驗在TPC-H基準數據集的基礎上擴展時態屬性，并通過TPC-C事務生成基準數據集的歷史數據[15]。本實驗采用數據集如表2所示。

表2 實驗數據集

其中，SF_0為TPC-H生成數據的比例因子；SF_H為TPC-C生成數據的比例因子，即數據集中時間版本的規模；lineitem表示數據集的總行數，version表示時間版本規模。

4.3 實驗結果與分析

4.3.1 checkpoint優化前后性能對比

為了規避時態操作時分段查詢干擾checkpoint性能判斷的問題，本實驗在小型數據集基礎上對比checkpoint優化前后的性能變化，確保數據在一個數據段中。實驗中查詢給定versionID的數據庫有效記錄。實驗結果如圖6所示，圖中橫坐標為查詢的versionID。

圖6 checkpoint優化性能對比

圖中查詢時間隨著查詢時間版本的增長出現折現波動，這是因為checkpoint保存了對應時間版本下的數據庫狀態，無需遍歷索引，而兩個checkpoint中的時間版本數據庫狀態需要遍歷時間線索引的對應區間，所以在checkpoint時間點上查詢時間突然下降，查詢兩個checkpoint間的時間版本數據庫狀態查詢時間是線性增長的。實驗結果表明，優化后的checkpoint相對于原始checkpoint結構在時態旅行上提升40%左右。由于優化后的checkpoint將visible rows分段，并添加對應的標識位，減去了不必要的遍歷的時間，這對于查詢性能的提升是顯著的。并且當數據集變大時，checkpoint中需要保存的記錄號變多了，則利用checkpoint進行時態操作時的遍歷量變大，而優化的checkpoint規避了這種遍歷所引起的時間開銷，也就是說數據量越大時，優化的checkpoint對于性能的提升越明顯。

4.3.2 跨區查詢時間開銷

實驗結果如圖7所示，優化后連接算法的執行效率要明顯由于原有連接算法。進行連接優化后，時間開銷隨連接記錄數增加呈線性增長，而未優化的連接算法呈幾乎指數級的增長態勢。在連接量較少時，原有連接算法略優于優化算法，這是因為數據混洗引起的時間開銷高于優化的時間代價。而連接的記錄數越多，優化的連接算法優勢越大，其原因主要在于未優化連接操作低效地兩兩連接，而優化后連接算法通過hash成功規避了低效連接操作，縮小了連接范圍。

圖7 跨區查詢性能對比

4.3.3 跨段查詢時間開銷

實驗結果如圖8所示，在四次不同時間版本跨度的查詢中，有三次查詢的耗時在5秒左右，只有最后一次查詢的時間開銷為10秒，這是因為前三次范圍查詢只涉及一個數據段，最后一次范圍查詢涉及到了兩個數據段。Spark集群將時態數據分段構建索引，在進行時態操作時，集群首先查詢全局索引，將時態區間與查詢時間版本有交叉的索引文件逐一從HDFS讀入Spark集群進行查詢。同時，由實驗數據可知，在進行范圍查詢時往往只涉及到一至兩個數據段，這是因為數據本身的時態特性就決定了數據本身在時間維度上是聚集連續的，在進行時態范圍查詢時只涉及到少數的數據段。因此，分段查詢在解決了數據量過大無法構建索引問題的同時，還保證了查詢的效率。

圖8 跨段查詢時間開銷

5 結 語

本文針對現有時態索引在數據量過大，普通硬件環境難以支持的問題，基于時態數據的特性，提出基于Spark的分布式時態索引方法。該方法在Spark集群上按數據分區單獨構建時態索引，在此基礎上優化輔助索引checkpoint結構，設計面向對象維度的輔助索引以及全局雙hash結構，全面高效地支持各種時態查詢操作。最后，通過基準數據集上的實驗驗證了所提方法的有效性。目前本文所實現的Spark時間索引是在離線數據的基礎上，在接下來的研究中，我們準備實現實時監控的流式構建時態索引系統，并進一步優化在跨區查詢時面對大量混洗數據的查詢算法。

參 考 文 獻

[1] Yong Tang.TimeDB-A Temporal Relational DBMS[OL].[2015-03-05].http://www.timeconsult.com/software/software.html, 1999.

[2] Saracco C M,Nicola M,Gandhi L.A matter of time:Temporal data management in DB2 10[R].Technical report,IBM,2012.

[3] Kaufmann M,Fischer P M,May N,et al.TPC-BiH:A Benchmark for Bitemporal Databases[M]//Performance Characterization and Benchmarking.Springer International Publishing,2013:16-31.

[4] Elmasri R,Wuu G T J,Kim Y J.The time index:An access structure for temporal data[C]//Proceedings of the 16th International Conference on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann Publishers,1990:1-12.

[5] Tao Y,Papadias D.Efficient historical R-trees[C]//Scientific and Statistical Database Management,2001.SSDBM 2001.Proceedings.Thirteenth International Conference on.IEEE,2001:223-232.

[6] Zhang F,Wang X,Ma S.Temporal XML Indexing Based on Suffix Tree[C]//Acis International Conference on Software Engineering Research,Management and Applications.IEEE,2009:140-144.

[7] Kaufmann M,Manjili A A,Vagenas P,et al.Timeline index:a unified data structure for processing queries on temporal data in SAP HANA[C]//ACM SIGMOD International Conference on Management of Data.ACM,2013:1173-1184.

[8] Kaufmann M,Fischer P M,May N,et al.Bi-temporal Timeline Index:A data structure for Processing Queries on bi-temporal data[C]//IEEE,International Conference on Data Engineering.IEEE,2015:471-482.

[9] Zaharia M,Chowdhury M,Franklin M J,et al.Spark:cluster computing with working sets[C]//Usenix Conference on Hot Topics in Cloud Computing.USENIX Association,2010:10-10.

[10] Becker B,Gschwind S,Ohler T,et al.An asymptotically optimal multiversion B-tree[J].The VLDB Journal,1996,5(4):264-275.

[11] Tao Y,Papadias D.MV3R-Tree:A Spatio-Temporal Access Method for Timestamp and Interval Queries[C]//VLDB 2001,Proceedings of,International Conference on Very Large Data Bases,September 11-14,2001,Roma,Italy.DBLP,2001:431-440.

[12] Liao H,Han J,Fang J.Multi-dimensional Index on Hadoop Distributed File System[C]//International Conference on Networking,Architecture,and Storage,Nas 2010,Macau,China,July.2010:240-249.

[13] Gankidi V R,Teletia N,Patel J M,et al.Indexing HDFS data in PDW[J].Proceedings of the VLDB Endowment,2014,7(13):1520-1528.

[14] Xie D,Li F,Yao B,et al.Simba:Efficient In-Memory Spatial Analytics[C]//International Conference on Management of Data.ACM,2016:1071-1085.

[15] Funke F,Kemper A,Krompass S,et al.Metrics for measuring the performance of the mixed workload CH-benCHmark[C]//Tpc Technology Conference on Topics in PERFORMANCE Evaluation,Measurement and Characterization.Springer-Verlag,2011:10-30.