物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析_第1頁
物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析_第2頁
物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析_第3頁
物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析_第4頁
物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析_第5頁
已閱讀5頁,還剩67頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析目錄n物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n海量元數(shù)據(jù)查詢需求分析n物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(shè)計(jì)n面向數(shù)據(jù)更新的結(jié)構(gòu)設(shè)計(jì)和分析 n面向預(yù)計(jì)算的元數(shù)據(jù)組織結(jié)構(gòu)數(shù)據(jù)立方體 物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析 n大規(guī)模存儲(chǔ)系統(tǒng)的應(yīng)用越來越廣泛,存儲(chǔ)容量也從以前的TB(Terabyte)級(jí)上升到PB(Petabyte)級(jí)甚至EB(Exabyte)級(jí)。n隨著存儲(chǔ)系統(tǒng)規(guī)模不斷增大,在大規(guī)模文件系統(tǒng)中,文件的數(shù)量高達(dá)幾十億個(gè),在這種海量數(shù)據(jù)中查找和管理文件變得異常困難。物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n這與互聯(lián)網(wǎng)環(huán)境形成了鮮明的對(duì)比:n由于搜索引擎技術(shù)的發(fā)展,在互聯(lián)網(wǎng)的環(huán)境下查找信息很方便,n而用戶在存

2、儲(chǔ)系統(tǒng)中找到想要的信息比在互聯(lián)網(wǎng)上查找信息更加困難 物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n如今存儲(chǔ)系統(tǒng)中的數(shù)據(jù)量的快速增長使得查找和管理文件異常的困難,n為了能夠合理的管理這些不斷增多的海量數(shù)據(jù),n不管是用戶還是管理者都需要能夠高效的獲得文件的屬性。物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n元數(shù)據(jù)查詢包含索引文件元數(shù)據(jù),例如索引節(jié)點(diǎn)和一些擴(kuò)展屬性,能夠幫助回答很多復(fù)雜查詢問題。n利用文件屬性,元數(shù)據(jù)查詢?cè)试S點(diǎn)查詢、范圍查詢、top-k查詢和聚集查詢,n這些使得復(fù)雜的、特定的查詢變得簡單。物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n能夠幫助管理者回答n“哪些文件在過去的一周里增長很快?”n或者是“哪些應(yīng)用程序和用戶的文件占用大多數(shù)存儲(chǔ)空間?”n元

3、數(shù)據(jù)查詢也能夠幫助用戶找到10個(gè)最近訪問的報(bào)告或最大的虛擬機(jī)鏡像。n準(zhǔn)確地回答這些問題能夠極大的提高用戶和管理者管理大規(guī)模存儲(chǔ)系統(tǒng)中的文件。物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n現(xiàn)存的系統(tǒng)一般都采用通用型的數(shù)據(jù)庫管理系統(tǒng)(Database Management System,DBMS)來索引元數(shù)據(jù),n由于DBMS不能很好的適用于多維元數(shù)據(jù)的查詢,n查詢效率非常低物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n這就限制了在大規(guī)模存儲(chǔ)系統(tǒng)中元數(shù)據(jù)查詢的性能和可擴(kuò)展性,n所以在大規(guī)模存儲(chǔ)系統(tǒng)中要想獲得快速、高效的元數(shù)據(jù)查詢是很難實(shí)現(xiàn)的。物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n從而使得一些復(fù)雜查詢非常耗時(shí)、效率低下,n不能有效地支持用戶或管理者查找到想要

