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

物聯(lián)網(wǎng)數(shù)據(jù)存放及

管理物聯(lián)網(wǎng)數(shù)據(jù)存放及管理分析1/72目錄物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析海量元數(shù)據(jù)查詢需求分析物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(shè)計面向數(shù)據(jù)更新構(gòu)造設(shè)計和分析面向估計算元數(shù)據(jù)組織構(gòu)造－數(shù)據(jù)立方體2/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析大規(guī)模存放系統(tǒng)應(yīng)用越來越廣泛，存放容量也從此前TB（Terabyte）級上升到PB（Petabyte）級甚至EB（Exabyte）級。伴隨存放系統(tǒng)規(guī)模不停增大，在大規(guī)模文獻系統(tǒng)中，文獻數(shù)量高達幾十億個，在這種海量數(shù)據(jù)中查找和管理文獻變得異常困難。3/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析這與互聯(lián)網(wǎng)環(huán)境形成了鮮明對比：由于搜索引擎技術(shù)發(fā)展，在互聯(lián)網(wǎng)環(huán)境下查找信息很方便，而顧客在存放系統(tǒng)中找到想要信息比在互聯(lián)網(wǎng)上查找信息愈加困難4/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析如今存放系統(tǒng)中數(shù)據(jù)量迅速增加使得查找和管理文獻異常困難，為了能夠合理管理這些不停增多海量數(shù)據(jù)，不論是顧客還是管理者都需要能夠高效取得文獻屬性。5/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析元數(shù)據(jù)查詢包括索引文獻元數(shù)據(jù)，例如索引節(jié)點和某些擴展屬性，能夠幫助回答很多復(fù)雜查問詢題。利用文獻屬性，元數(shù)據(jù)查詢允許點查詢、范圍查詢、top-k查詢和聚集查詢，這些使得復(fù)雜、特定查詢變得簡單。6/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析能夠幫助管理者回答“哪些文獻在過去一周里增加很快？”或者是“哪些應(yīng)用程序和顧客文獻占用大多數(shù)存放空間？”元數(shù)據(jù)查詢也能夠幫助顧客找到10個近來訪問報告或最大虛擬機鏡像。精確地回答這些問題能夠極大提升顧客和管理者管理大規(guī)模存放系統(tǒng)中文獻。7/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析現(xiàn)存系統(tǒng)一般都采取通用型數(shù)據(jù)庫管理系統(tǒng)（DatabaseManagementSystem，DBMS）來索引元數(shù)據(jù)，由于DBMS不能較好適用于多維元數(shù)據(jù)查詢，查詢效率非常低8/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析這就限制了在大規(guī)模存放系統(tǒng)中元數(shù)據(jù)查詢性能和可擴展性，因此在大規(guī)模存放系統(tǒng)中要想取得迅速、高效元數(shù)據(jù)查詢是很難實現(xiàn)。9/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析從而使得某些復(fù)雜查詢非常耗時、效率低下，不能有效地支持顧客或管理者查找到想要文獻，或得到想要數(shù)據(jù)。例如，“我近來修改正PPT在哪？”或者“我目錄下這個文獻有幾個副本？10/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析為理解決上述問題，必須提供一種高效多維元數(shù)據(jù)查詢系統(tǒng)，并且必須滿足以下特點：第一，必須能夠從存放系統(tǒng)中快速收集到元數(shù)據(jù)；第二，查詢和更新必須快速并且可擴展；第三，必須能夠快速返回計算結(jié)果，比如用戶提交一個復(fù)雜查詢后并不想長時間在線等候計算結(jié)果，有時這個過程非常費時11/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析例如“某公司想統(tǒng)計一種星期內(nèi)顧客產(chǎn)生數(shù)據(jù)總量有多少？”或者“近來一星期內(nèi)排前五名熱點文獻是哪五個？”，顧客或管理者希望系統(tǒng)能夠預(yù)先計算好這些成果而不用在線等候，當提交查詢后能夠迅速返回成果12/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析第四，資源需求必須很低，現(xiàn)存很多元數(shù)據(jù)查詢工具需要專門CPU、內(nèi)存以及硬盤，這就使得它們非常昂貴并且很難集成到存放系統(tǒng)中；第五，查詢接口必須靈活好用，對于現(xiàn)存文獻系統(tǒng)接口和查詢語言，復(fù)雜查詢非常困難13/72物聯(lián)網(wǎng)數(shù)據(jù)存放現(xiàn)狀分析在海量數(shù)據(jù)中，讓顧客取得想要信息至關(guān)主要，對存放系統(tǒng)中多維元數(shù)據(jù)查詢研究將大大提升文獻元數(shù)據(jù)查詢效率，實現(xiàn)復(fù)雜查詢，縮短響應(yīng)時間，這對于顧客或管理者查找和管理文獻，以及決策支持都有主要意義14/72海量元數(shù)據(jù)查詢需求分析目前存放系統(tǒng)都是采取層次化目錄構(gòu)造來組織文獻，層次化構(gòu)造使得文獻訪問效率不高。訪問某個文獻必須通過層次型目錄樹構(gòu)造達到文獻保存位置，假如不懂得文獻保存位置，就必須遍歷整個目錄或使用操作系統(tǒng)搜索功能，而操作系統(tǒng)僅能依靠文獻名來檢索和查找數(shù)據(jù)。15/72海量元數(shù)據(jù)查詢需求分析在近來十幾年里，新數(shù)據(jù)類型（多媒體、電子郵件）不停涌現(xiàn)，這些數(shù)據(jù)中包括了大量元數(shù)據(jù)信息。結(jié)識到現(xiàn)有文獻系統(tǒng)不足，學(xué)術(shù)界和工業(yè)界都做了大量工作來研究如何利用豐富元數(shù)據(jù)信息來提升文獻管理和搜索效率16/72海量元數(shù)據(jù)查詢需求分析在大規(guī)模存放系統(tǒng)中查找和管理文獻顯得愈加困難，元數(shù)據(jù)查詢能夠較好處理點查詢、范圍查詢、top-k查詢以及聚集查詢，便于進行某些復(fù)雜、特殊查詢。能夠迅速地實現(xiàn)上述查詢能極大地提升顧客或管理者對大規(guī)模存放系統(tǒng)管理17/72海量元數(shù)據(jù)查詢需求分析在大規(guī)模存放系統(tǒng)提供高效元數(shù)據(jù)查詢是一種很大挑戰(zhàn)，而目前有某些商業(yè)元數(shù)據(jù)查詢系統(tǒng)主要致力于小型存放系統(tǒng)（最多幾千萬個文獻）并且經(jīng)常很慢，花費資源多18/72海量元數(shù)據(jù)查詢需求分析在大規(guī)模存放系統(tǒng)中想要實現(xiàn)高效元數(shù)據(jù)查詢，需滿足下列幾點:最小資源需求元數(shù)據(jù)查詢不應(yīng)當需要額外硬件，它應(yīng)當集成到存放系統(tǒng)中而不減少系統(tǒng)性能。目前大多數(shù)元數(shù)據(jù)查詢系統(tǒng)都需要專門CPU、內(nèi)存以及磁盤，使得它們非常昂貴并且很難布署，這就限制它們擴展性19/72海量元數(shù)據(jù)查詢需求分析迅速元數(shù)據(jù)搜集必須從幾十億、幾百億個文獻中周期性搜集發(fā)生變化元數(shù)據(jù)，而不會給整個存放系統(tǒng)帶來額外負載，使得系統(tǒng)變慢。目前爬行算法（crawlingmethod）非常慢并且消耗系統(tǒng)資源20/72海量元數(shù)據(jù)查詢需求分析迅速可擴展索引查詢和更新查詢必須迅速，甚至伴隨系統(tǒng)規(guī)模擴大，性能依舊能保持較好，能夠迅速周期性對元數(shù)據(jù)索引進行更新。不過，現(xiàn)存系統(tǒng)一般都采取通用型關(guān)系型數(shù)據(jù)庫來索引元數(shù)據(jù)。DBMS經(jīng)常使用重量級鎖和事務(wù)，這給系統(tǒng)增加負載21/72海量元數(shù)據(jù)查詢需求分析易用查詢接口大多數(shù)系統(tǒng)輸出簡單查詢應(yīng)用程序接口，不過研究表白專門設(shè)計接口能夠較好體現(xiàn)且容易使用，這會大大提升查詢體驗。22/72物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(shè)計系統(tǒng)設(shè)計要求第一、高性能，能夠迅速從文獻系統(tǒng)中聚集元數(shù)據(jù)，處理并發(fā)操作、熱點數(shù)據(jù)管理和訪問等問題；第二、查找和更新速度必須快且可靠?，F(xiàn)有系統(tǒng)一般采取通用DBMS來索引元數(shù)據(jù)，不過通用DBMS設(shè)計并不完全適合多種應(yīng)用場所，例如元數(shù)據(jù)查找，尤其是支持多種復(fù)雜元數(shù)據(jù)查詢，熱點數(shù)據(jù)查詢等；并且在大規(guī)模存放系統(tǒng)中會限制其性能和擴展性。23/72物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(shè)計第三、低資源消耗。確保元數(shù)據(jù)查詢不需要占用太多存放空間，且不會減少系統(tǒng)性能。第四、接口靈活好用?，F(xiàn)有文獻系統(tǒng)接口不能較好支持多種復(fù)雜文獻查詢。第五、良好伸縮性及可用性。伴隨存放系統(tǒng)規(guī)模越來越大，必須確保系統(tǒng)具有良好伸縮性和可用性24/72多維元數(shù)據(jù)組織構(gòu)造傳統(tǒng)索引辦法已不能滿足多維數(shù)據(jù)索引和查詢要求，例如哈希表是數(shù)據(jù)精確匹配而不能進行范圍查詢，而B樹索引一維數(shù)據(jù)而不能搜索多維空間。目前存在大量空間數(shù)據(jù)索引辦法25/72多維元數(shù)據(jù)組織構(gòu)造一般來說，常見多維空間數(shù)據(jù)索引有兩種數(shù)據(jù)組織方式：基于規(guī)則分割辦法和基于數(shù)據(jù)分割辦法。基于規(guī)則分割索引構(gòu)造按照特定算法對數(shù)據(jù)空間進行劃分，包括KD樹、網(wǎng)格等，這種辦法僅適用于數(shù)據(jù)分布均勻情況，在數(shù)據(jù)分布不均勻時會引發(fā)索引構(gòu)造不平衡。基于數(shù)據(jù)分割辦法有R樹，Cell樹等，按照數(shù)據(jù)分布特性逐層劃分空間26/72多維元數(shù)據(jù)組織構(gòu)造假如系統(tǒng)基于每個維度單獨建立索引，則需要對每個維度進行查找之后將成果做交集。假如系統(tǒng)按照多維屬性信息建立了空間索引構(gòu)造，則能夠同步在文獻大小、創(chuàng)建時間和修改時間這個三個屬性維度上做約束，大大減少了查詢數(shù)據(jù)量和查詢時間代價。系統(tǒng)花費一定存放空間維護空間索引構(gòu)造，在提供多種復(fù)雜查詢服務(wù)時能夠有效減少查詢時間延遲27/72有關(guān)研究工作:R樹構(gòu)造與B樹相同，R樹是一種高度平衡樹，它葉子節(jié)點統(tǒng)計包括數(shù)據(jù)對象指針。假如索引是磁盤駐留，則每個節(jié)點對應(yīng)一種磁盤頁，以節(jié)點為單位讀取和寫入。該構(gòu)造設(shè)計使得空間搜索只需要訪問一小部分節(jié)點，大大提升檢索效率。索引構(gòu)造是完全動態(tài)；插入、刪除和查找操作能同步進行并且不需要定期地對樹構(gòu)造進行重新組織28/72有關(guān)研究工作:B樹、B-樹、B+樹、B*樹B樹即二叉搜索樹：

