物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析

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é)果并保存起來