4、的文件,或得到想要的數(shù)據(jù)。n例如,“我最近修改過的PPT在哪?”n或者“我的目錄下這個(gè)文件有幾個(gè)副本? 物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n為了解決上述問題,必須提供一種高效的多維元數(shù)據(jù)查詢系統(tǒng),而且必須滿足以下特點(diǎn):n第一,必須能夠從存儲(chǔ)系統(tǒng)中快速收集到元數(shù)據(jù);n第二,查詢和更新必須快速而且可擴(kuò)展;n第三,必須能夠快速的返回計(jì)算結(jié)果,比如用戶提交一個(gè)復(fù)雜查詢后并不想長時(shí)間在線等待計(jì)算結(jié)果,有時(shí)這個(gè)過程非常費(fèi)時(shí)物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n例如n“某公司想統(tǒng)計(jì)一個(gè)星期內(nèi)用戶產(chǎn)生的數(shù)據(jù)總量有多少?”n或者“最近一星期內(nèi)排前五名的熱點(diǎn)文件是哪五個(gè)?”,n用戶或管理者希望系統(tǒng)能夠預(yù)先計(jì)算好這些結(jié)果而不用在線等待,當(dāng)提

5、交查詢后能夠快速返回結(jié)果物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n第四,資源需求必須很低,現(xiàn)存的很多元數(shù)據(jù)查詢工具需要專門的CPU、內(nèi)存以及硬盤,這就使得它們非常昂貴而且很難集成到存儲(chǔ)系統(tǒng)中;n第五,查詢的接口必須靈活好用,對(duì)于現(xiàn)存的文件系統(tǒng)接口和查詢語言,復(fù)雜查詢非常困難 物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析n在海量的數(shù)據(jù)中,讓用戶獲得想要的信息至關(guān)重要,n對(duì)存儲(chǔ)系統(tǒng)中多維元數(shù)據(jù)查詢的研究將大大提高文件元數(shù)據(jù)的查詢效率,n實(shí)現(xiàn)復(fù)雜查詢,縮短響應(yīng)時(shí)間,n這對(duì)于用戶或管理者查找和管理文件,以及決策支持都有重要的意義 海量元數(shù)據(jù)查詢需求分析 n現(xiàn)在的存儲(chǔ)系統(tǒng)都是采用層次化的目錄結(jié)構(gòu)來組織文件的,層次化結(jié)構(gòu)使得文件的訪問效率不高。

6、n訪問某個(gè)文件必須通過層次型的目錄樹結(jié)構(gòu)到達(dá)文件的保存位置,n如果不知道文件保存位置,就必須遍歷整個(gè)目錄或使用操作系統(tǒng)的搜索功能,n而操作系統(tǒng)僅能依靠文件名來檢索和查找數(shù)據(jù)。海量元數(shù)據(jù)查詢需求分析 n在最近的十幾年里,新數(shù)據(jù)類型(多媒體、電子郵件)不斷涌現(xiàn),n這些數(shù)據(jù)中包含了大量的元數(shù)據(jù)信息。n認(rèn)識(shí)到現(xiàn)有文件系統(tǒng)的不足,學(xué)術(shù)界和工業(yè)界都做了大量的工作來研究如何利用豐富的元數(shù)據(jù)信息來提高文件的管理和搜索效率 海量元數(shù)據(jù)查詢需求分析n在大規(guī)模存儲(chǔ)系統(tǒng)中查找和管理文件顯得更加困難,n元數(shù)據(jù)查詢可以很好的解決點(diǎn)查詢、范圍查詢、top-k查詢以及聚集查詢,n便于進(jìn)行一些復(fù)雜、特殊的查詢。n能夠快速地實(shí)現(xiàn)

