面向云計算的多維數(shù)據(jù)索引研究.pdf

1、云計算技術(shù)的廣泛應(yīng)用使數(shù)據(jù)呈現(xiàn)出爆炸式增長的趨勢，對傳統(tǒng)的數(shù)據(jù)管理技術(shù)提出了新的挑戰(zhàn)?，F(xiàn)有的云存儲系統(tǒng)普遍采用分布式哈希表的形式存取數(shù)據(jù)，這種基于key-value的模型在單維度查詢時可以獲得較高的訪問效率，但是對多維度查詢的支持不足。當用戶提交基于多個屬性列的多維查詢時，由于缺乏有效的二級索引系統(tǒng)的支持，需要運行MapReduce任務(wù)掃描整個數(shù)據(jù)集，從而使查詢效率降低。因此，近年來云存儲輔助索引成為學術(shù)界研究的熱點，相關(guān)成果陸續(xù)發(fā)表在

2、數(shù)據(jù)庫領(lǐng)域國際頂級會議和頂級期刊上。
　　本文對云計算環(huán)境下的多維數(shù)據(jù)索引技術(shù)進行研究。論文工作分別從云存儲系統(tǒng)中的多維數(shù)據(jù)索引、基于主從結(jié)構(gòu)的雙層多維數(shù)據(jù)索引、以及純分布式環(huán)境下支持動態(tài)維度擴展的多維數(shù)據(jù)索引三個方面展開，主要內(nèi)容概述如下：
　　1.針對現(xiàn)有云存儲系統(tǒng)主要支持單鍵值索引，缺乏有效的多維索引，導(dǎo)致多維度查詢效率較低的問題，本文提出了一種基于 UB樹的新型多維云數(shù)據(jù)索引方案：CloudUB。該方案首先利用Z曲線

3、進行多維空間的降維，然后沿 Z曲線將多維空間劃分成Z區(qū)域，利用B+樹組織Z區(qū)域信息，建立改進的UB樹索引。CloudUB在執(zhí)行多維查詢時能夠基于 Z區(qū)域濾除不可能包含查詢結(jié)果的數(shù)據(jù)空間，從而提高查詢效率。另外，本文設(shè)計了基于 HBase的索引構(gòu)建和維護機制，并提出了相應(yīng)的實時和離線索引構(gòu)建算法。該機制把基于 Z曲線降維的 B+樹葉節(jié)點保存在HBase中，將原始多維空間的查找問題轉(zhuǎn)化成現(xiàn)有云存儲系統(tǒng)能夠支持的key-value查詢問題，從

4、而支持MapReduce技術(shù)對索引表的高并發(fā)訪問。最后，本文設(shè)計了CloudUB的多維查找算法并進行了效率分析。基于Hadoop2.2版本、1000萬級數(shù)據(jù)量的測試結(jié)果表明，CloudUB索引方案支持靈活、高效的實時索引構(gòu)建，多維查詢效率顯著提升。
　　2.通過對云計算系統(tǒng)中數(shù)據(jù)管理方式的深入研究，本文提出了一種符合云計算系統(tǒng)主從管理方式的雙層多維數(shù)據(jù)索引：KD-R。該索引方案為云計算系統(tǒng)中的每一個數(shù)據(jù)服務(wù)器上的本地數(shù)據(jù)建立一個R

5、樹索引，所有本地的R樹索引共同構(gòu)成雙層索引系統(tǒng)的下層索引，然后將每個 R樹索引的部分節(jié)點信息發(fā)布到全局服務(wù)器層，由此構(gòu)建一個統(tǒng)一的 KD樹索引。針對將哪些局部索引節(jié)點發(fā)布到全局索引的問題，本文設(shè)計了自適應(yīng)的節(jié)點發(fā)布算法，以及選擇發(fā)布節(jié)點的代價模型，該代價模型可以估算局部索引節(jié)點的索引代價。索引系統(tǒng)根據(jù)代價模型對局部數(shù)據(jù)服務(wù)器上的索引節(jié)點進行周期性的檢測，然后利用自適應(yīng)節(jié)點發(fā)布算法，調(diào)整發(fā)布的局部索引節(jié)點，達到動態(tài)優(yōu)化KD-R索引的目的。

6、實驗結(jié)果表明，基于KD-R索引的多維查詢算法具有較高的內(nèi)存利用率和查詢效率，展示了良好的可用性。
　　3.針對云計算系統(tǒng)中用戶的需求具有彈性，存在動態(tài)擴展查詢維度的現(xiàn)狀，本文提出了一種基于Chord覆蓋網(wǎng)絡(luò)和分區(qū)位圖的多維云數(shù)據(jù)索引：CB-index。該索引方案采用 Chord覆蓋網(wǎng)絡(luò)構(gòu)建全局索引，克服了主從結(jié)構(gòu)帶來的全局服務(wù)器易形成瓶頸的問題，實現(xiàn)了純分布式的雙層索引架構(gòu)；同時，本文設(shè)計了分區(qū)位圖編碼機制，通過分區(qū)位圖構(gòu)建本地數(shù)