1.所有非葉子結(jié)點至多擁有兩個兒子（Left和Right）；

2.所有結(jié)點存放一種關(guān)鍵字；

3.非葉子結(jié)點左指針指向小于其關(guān)鍵字子樹，右指針指向大于其關(guān)鍵字子樹； 如：29/72B樹

B樹搜索，從根結(jié)點開始，假如查詢關(guān)鍵字與結(jié)點關(guān)鍵字相等，那么就命中；不然，假如查詢關(guān)鍵字比結(jié)點關(guān)鍵字小，就進入左兒子；假如比結(jié)點關(guān)鍵字大，就進入右兒子；假如左兒子或右兒子指針為空，則報告找不到對應(yīng)關(guān)鍵字； 假如B樹所有非葉子結(jié)點左右子樹結(jié)點數(shù)目均保持差不多（平衡），那么B樹搜索性能逼近二分查找；但它比連續(xù)內(nèi)存空間二分查找長處是，變化B樹構(gòu)造（插入與刪除結(jié)點）不需要移動大段內(nèi)存數(shù)據(jù)，甚至一般是常數(shù)開銷；30/72B樹31/72

是一種多路搜索樹（并不是二叉）：

1.定義任意非葉子結(jié)點最多只有M個兒子；且M>2；

2.根結(jié)點兒子數(shù)為[2,M]；