7、上述查詢能極大地提高用戶或管理者對(duì)大規(guī)模存儲(chǔ)系統(tǒng)的管理 海量元數(shù)據(jù)查詢需求分析n在大規(guī)模存儲(chǔ)系統(tǒng)提供高效的元數(shù)據(jù)查詢是一個(gè)很大的挑戰(zhàn),n而現(xiàn)在有一些商業(yè)元數(shù)據(jù)查詢系統(tǒng)主要致力于小型的存儲(chǔ)系統(tǒng)(最多幾千萬個(gè)文件)n并且常常很慢,耗費(fèi)的資源多 海量元數(shù)據(jù)查詢需求分析n在大規(guī)模存儲(chǔ)系統(tǒng)中想要實(shí)現(xiàn)高效的元數(shù)據(jù)查詢,需滿足以下幾點(diǎn): n最小的資源需求最小的資源需求p元數(shù)據(jù)查詢不應(yīng)該需要額外的硬件,它應(yīng)該集成到存儲(chǔ)系統(tǒng)中而不降低系統(tǒng)的性能。p現(xiàn)在大多數(shù)的元數(shù)據(jù)查詢系統(tǒng)都需要專門的CPU、內(nèi)存以及磁盤,p使得它們非常昂貴而且很難部署,這就限制它們的擴(kuò)展性 海量元數(shù)據(jù)查詢需求分析n快速的元數(shù)據(jù)收集快速的元數(shù)據(jù)

8、收集n必須從幾十億、幾百億個(gè)文件中周期性的收集發(fā)生改變的元數(shù)據(jù),n而不會(huì)給整個(gè)存儲(chǔ)系統(tǒng)帶來額外負(fù)載,使得系統(tǒng)變慢。n現(xiàn)在的爬行算法(crawling method)非常慢而且消耗系統(tǒng)資源 海量元數(shù)據(jù)查詢需求分析n快速可擴(kuò)展的索引查詢和更新快速可擴(kuò)展的索引查詢和更新n查詢必須快速,甚至隨著系統(tǒng)規(guī)模的擴(kuò)大,性能依舊能保持很好,能夠快速周期性的對(duì)元數(shù)據(jù)索引進(jìn)行更新。n但是,現(xiàn)存的系統(tǒng)一般都采用通用型的關(guān)系型數(shù)據(jù)庫來索引元數(shù)據(jù)。nDBMS常常使用重量級(jí)的鎖和事務(wù),這給系統(tǒng)增加負(fù)載 海量元數(shù)據(jù)查詢需求分析n易用的查詢接口易用的查詢接口n大多數(shù)系統(tǒng)輸出簡單的查詢應(yīng)用程序接口,n但是研究表明專門設(shè)計(jì)的接口能

9、夠很好表達(dá)且容易使用,n這會(huì)大大提升查詢體驗(yàn)。 物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(shè)計(jì) n系統(tǒng)設(shè)計(jì)要求系統(tǒng)設(shè)計(jì)要求n第一、高性能,能夠快速的從文件系統(tǒng)中聚集元數(shù)據(jù),解決并發(fā)操作、熱點(diǎn)數(shù)據(jù)的管理和訪問等問題;n第二、查找和更新速度必須快且可靠?,F(xiàn)有的系統(tǒng)一般采用通用的DBMS來索引元數(shù)據(jù),但是通用的DBMS的設(shè)計(jì)并不完全適合各種應(yīng)用場合,比如元數(shù)據(jù)查找,特別是支持各種復(fù)雜的元數(shù)據(jù)查詢,熱點(diǎn)數(shù)據(jù)查詢等;而且在大規(guī)模存儲(chǔ)系統(tǒng)中會(huì)限制其性能和擴(kuò)展性。物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(shè)計(jì)n第三、低的資源消耗。保證元數(shù)據(jù)查詢不需要占用太多的存儲(chǔ)空間,且不會(huì)降低系統(tǒng)的性能。n第四、接口靈活好用?,F(xiàn)有的文件系統(tǒng)接口不能很好的支持各種復(fù)

