時態(tài)數(shù)據(jù)索引技術(shù)(數(shù)據(jù)庫)

時間：2022-11-11 10:30:01 | 來源：信息時代

時間：2022-11-11 10:30:01 來源：信息時代

    時態(tài)數(shù)據(jù)索引技術(shù) : 支持事務時間和有效時間的一種索引技術(shù)。傳統(tǒng)索引(例如B⁺-樹)采用單值數(shù)據(jù)、線性的索引技術(shù),時態(tài)數(shù)據(jù)索引則是非線性的、多維的索引技術(shù)。在建立數(shù)據(jù)的線性索引的同時,需要建立相應的事務時間和有效時間維索引。
時間是分區(qū)段的、非單值的,采用傳統(tǒng)的索引技術(shù)存儲時態(tài)數(shù)據(jù),會導致元組的時間區(qū)間要被分割成幾塊,并映射到不同的索引頁上,這會產(chǎn)生重疊問題,降低檢索效率。時態(tài)索引除了需要考慮其分頁和數(shù)據(jù)聚簇之外,還需要考慮其他問題,如數(shù)據(jù)的查詢方式對時態(tài)索引的影響,例如對時間的點切片查詢很有效率的索引,可能降低對數(shù)據(jù)值的點查詢效率。隨著時間的推移,數(shù)據(jù)增量巨大,可能需要遷移到其他存取介質(zhì)上,存取介質(zhì)的變化也會導致索引結(jié)構(gòu)的變化。
1.支持事務時間的索引技術(shù)
根據(jù)不同的數(shù)據(jù)聚簇方式,事務數(shù)據(jù)庫索引技術(shù)可以分成三種類型: 按鍵索引、按時間索引和按鍵-時間索引。
1982年,Ben-Zvi等人提出了反向鏈(reverse chaining),并由Lum等人于1984年改進了該方法,這是一種按鍵索引技術(shù),它將當前狀態(tài)的數(shù)據(jù)跟歷史數(shù)據(jù)分開存儲。因為當前狀態(tài)下的數(shù)據(jù)被查詢的多,因此能縮小查找結(jié)構(gòu),提高查找速度。每個鍵的所有版本按照其事務時間的降序排列成一條鏈,按不同的鍵形成了多條時間鏈。在此方法中當前狀態(tài)的數(shù)據(jù)用傳統(tǒng)的B+樹做索引。歷史數(shù)據(jù)可以從當前鍵開始回溯而得到。
Gunadhi和Segev提出的AP-樹(appended-only tree)是一種按時間索引方法。AP是樹是一種ISAM索引和B⁺-樹相結(jié)合的多路搜索樹。每一個元組被賦予一個[起始時間,結(jié)束時間]的時間區(qū)間,并在起始時間上作索引。每個葉子結(jié)點用(t,b)表示,其中t表示時間,b是指針,指向其對應的桶,桶內(nèi)是一些元組的集合: 它們的起始時間比其前一個元素的起始時間晚的,而且比t早或跟t相等;每個非葉子結(jié)點的則指向下一層。其更新操作的復雜度為O(1)。
2.支持有效時間的索引技術(shù)
歷史數(shù)據(jù)庫必須維護數(shù)據(jù)時間屬性的動態(tài)變化。Kanellakis等人提出了Metablock樹,實現(xiàn)了對數(shù)據(jù)有效時間動態(tài)變化的管理。Metablock樹是B維的索引方法,它把二維時間空間的上半部分劃分為多個小塊,每個小塊有B²數(shù)據(jù)點。但是Metablock樹是個半動態(tài)的結(jié)構(gòu),因為只支持時間區(qū)間的增添而不支持刪除。
3.雙時態(tài)數(shù)據(jù)庫索引技術(shù)
在雙時態(tài)數(shù)據(jù)庫中比較有代表性的索引是R-tree,GR-tree,4R-樹。
(1) R-tree時態(tài)索引技術(shù):R-樹最早由Auttman在1984年提出,其后又有了許多變形,形成了由R-樹、R⁺-樹、R^*-樹、HilbertR-樹、SR-樹等組成的R-樹系列空間索引。R-tree是一種空間索引技術(shù),為空間搜索提供了一種合適的數(shù)據(jù)結(jié)構(gòu),以提高搜索速度。R樹空間索引技術(shù)的核心是:根據(jù)搜索條件(一個矩形)迅速找到與該矩形相交的所有空間對象集合。當數(shù)據(jù)量巨大,矩形框相對于全圖很小時,這個集合相對于全圖數(shù)據(jù)集大為縮小,在這個縮小的集合上再進行各種復雜的搜索,可以減少IO操作,大大提高查詢效率。
(2) GR-tree時態(tài)索引技術(shù): 通常的R-tree綁定的矩形框是固定不變的,不能用于含有now和UC等時間變元的時態(tài)索引,為了解決此問題,擴充一般的R-tree使其可處理帶變元的時態(tài)數(shù)據(jù),稱之為GR-tree。在GR-tree的層次上使用變量now和UC,就可以在葉子結(jié)點上確切的記錄時間域的幾何關(guān)系,根據(jù)有效時間和事務時間的終止值是固定的還是可變的可將雙時態(tài)域分為四種類型。相應的雙時態(tài)域?qū)鲩L矩形、固定矩形、增長樓梯形和固定樓梯形。
(3) 4R-tree時態(tài)索引技術(shù):應用GR-tree能使時態(tài)數(shù)據(jù)的檢索速度提高,其不足之處是現(xiàn)有的數(shù)據(jù)庫管理系統(tǒng)內(nèi)核暫時還不能處理這種帶變元的索引方法,而4R-tree就很好地解決了這個問題,它通過變換將不同的變元轉(zhuǎn)化成不同固定值,將GR-tree樹分別映射到四種不同形式的R-tree再利用R-tree索引,對于查詢中的變元也采用同樣的方法有效解決了GR-tree不能應用于實際的不足。4R-樹索引由4個R-樹組成,索引過程比較復雜。