3.除根結(jié)點以外非葉子結(jié)點兒子數(shù)為[M/2,M]；

4.每個結(jié)點寄存最少M/2-1（取上整）和至多M-1個關(guān)鍵字；（最少2個關(guān)鍵字）

5.非葉子結(jié)點關(guān)鍵字個數(shù)=指向兒子指針個數(shù)-1；

6.非葉子結(jié)點關(guān)鍵字：K[1],K[2],…,K[M-1]；且K[i]<K[i+1]；

7.非葉子結(jié)點指針：P[1],P[2],…,P[M]；其中P[1]指向關(guān)鍵字不大于K[1]子樹，P[M]指向關(guān)鍵字大于K[M-1]子樹，其他P[i]指向關(guān)鍵字屬于(K[i-1],K[i])子樹；

8.所有葉子結(jié)點位于同一層； 如：（M=3）B-樹32/72B樹33/72 B+樹是B-樹變體，也是一種多路搜索樹：

1.其定義基本與B-樹同，除了：

2.非葉子結(jié)點子樹指針與關(guān)鍵字個數(shù)相同；

3.非葉子結(jié)點子樹指針P[i]，指向關(guān)鍵字值屬于[K[i],K[i+1])子樹（B-樹是開區(qū)間）；

5.為所有葉子結(jié)點增加一種鏈指針；