10、雜文件查詢。n第五、良好的伸縮性及可用性。隨著存儲(chǔ)系統(tǒng)的規(guī)模越來越大,必須保證系統(tǒng)具有良好的伸縮性和可用性 多維元數(shù)據(jù)組織結(jié)構(gòu) n傳統(tǒng)的索引方法已不能滿足多維數(shù)據(jù)的索引和查詢要求,n比如哈希表是數(shù)據(jù)的精確匹配而不能進(jìn)行范圍查詢,n而B樹索引一維數(shù)據(jù)而不能搜索多維空間。n目前存在大量的空間數(shù)據(jù)索引方法多維元數(shù)據(jù)組織結(jié)構(gòu)n一般來說,常見的多維空間數(shù)據(jù)索引有兩種數(shù)據(jù)組織方式:基于規(guī)則的分割方法和基于數(shù)據(jù)的分割方法。n基于規(guī)則分割的索引結(jié)構(gòu)按照特定算法對(duì)數(shù)據(jù)空間進(jìn)行劃分,包括KD樹、網(wǎng)格等,n這種方法僅適用于數(shù)據(jù)分布均勻的情況,在數(shù)據(jù)分布不均勻時(shí)會(huì)引起索引結(jié)構(gòu)的不平衡。n基于數(shù)據(jù)的分割方法有R樹,Ce

11、ll樹等,按照數(shù)據(jù)的分布特性逐層劃分空間 多維元數(shù)據(jù)組織結(jié)構(gòu)n如果系統(tǒng)基于每個(gè)維度單獨(dú)建立索引,則需要對(duì)每個(gè)維度進(jìn)行查找之后將結(jié)果做交集。n如果系統(tǒng)按照多維屬性信息建立了空間索引結(jié)構(gòu),則可以同時(shí)在文件大小、創(chuàng)建時(shí)間和修改時(shí)間這個(gè)三個(gè)屬性維度上做約束,大大減少了查詢的數(shù)據(jù)量和查詢的時(shí)間代價(jià)。n系統(tǒng)耗費(fèi)一定的存儲(chǔ)空間維護(hù)空間索引結(jié)構(gòu),在提供各種復(fù)雜查詢服務(wù)時(shí)可以有效的減少查詢時(shí)間延遲 相關(guān)研究工作: R樹結(jié)構(gòu)n與B樹相似,R樹是一種高度平衡的樹,它的葉子節(jié)點(diǎn)的記錄包含數(shù)據(jù)對(duì)象的指針。n如果索引是磁盤駐留的,則每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)磁盤頁,以節(jié)點(diǎn)為單位讀取和寫入。n該結(jié)構(gòu)設(shè)計(jì)使得空間搜索只需要訪問一小部分

12、的節(jié)點(diǎn),大大提高檢索效率。n索引結(jié)構(gòu)是完全動(dòng)態(tài)的;插入、刪除和查找操作能同時(shí)進(jìn)行而且不需要定期地對(duì)樹的結(jié)構(gòu)進(jìn)行重新組織 相關(guān)研究工作相關(guān)研究工作:B樹、樹、B-樹、樹、B+樹、樹、B*樹樹nB樹樹 即二叉搜索樹:1.所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)兒子(Left和Right);2.所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字;3.非葉子結(jié)點(diǎn)的左指針指向小 于其關(guān)鍵字的子樹,右指針 指向大于其關(guān)鍵字的子樹;如:B樹樹n B樹的搜索,從根結(jié)點(diǎn)開始,如果查詢的關(guān)鍵字與結(jié)點(diǎn)的關(guān)鍵字相等,那么就命中;否則,如果查詢關(guān)鍵字比結(jié)點(diǎn)關(guān)鍵字小,就進(jìn)入左兒子;如果比結(jié)點(diǎn)關(guān)鍵字大,就進(jìn)入右兒子;如果左兒子或右兒子的指針為空,則報(bào)告找不到相應(yīng)的

