前綴立方的結(jié)構(gòu)化索引.pdf

1、前綴立方是最近提出的一種數(shù)據(jù)立方結(jié)構(gòu)，它利用前綴共享和基本單元技術(shù)，在濃縮數(shù)據(jù)立方的基礎(chǔ)上進一步消除了數(shù)據(jù)小方內(nèi)的前綴冗余，從而進一步減小了數(shù)據(jù)立方的尺寸。由于對數(shù)據(jù)立方的任一范圍查詢事實上均可最終歸結(jié)為針對其中特定數(shù)據(jù)小方的范圍查詢，所以前綴立方仍然按數(shù)據(jù)小方聚簇，在每一個數(shù)據(jù)小方內(nèi)，立方元組按照共享維值進行聚簇，并且通過共享前綴形成分組結(jié)構(gòu)。 由于分組結(jié)構(gòu)的存在，前綴立方不能沿用濃縮數(shù)據(jù)立方的索引，必須為它尋求一種新的索引機

2、制。研究工作者最近提出了前綴立方的一種索引機制Prefix-CuboidTree。它結(jié)合C-曲線和B-Tree索引結(jié)構(gòu)成功地對前綴立方進行索引。該索引范圍查詢算法采用深度優(yōu)先的策略，通過查詢點跳躍減少了I/O代價。 現(xiàn)實世界中的數(shù)據(jù)往往都是非均勻分布的，所以在整個數(shù)據(jù)空間中大部分空間是未為利用的死區(qū)。怎樣避免對死區(qū)的查詢成為提升索引的查詢性能至關(guān)重要的問題之一。而Prefix-CuboidTree并沒有考慮到這個問題，因此，基于

3、BUB-Tree和R-Tree索引技術(shù)得到了前綴立方的一種新的索引機制Bound-CuboidTree。它在每個數(shù)據(jù)小方內(nèi)以Z-順序保持分組的空間臨近性，然后使用BUB-Tree對每個數(shù)據(jù)小方進行索引，減少了范圍查詢時的死區(qū)，提高了查詢效率。同時參考R-Tree生長機制，通過選取插入后索引節(jié)點表示范圍的增量最少的那個索引節(jié)點進行插入，成功解決了BUB-Tree不能在索引節(jié)點的Z-曲線編碼范圍是連續(xù)且不相交的情況下使用的問題。在此基礎(chǔ)上提