6.所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)； 如：（M=3）B+樹34/72是B+樹變體，在B+樹非根和非葉子結(jié)點再增加指向弟兄指針；B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)最少為(2/3)*M，即塊最低使用率為2/3（替代B+樹1/2）；

B+樹分裂：當一種結(jié)點滿時，分派一種新結(jié)點，并將原結(jié)點中1/2數(shù)據(jù)復(fù)制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點指針；B+樹分裂只影響原結(jié)點和父結(jié)點，而不會影響弟兄結(jié)點，因此它不需要指向弟兄指針；

B*樹分裂：當一種結(jié)點滿時，假如它下一種弟兄結(jié)點未滿，那么將一部分數(shù)據(jù)移到弟兄結(jié)點中，再在原結(jié)點插入關(guān)鍵字，最后修改父結(jié)點中弟兄結(jié)點關(guān)鍵字（由于弟兄結(jié)點關(guān)鍵字范圍變化了）；假如弟兄也滿了，則在原結(jié)點與弟兄結(jié)點之間增加新結(jié)點，并各復(fù)制1/3數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點指針；

因此，B*樹分派新結(jié)點概率比B+樹要低，空間使用率更高；B*樹35/72 B樹：二叉樹，每個結(jié)點只存放一種關(guān)鍵字，等于則命中，不大于走左結(jié)點，大于走右結(jié)點；