13、關(guān)鍵字;n如果B樹的所有非葉子結(jié)點(diǎn)的左右子樹的結(jié)點(diǎn)數(shù)目均保持差不多(平衡),那么B樹的搜索性能逼近二分查找;但它比連續(xù)內(nèi)存空間的二分查找的優(yōu)點(diǎn)是,改變B樹結(jié)構(gòu)(插入與刪除結(jié)點(diǎn))不需要移動(dòng)大段的內(nèi)存數(shù)據(jù),甚至通常是常數(shù)開銷;B樹樹是一種多路搜索樹(并不是二叉的):1.定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子;且M2;2.根結(jié)點(diǎn)的兒子數(shù)為2, M;3.除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為M/2, M;4.每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1(取上整)和至多M-1個(gè)關(guān)鍵字;(至少2個(gè)關(guān)鍵字)5.非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1;6.非葉子結(jié)點(diǎn)的關(guān)鍵字:K1, K2, , KM-1;且Ki Ki+1;7.

14、非葉子結(jié)點(diǎn)的指針:P1, P2, , PM;其中P1指向關(guān)鍵字小于K1的子樹,PM指向關(guān)鍵字大于KM-1的子樹,其它Pi指向關(guān)鍵字屬于(Ki-1, Ki)的子樹;8.所有葉子結(jié)點(diǎn)位于同一層;如:(M=3)B-樹樹B樹樹B+樹是B-樹的變體,也是一種多路搜索樹:1.其定義基本與B-樹同,除了:2.非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同;3.非葉子結(jié)點(diǎn)的子樹指針Pi,指向關(guān)鍵字值屬于Ki, Ki+1)的子樹(B-樹是開區(qū)間);5.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針;6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn);如:(M=3)B+樹樹n是B+樹的變體,在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針;nB*樹定義了非葉子結(jié)

15、點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M,即塊的最低使用率為2/3(代替B+樹的1/2);B+樹的分裂:當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí),分配一個(gè)新的結(jié)點(diǎn),并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn),最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針;B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn),而不會(huì)影響兄弟結(jié)點(diǎn),所以它不需要指向兄弟的指針;B*樹的分裂:當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí),如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿,那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中,再在原結(jié)點(diǎn)插入關(guān)鍵字,最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字(因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了);如果兄弟也滿了,則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn),并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn),最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針;所以,B*樹分配新結(jié)點(diǎn)的概

16、率比B+樹要低,空間使用率更高;B*樹樹nB樹:二叉樹,每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字,等于則命中,小于走左結(jié)點(diǎn),大于走右結(jié)點(diǎn);nB-樹:多路搜索樹,每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字,非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn);n所有關(guān)鍵字在整顆樹中出現(xiàn),且只出現(xiàn)一次,非葉子結(jié)點(diǎn)可以命中;nB+樹:在B-樹基礎(chǔ)上,為葉子結(jié)點(diǎn)增加鏈表指針,所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn),非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引;B+樹總是到葉子結(jié)點(diǎn)才命中;nB*樹:在B+樹基礎(chǔ)上,為非葉子結(jié)點(diǎn)也增加鏈表指針,將結(jié)點(diǎn)的最低利用率從1/2提高到2/3;相關(guān)研究工作相關(guān)研究工作:B樹、樹、B-樹、樹、B+樹、樹、B*樹樹相關(guān)研究工作: R樹結(jié)構(gòu)

17、nR樹是一個(gè)高度平衡樹,它是B樹在k維上的自然擴(kuò)展,用空間對(duì)象的MBR來近似表達(dá)空間對(duì)象,根據(jù)地物的MBR建立R樹,可以直接對(duì)空間中占據(jù)一定范圍的空間對(duì)象進(jìn)行索引。R樹的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著磁盤頁D和區(qū)域I,如果結(jié)點(diǎn)不是葉結(jié)點(diǎn),則該結(jié)點(diǎn)的所有子結(jié)點(diǎn)的區(qū)域都在區(qū)域I的范圍之內(nèi),而且存儲(chǔ)在磁盤頁D中。如果結(jié)點(diǎn)是葉結(jié)點(diǎn),那么磁盤頁D中存儲(chǔ)的將是區(qū)域I范圍內(nèi)的一系列子區(qū)域,子區(qū)域緊緊圍繞空間對(duì)象,一般為空間對(duì)象的外接矩形。 n一個(gè)空間數(shù)據(jù)庫由代表對(duì)象的的集合組成。n每個(gè)對(duì)象元組都有一個(gè)唯一的標(biāo)識(shí)符,可通過這些標(biāo)識(shí)符來檢索對(duì)象元組。nR樹的葉節(jié)點(diǎn)按以下形式記錄索引記錄的入口 比較典型的有R+樹、R樹、壓縮

