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

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

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

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