B-樹：多路搜索樹，每個結(jié)點存放M/2到M個關(guān)鍵字，非葉子結(jié)點存放指向關(guān)鍵字范圍子結(jié)點； 所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點能夠命中；

B+樹：在B-樹基礎(chǔ)上，為葉子結(jié)點增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點中出現(xiàn)，非葉子結(jié)點作為葉子結(jié)點索引；B+樹總是到葉子結(jié)點才命中；

B*樹：在B+樹基礎(chǔ)上，為非葉子結(jié)點也增加鏈表指針，將結(jié)點最低利用率從1/2提升到2/3；有關(guān)研究工作:B樹、B-樹、B+樹、B*樹36/72有關(guān)研究工作:R樹構(gòu)造

R樹是一種高度平衡樹，它是B樹在k維上自然擴展，用空間對象MBR來近似體現(xiàn)空間對象，根據(jù)地物MBR建立R樹，能夠直接對空間中占據(jù)一定范圍空間對象進行索引。R樹每一種結(jié)點都對應(yīng)著磁盤頁D和區(qū)域I，假如結(jié)點不是葉結(jié)點，則該結(jié)點所有子結(jié)點區(qū)域都在區(qū)域I范圍之內(nèi)，并且存放在磁盤頁D中。假如結(jié)點是葉結(jié)點，那么磁盤頁D中存放將是區(qū)域I范圍內(nèi)一系列子區(qū)域，子區(qū)域緊扣空間對象，一般為空間對象外接矩形。一種空間數(shù)據(jù)庫由代表對象集合組成。每個對象元組都有一種唯一標識符，可通過這些標識符來檢索對象元組。R樹葉節(jié)點按下列形式統(tǒng)計索引統(tǒng)計入口比較典型有R+樹、R·樹、壓縮R樹等。37/72有關(guān)研究工作:R樹構(gòu)造特點；

1．根節(jié)點若非葉子節(jié)點，則最少有兩個子節(jié)點；

2．每個非根葉節(jié)點和非葉節(jié)點包括實體個數(shù)均介于m和M之間；

3．所有葉子節(jié)點在同一層次；