18、R樹等。 相關(guān)研究工作: R樹結(jié)構(gòu)n特點(diǎn); 1根節(jié)點(diǎn)若非葉子節(jié)點(diǎn),則至少有兩個(gè)子節(jié)點(diǎn); 2每個(gè)非根葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)包含的實(shí)體個(gè)數(shù)均介于m和M之間; 3所有葉子節(jié)點(diǎn)在同一層次; R樹兄弟結(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域可以重疊,可以較容易地進(jìn)行插入和刪除操作。但正因?yàn)閰^(qū)域之間有重疊,空間索引可能要對(duì)多條路徑進(jìn)行搜索后才能得到最后的結(jié)果。 R樹的空間分布圖 Bloom filternBloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu),它利用位數(shù)組很簡潔地表示一個(gè)集合,并能判斷一個(gè)元素是否屬于這個(gè)集合。Bloom Filter的這種高效是有一定代價(jià)的:在判斷一個(gè)元素是否屬于某個(gè)集合時(shí),有可能會(huì)把不屬于這個(gè)集

19、合的元素誤認(rèn)為屬于這個(gè)集合(false positive)。因此,Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場合。而在能容忍低錯(cuò)誤率的應(yīng)用場合下,Bloom Filter通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。n由一個(gè)很長的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成,n它只需要哈希表 1/8 到 1/4 的大小就能解決同樣規(guī)模的集合的查詢問題 Bloom filterBloom filter nBloom filter的本質(zhì)是哈希計(jì)算,不同之處在于Bloom filter對(duì)同一數(shù)據(jù)使用多個(gè)哈希函數(shù)進(jìn)行多次哈希,將結(jié)果保存在同一個(gè)向量數(shù)組中,n所以Bloom filter在達(dá)到相同的功能的情

20、況下比原始的哈希結(jié)構(gòu)更節(jié)約存儲(chǔ)空間。nBloom filter算法的一個(gè)缺點(diǎn)在于查詢一個(gè)元素是否在集合S上可能存在失誤定位(False Positive) n集合表示和元素查詢集合表示和元素查詢n下面我們具體來看Bloom Filter是如何用位數(shù)組表示集合的。初始狀態(tài)時(shí),Bloom Filter是一個(gè)包含m位的位數(shù)組,每一位都置為0。Bloom filtern為了表達(dá)S=x1, x2,xn這樣一個(gè)n個(gè)元素的集合,Bloom Filter使用k個(gè)相互獨(dú)立的哈希函數(shù)(Hash Function),它們分別將集合中的每個(gè)元素映射到1,m的范圍中。對(duì)任意一個(gè)元素x,第i個(gè)哈希函數(shù)映射的位置hi(x)

21、就會(huì)被置為1(1ik)。注意,如果一個(gè)位置多次被置為1,那么只有第一次會(huì)起作用,后面幾次將沒有任何效果。在下圖中,k=3,且有兩個(gè)哈希函數(shù)選中同一個(gè)位置(從左邊數(shù)第五位)。 Bloom filtern在判斷y是否屬于這個(gè)集合時(shí),我們對(duì)y應(yīng)用k次哈希函數(shù),如果所有hi(y)的位置都是1(1ik),那么我們就認(rèn)為y是集合中的元素,否則就認(rèn)為y不是集合中的元素。下圖中y1就不是集合中的元素。y2或者屬于這個(gè)集合,或者剛好是一個(gè)false positive。 算法算法Bloom filter Bloom filterRBF索引結(jié)構(gòu) n從B樹演變而來的R樹結(jié)構(gòu),能有效地支持多維范圍查詢。n但是,R樹不能

22、有效地支持點(diǎn)查詢。因?yàn)槌蓡T查詢只能在葉子節(jié)點(diǎn)上進(jìn)行,相應(yīng)的操作將導(dǎo)致查詢效率很低。n然而,Bloom filter是一種空間利用率高且能有效地支持點(diǎn)查詢的結(jié)構(gòu)。RBF索引結(jié)構(gòu)n一種叫做RBF的新的空間存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)多維元數(shù)據(jù),n基本思路是是擴(kuò)展經(jīng)典的R樹結(jié)構(gòu),n將Bloom filter插入到每個(gè)R樹結(jié)點(diǎn)上來支持點(diǎn)查詢,n維持多維范圍信息并實(shí)現(xiàn)空間效率 RBF索引結(jié)構(gòu)面向數(shù)據(jù)更新的結(jié)構(gòu)設(shè)計(jì)和分析 nR樹更新 n基于R樹的索引在商業(yè)上得到廣泛應(yīng)用和發(fā)展,n但是它在頻繁更新操作時(shí)性能低下。nR樹及其變體在空間索引結(jié)構(gòu)中占據(jù)主導(dǎo)地位,R樹更新 n傳統(tǒng)的空間索引的研究主要考慮靜態(tài)數(shù)據(jù),n只關(guān)注高效的查

23、詢處理,R樹的更新性能很差,n不能直接用于頻繁更新的應(yīng)用環(huán)境R樹更新n存儲(chǔ)系統(tǒng)下元數(shù)據(jù)的更新是很頻繁的,n直接對(duì)索引的修改會(huì)產(chǎn)生大量的磁盤操作并可能引起索引結(jié)構(gòu)的不平衡。n已經(jīng)存在的各種基于R樹索引的更新機(jī)制主要采取的是自頂向下模式 減少更新操作的方法 n位置預(yù)測位置預(yù)測n一種減少對(duì)象更新操作次數(shù)的策略是采用線性函數(shù)來表示移動(dòng)對(duì)象的位置,n保存對(duì)象的運(yùn)動(dòng)特性,包括當(dāng)前位置和速度參數(shù)等,n通過這些數(shù)據(jù)可以預(yù)測將來一段時(shí)間后的位置 減少更新操作的方法n容忍更新容忍更新n減少更新次數(shù)的另一種策略是容忍更新。并不是每次更新都需要一個(gè)至上而下的刪除操作和插入操作。n當(dāng)一個(gè)對(duì)象的新位置沒有移出原來的MBR

24、,換句話說就是該對(duì)象還在同一個(gè)葉子節(jié)點(diǎn)內(nèi)時(shí),n只要修改對(duì)應(yīng)葉子節(jié)點(diǎn)的數(shù)據(jù)信息即可,不需要?jiǎng)h除后插入,也不可能引起分裂和合并操作 延遲更新 n更新操作包括刪除和插入兩個(gè)步驟,延遲更新也包括延遲刪除和延遲插入兩個(gè)方面。n延遲刪除的策略是將更新信息立即插入,而舊的對(duì)象信息不會(huì)立即刪除,n而是使用某種策略將未刪除的索引信息緩存起來以便區(qū)分新舊數(shù)據(jù),直到緩沖區(qū)滿或者其它情況下才進(jìn)行刪除操作 批量操作nR樹的批量插入策略是當(dāng)前研究的熱點(diǎn)之一。n其中STLT (Small-Tree-Large-Tree) 技術(shù),n首先利用輸入數(shù)據(jù)集建立一棵小R(Small tree)樹,n然后將小R樹插入到原有的大R樹(L

25、arge tree)中 批量操作nGBI(Generalized Bulk Insertion)技術(shù)利用聚類算法將輸入數(shù)據(jù)集分割為多個(gè)空間上接近的數(shù)據(jù)組,n為每個(gè)數(shù)據(jù)組建立R樹結(jié)構(gòu),n最后將這些R樹結(jié)構(gòu)批量插入到目標(biāo)R樹中 多版本文件更新系統(tǒng) nVersioning文件系統(tǒng)保存被修改的文件之前的版本,來實(shí)現(xiàn)用戶誤操作以及系統(tǒng)錯(cuò)誤后的數(shù)據(jù)恢復(fù)。nVersioning文件系統(tǒng)存在的主要問題是不能有效地保存大量的version,version數(shù)據(jù)消耗大量的存儲(chǔ)空間,n對(duì)version的刪除的策略,恢復(fù)系統(tǒng)時(shí)version的選擇問題等 多版本文件更新系統(tǒng)nCedar采用簡單的version策略來幫助客