R樹弟兄結(jié)點對應(yīng)空間區(qū)域能夠重合，能夠較容易地進行插入和刪除操作。但正由于區(qū)域之間有重合，空間索引也許要對多條途徑進行搜索后才能得到最后成果。38/72R樹空間分布圖39/72BloomfilterBloomFilter是一種空間效率很高隨機數(shù)據(jù)構(gòu)造，它利用位數(shù)組很簡潔地表達一種集合，并能判斷一種元素是否屬于這個集合。BloomFilter這種高效是有一定代價：在判斷一種元素是否屬于某個集合時，有也許會把不屬于這個集合元素誤以為屬于這個集合（falsepositive）。因此，BloomFilter不適合那些“零錯誤”應(yīng)用場所。而在能容忍低錯誤率應(yīng)用場所下，BloomFilter通過很少錯誤換取了存放空間極大節(jié)省。40/72由一種很長二進制向量數(shù)組和一系列隨機映射函數(shù)組成，它只需要哈希表1/8到1/4大小就能處理同樣規(guī)模集合查問詢題Bloomfilter41/72BloomfilterBloomfilter本質(zhì)是哈希計算，不一樣之處于于Bloomfilter對同一數(shù)據(jù)使用多種哈希函數(shù)進行數(shù)次哈希，將成果保存在同一種向量數(shù)組中，因此Bloomfilter在達成相同功能情況下比原始哈希構(gòu)造更節(jié)省存放空間。Bloomfilter算法一種缺陷在于查詢一種元素是否在集合S上也許存在失誤定位(FalsePositive)42/72集合表達和元素查詢下面我們詳細來看BloomFilter是如何用位數(shù)組表達集合。初始狀態(tài)時，BloomFilter是一種包括m位位數(shù)組，每一位都置為0。Bloomfilter43/72為了體現(xiàn)S={x1,x2,…,xn}這樣一種n個元素集合，BloomFilter使用k個互相獨立哈希函數(shù)（HashFunction），它們分別將集合中每個元素映射到{1,…,m}范圍中。對任意一種元素x，第i個哈希函數(shù)映射位置hi(x)就會被置為1（1≤i≤k）。注意，假如一種位置數(shù)次被置為1，那么只有第一次會起作用，背面幾次將沒有任何效果。在下列圖中，k=3，且有兩個哈希函數(shù)選中同一種位置（從左邊數(shù)第五位）。Bloomfilter44/72在判斷y是否屬于這個集合時，我們對y應(yīng)用k次哈希函數(shù)，假如所有hi(y)位置都是1（1≤i≤k），那么我們就以為y是集合中元素，不然就以為y不是集合中元素。下列圖中y1就不是集合中元素。y2或者屬于這個集合，或者剛好是一種falsepositive。

算法Bloomfilter