26、戶在誤操作后恢復(fù)數(shù)據(jù)。n最近的Elephant文件系統(tǒng)提供了一系列的version選項(xiàng),n用來保存對(duì)用戶最為重要的文件的version。多版本文件更新系統(tǒng)nCVFS提出兩種有效節(jié)省空間的version元數(shù)據(jù)結(jié)構(gòu),n對(duì)于inodes和indirect blocks采用Journal-based元數(shù)據(jù),n而對(duì)于目錄采用Multiversion B樹,有效地節(jié)省了version占用的空間。多版本文件更新系統(tǒng)nCausality-based versioning結(jié)合causal relationship和versioning技術(shù),n通過causal connection使得version更具意義,n提

27、出新的在何時(shí)創(chuàng)建version的算法;n通過causal relationship定位version,能夠更有效的在錯(cuò)誤后恢復(fù)到正確的version 面向預(yù)計(jì)算的元數(shù)據(jù)組織結(jié)構(gòu)數(shù)據(jù)立方體 n數(shù)據(jù)立方體(Data Cube)是分析數(shù)據(jù)倉庫數(shù)據(jù)的基本單位,是聯(lián)機(jī)分析處理(On-Line Analytical Processing, OLAP)中的主要對(duì)象,n是一項(xiàng)可對(duì)數(shù)據(jù)倉庫中的數(shù)據(jù)進(jìn)行快速訪問的技術(shù)。n數(shù)據(jù)立方體是一個(gè)數(shù)據(jù)集合,通常由數(shù)據(jù)倉庫的子集構(gòu)造,并組織和匯總成一個(gè)由一組維度和度量值定義的多維結(jié)構(gòu)。n數(shù)據(jù)立方體提供一種便于使用的查詢數(shù)據(jù)機(jī)制,響應(yīng)時(shí)間短 數(shù)據(jù)立方體n數(shù)據(jù)立方體是多維數(shù)據(jù)庫的基本結(jié)構(gòu),n并作為在多維數(shù)據(jù)庫上定義的所有操作符的輸入輸出基本單位。n將它定義為一個(gè)四元組,這四個(gè)組件分別表示數(shù)據(jù)立方體的特征 數(shù)據(jù)立方體n在典型的OLAP應(yīng)用中,存在一個(gè)中心關(guān)系或數(shù)據(jù)集合,稱作事實(shí)表。n事實(shí)表代表感興趣的事件或?qū)ο?。n事實(shí)表通常有幾個(gè)表示維的屬性和一個(gè)或多個(gè)度量屬性,n這些度量屬性一般是用戶想要查詢到的一些值 維數(shù)據(jù)立方體表示 數(shù)據(jù)立方體的計(jì)算 n數(shù)據(jù)立方體的計(jì)算是數(shù)據(jù)倉庫實(shí)現(xiàn)的一項(xiàng)基本任務(wù),數(shù)據(jù)立方體計(jì)算也稱為數(shù)據(jù)立方體的物化(Materialization)n簡單的說,它是將常用的查詢按照各自的屬性分組(Group by)提前計(jì)算出結(jié)果并保存起來

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論