Bloomfilter45/72RBF索引構(gòu)造從B樹演變而來R樹構(gòu)造，能有效地支持多維范圍查詢。不過，R樹不能有效地支持點查詢。由于組員查詢只能在葉子節(jié)點上進行，對應(yīng)操作將造成查詢效率很低。然而，Bloomfilter是一種空間利用率高且能有效地支持點查詢構(gòu)造。46/72RBF索引構(gòu)造一種叫做RBF新空間存放構(gòu)造來存放多維元數(shù)據(jù)，基本思緒是是擴展典型R樹構(gòu)造，將Bloomfilter插入到每個R樹結(jié)點上來支持點查詢，維持多維范圍信息并實現(xiàn)空間效率47/72RBF索引構(gòu)造48/72面向數(shù)據(jù)更新構(gòu)造設(shè)計和分析R樹更新基于R樹索引在商業(yè)上得到廣泛應(yīng)用和發(fā)展，不過它在頻繁更新操作時性能低下。R樹及其變體在空間索引構(gòu)造中占據(jù)主導(dǎo)地位，49/72R樹更新傳統(tǒng)空間索引研究主要考慮靜態(tài)數(shù)據(jù)，只關(guān)注高效查詢處理，R樹更新性能很差，不能直接用于頻繁更新應(yīng)用環(huán)境50/72R樹更新存放系統(tǒng)下元數(shù)據(jù)更新是很頻繁，直接對索引修改會產(chǎn)生大量磁盤操作并也許引發(fā)索引構(gòu)造不平衡。已經(jīng)存在多種基于R樹索引更新機制主要采取是自頂向下模式51/72減少更新操作辦法位置預(yù)測一種減少對象更新操作次數(shù)策略是采取線性函數(shù)來表達移動對象位置，保存對象運動特性，包括目前位置和速度參數(shù)等，通過這些數(shù)據(jù)能夠預(yù)測將來一段時間后位置52/72減少更新操作辦法容忍更新減少更新次數(shù)另一種策略是容忍更新。并不是每次更新都需要一種至上而下刪除操作和插入操作。當一種對象新位置沒有移出本來MBR，換句話說就是該對象還在同一種葉子節(jié)點內(nèi)時，只要修改對應(yīng)葉子節(jié)點數(shù)據(jù)信息即可，不需要刪除后插入，也不也許引發(fā)分裂和合并操作53/72延遲更新更新操作包括刪除和插入兩個步驟，延遲更新也包括延遲刪除和延遲插入兩個方面。延遲刪除策略是將更新信息立即插入，而舊對象信息不會立即刪除，而是使用某種策略將未刪除索引信息緩存起來方便辨別新舊數(shù)據(jù)，直到緩沖區(qū)滿或者其他情況下才進行刪除操作54/72批量操作R樹批量插入策略是目前研究熱點之一。其中STLT(Small-Tree-Large-Tree)技術(shù)，首先利用輸入數(shù)據(jù)集建立一棵小R（Smalltree）樹，然后將小R樹插入到原有大R樹（Largetree）中55/72批量操作GBI（GeneralizedBulkInsertion）技術(shù)利用聚類算法將輸入數(shù)據(jù)集分割為多種空間上接近數(shù)據(jù)組，為每個數(shù)據(jù)組建立R樹構(gòu)造，最后將這些R樹構(gòu)造批量插入到目標R樹中56/72多版本文獻更新系統(tǒng)Versioning文獻系統(tǒng)保存被修改文獻之前版本，來實現(xiàn)顧客誤操作以及系統(tǒng)錯誤后數(shù)據(jù)恢復(fù)。Versioning文獻系統(tǒng)存在主要問題是不能有效地保存大量version，version數(shù)據(jù)消耗大量存放空間，對version刪除策略，恢復(fù)系統(tǒng)時version選擇問題等57/72多版本文獻更新系統(tǒng)Cedar采取簡單version策略來幫助客戶在誤操作后恢復(fù)數(shù)據(jù)。近來Elephant文獻系統(tǒng)提供了一系列version選項，用來保存對顧客最為主要文獻version。58/72多版本文獻更新系統(tǒng)CVFS提出兩種有效節(jié)省空間version元數(shù)據(jù)構(gòu)造，對于inodes和indirectblocks采取Journal-based元數(shù)據(jù)，而對于目錄采取MultiversionB樹，有效地節(jié)省了version占用空間。59/72多版本文獻更新系統(tǒng)Causality-basedversioning結(jié)合causalrelationship和versioning技術(shù)，通過causalconnection使得version更具意義，提出新在何時創(chuàng)建version算法；通過causalrelationship定位version，能夠更有效在錯誤后恢復(fù)到正確version60/72面向估計算元數(shù)據(jù)組織構(gòu)造－數(shù)據(jù)立方體數(shù)據(jù)立方體（DataCube）是分析數(shù)據(jù)倉庫數(shù)據(jù)基本單位，是聯(lián)機分析處理（On-LineAnalyticalProcessing,OLAP）中主要對象，是一項可對數(shù)據(jù)倉庫中數(shù)據(jù)進行迅速訪問技術(shù)。數(shù)據(jù)立方體是一種數(shù)據(jù)集合，一般由數(shù)據(jù)倉庫子集構(gòu)造，并組織和匯總成一種由一組維度和度量值定義多維構(gòu)造。數(shù)據(jù)立方體提供一種便于使用查詢數(shù)據(jù)機制，響應(yīng)時間短61/72數(shù)據(jù)立方體數(shù)據(jù)立方體是多維數(shù)據(jù)庫基本構(gòu)造，并作為在多維數(shù)據(jù)庫上定義所有操作符輸入輸出基本單位。將它定義為一種四元組<D，M，A，f>，這四個組件分別表達數(shù)據(jù)立方體特性62/72數(shù)據(jù)立方體在典型OLAP應(yīng)用中，存在一種中心關(guān)系或數(shù)據(jù)集合，稱作事實表。事實表代表感愛好事件或?qū)ο?。事實表一般有幾個表達維屬性和一種或多種度量屬性，這些度量屬性一般是顧客想要查詢到某些值63/72維數(shù)據(jù)