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

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

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

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

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

2.所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字；

3.非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹； 如：相關(guān)研究工作:B樹、B-樹、B+樹、B*樹B樹即二叉搜索B樹

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)的關(guā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樹

B樹的搜索，從根結(jié)點(diǎn)開始，如果查詢的關(guān)鍵字與結(jié)點(diǎn)的B樹B樹

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

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

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)鍵字：K[1],K[2],…,K[M-1]；且K[i]<K[i+1]；

7.非葉子結(jié)點(diǎn)的指針：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é)點(diǎn)位于同一層； 如：（M=3）B-樹 是一種多路搜索樹（并不是二叉的）：B-樹B樹B樹 B+樹是B-樹的變體，也是一種多路搜索樹：

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

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

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

5.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；

6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)； 如：（M=3）B+樹 B+樹是B-樹的變體，也是一種多路搜索樹：B+樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹定義了非葉子結(jié)點(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)的概率比B+樹要低，空間使用率更高；B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指 B樹：二叉樹，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)；

B-樹：多路搜索樹，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)； 所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中；

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

B*樹：在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3；相關(guān)研究工作:B樹、B-樹、B+樹、B*樹 B樹：二叉樹，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走相關(guān)研究工作:R樹結(jié)構(gòu)

R樹是一個(gè)高度平衡樹，它是B樹在k維上的自然擴(kuò)展，用空間對(duì)象的MBR來近似表達(dá)空間對(duì)象，根據(jù)地物的MBR建立R樹，可以直接對(duì)空間中占據(jù)一定范圍的空間對(duì)象進(jìn)行索引。R樹的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著磁盤頁(yè)D和區(qū)域I，如果結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則該結(jié)點(diǎn)的所有子結(jié)點(diǎn)的區(qū)域都在區(qū)域I的范圍之內(nèi)，而且存儲(chǔ)在磁盤頁(yè)D中。如果結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么磁盤頁(yè)D中存儲(chǔ)的將是區(qū)域I范圍內(nèi)的一系列子區(qū)域，子區(qū)域緊緊圍繞空間對(duì)象，一般為空間對(duì)象的外接矩形。一個(gè)空間數(shù)據(jù)庫(kù)由代表對(duì)象的的集合組成。每個(gè)對(duì)象元組都有一個(gè)唯一的標(biāo)識(shí)符，可通過這些標(biāo)識(shí)符來檢索對(duì)象元組。R樹的葉節(jié)點(diǎn)按以下形式記錄索引記錄的入口比較典型的有R+樹、R·樹、壓縮R樹等。相關(guān)研究工作:R樹結(jié)構(gòu)R樹是一個(gè)高度平衡樹，它是B樹在k相關(guān)研究工作:R樹結(jié)構(gòu)特點(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é)果。相關(guān)研究工作:R樹結(jié)構(gòu)特點(diǎn)；R樹的空間分布圖R樹的空間分布圖BloomfilterBloomFilter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。BloomFilter的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（falsepositive）。因此，BloomFilter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，BloomFilter通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。BloomfilterBloomFilter是一種空間效由一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成，它只需要哈希表1/8到1/4的大小就能解決同樣規(guī)模的集合的查詢問題Bloomfilter由一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成，BlooBloomfilterBloomfilter的本質(zhì)是哈希計(jì)算，不同之處在于Bloomfilter對(duì)同一數(shù)據(jù)使用多個(gè)哈希函數(shù)進(jìn)行多次哈希，將結(jié)果保存在同一個(gè)向量數(shù)組中，所以Bloomfilter在達(dá)到相同的功能的情況下比原始的哈希結(jié)構(gòu)更節(jié)約存儲(chǔ)空間。Bloomfilter算法的一個(gè)缺點(diǎn)在于查詢一個(gè)元素是否在集合S上可能存在失誤定位(FalsePositive)BloomfilterBloomfilter的本質(zhì)是哈集合表示和元素查詢下面我們具體來看BloomFilter是如何用位數(shù)組表示集合的。初始狀態(tài)時(shí)，BloomFilter是一個(gè)包含m位的位數(shù)組，每一位都置為0。Bloomfilter集合表示和元素查詢Bloomfilter為了表達(dá)S={x1,x2,…,xn}這樣一個(gè)n個(gè)元素的集合，BloomFilter使用k個(gè)相互獨(dú)立的哈希函數(shù)（HashFunction），它們分別將集合中的每個(gè)元素映射到{1,…,m}的范圍中。對(duì)任意一個(gè)元素x，第i個(gè)哈希函數(shù)映射的位置hi(x)就會(huì)被置為1（1≤i≤k）。注意，如果一個(gè)位置多次被置為1，那么只有第一次會(huì)起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個(gè)哈希函數(shù)選中同一個(gè)位置（從左邊數(shù)第五位）。Bloomfilter為了表達(dá)S={x1,x2,…,xn}這樣一個(gè)n個(gè)元素的集合在判斷y是否屬于這個(gè)集合時(shí)，我們對(duì)y應(yīng)用k次哈希函數(shù)，如果所有hi(y)的位置都是1（1≤i≤k），那么我們就認(rèn)為y是集合中的元素，否則就認(rèn)為y不是集合中的元素。下圖中y1就不是集合中的元素。y2或者屬于這個(gè)集合，或者剛好是一個(gè)falsepositive。

算法Bloomfilter

Bloomfilter在判斷y是否屬于這個(gè)集合時(shí)，我們對(duì)y應(yīng)用k次哈希函數(shù)，如果所RBF索引結(jié)構(gòu)從B樹演變而來的R樹結(jié)構(gòu)，能有效地支持多維范圍查詢。但是，R樹不能有效地支持點(diǎn)查詢。因?yàn)槌蓡T查詢只能在葉子節(jié)點(diǎn)上進(jìn)行，相應(yīng)的操作將導(dǎo)致查詢效率很低。然而，Bloomfilter是一種空間利用率高且能有效地支持點(diǎn)查詢的結(jié)構(gòu)。RBF索引結(jié)構(gòu)從B樹演變而來的R樹結(jié)構(gòu)，能有效地支持多維范RBF索引結(jié)構(gòu)一種叫做RBF的新的空間存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)多維元數(shù)據(jù)，基本思路是是擴(kuò)展經(jīng)典的R樹結(jié)構(gòu)，將Bloomfilter插入到每個(gè)R樹結(jié)點(diǎn)上來支持點(diǎn)查詢，維持多維范圍信息并實(shí)現(xiàn)空間效率RBF索引結(jié)構(gòu)一種叫做RBF的新的空間存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)多維元數(shù)RBF索引結(jié)構(gòu)RBF索引結(jié)構(gòu)面向數(shù)據(jù)更新的結(jié)構(gòu)設(shè)計(jì)和分析R樹更新基于R樹的索引在商業(yè)上得到廣泛應(yīng)用和發(fā)展，但是它在頻繁更新操作時(shí)性能低下。R樹及其變體在空間索引結(jié)構(gòu)中占據(jù)主導(dǎo)地位，面向數(shù)據(jù)更新的結(jié)構(gòu)設(shè)計(jì)和分析R樹更新R樹更新傳統(tǒng)的空間索引的研究主要考慮靜態(tài)數(shù)據(jù)，只關(guān)注高效的查詢處理，R樹的更新性能很差，不能直接用于頻繁更新的應(yīng)用環(huán)境R樹更新傳統(tǒng)的空間索引的研究主要考慮靜態(tài)數(shù)據(jù)，R樹更新存儲(chǔ)系統(tǒng)下元數(shù)據(jù)的更新是很頻繁的，直接對(duì)索引的修改會(huì)產(chǎn)生大量的磁盤操作并可能引起索引結(jié)構(gòu)的不平衡。已經(jīng)存在的各種基于R樹索引的更新機(jī)制主要采取的是自頂向下模式R樹更新存儲(chǔ)系統(tǒng)下元數(shù)據(jù)的更新是很頻繁的，減少更新操作的方法位置預(yù)測(cè)一種減少對(duì)象更新操作次數(shù)的策略是采用線性函數(shù)來表示移動(dòng)對(duì)象的位置，保存對(duì)象的運(yùn)動(dòng)特性，包括當(dāng)前位置和速度參數(shù)等，通過這些數(shù)據(jù)可以預(yù)測(cè)將來一段時(shí)間后的位置減少更新操作的方法位置預(yù)測(cè)減少更新操作的方法容忍更新減少更新次數(shù)的另一種策略是容忍更新。并不是每次更新都需要一個(gè)至上而下的刪除操作和插入操作。當(dāng)一個(gè)對(duì)象的新位置沒有移出原來的MBR，換句話說就是該對(duì)象還在同一個(gè)葉子節(jié)點(diǎn)內(nèi)時(shí)，只要修改對(duì)應(yīng)葉子節(jié)點(diǎn)的數(shù)據(jù)信息即可，不需要?jiǎng)h除后插入，也不可能引起分裂和合并操作減少更新操作的方法容忍更新延遲更新更新操作包括刪除和插入兩個(gè)步驟，延遲更新也包括延遲刪除和延遲插入兩個(gè)方面。延遲刪除的策略是將更新信息立即插入，而舊的對(duì)象信息不會(huì)立即刪除，而是使用某種策略將未刪除的索引信息緩存起來以便區(qū)分新舊數(shù)據(jù)，直到緩沖區(qū)滿或者其它情況下才進(jìn)行刪除操作延遲更新更新操作包括刪除和插入兩個(gè)步驟，延遲更新也包括延遲批量操作R樹的批量插入策略是當(dāng)前研究的熱點(diǎn)之一。其中STLT(Small-Tree-Large-Tree)技術(shù)，首先利用輸入數(shù)據(jù)集建立一棵小R（Smalltree）樹，然后將小R樹插入到原有的大R樹（Largetree）中批量操作R樹的批量插入策略是當(dāng)前研究的熱點(diǎn)之一。批量操作GBI（GeneralizedBulkInsertion）技術(shù)利用聚類算法將輸入數(shù)據(jù)集分割為多個(gè)空間上接近的數(shù)據(jù)組，為每個(gè)數(shù)據(jù)組建立R樹結(jié)構(gòu)，最后將這些R樹結(jié)構(gòu)批量插入到目標(biāo)R樹中批量操作GBI（GeneralizedBulkInser多版本文件更新系統(tǒng)Versioning文件系統(tǒng)保存被修改的文件之前的版本，來實(shí)現(xiàn)用戶誤操作以及系統(tǒng)錯(cuò)誤后的數(shù)據(jù)恢復(fù)。Versioning文件系統(tǒng)存在的主要問題是不能有效地保存大量的version，version數(shù)據(jù)消耗大量的存儲(chǔ)空間，對(duì)version的刪除的策略，恢復(fù)系統(tǒng)時(shí)version的選擇問題等多版本文件更新系統(tǒng)Versioning文件系統(tǒng)保存被修改的多版本文件更新系統(tǒng)Cedar采用簡(jiǎn)單的version策略來幫助客戶在誤操作后恢復(fù)數(shù)據(jù)。最近的Elephant文件系統(tǒng)提供了一系列的version選項(xiàng)，用來保存對(duì)用戶最為重要的文件的version。多版本文件更新系統(tǒng)Cedar采用簡(jiǎn)單的version策略來幫多版本文件更新系統(tǒng)CVFS提出兩種有效節(jié)省空間的version元數(shù)據(jù)結(jié)構(gòu)，對(duì)于inodes和indirectblocks采用Journal-based元數(shù)據(jù)，而對(duì)于目錄采用MultiversionB樹，有效地節(jié)省了version占用的空間。多版本文件更新系統(tǒng)CVFS提出兩種有效節(jié)省空間的versio多版本文件更新系統(tǒng)Causality-basedversioning結(jié)合causalrelationship和versioning技術(shù)，通過causalconnection使得version更具意義，提出新的在何時(shí)創(chuàng)建version的算法；通過causalrelationship定位version，能夠更有效的在錯(cuò)誤后恢復(fù)到正確的version多版本文件更新系統(tǒng)Causality-basedversi面向預(yù)計(jì)算的元數(shù)據(jù)組織結(jié)構(gòu)－數(shù)據(jù)立方體數(shù)據(jù)立方體（DataCube）是分析數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)的基本單位，是聯(lián)機(jī)分析處理（On-LineAnalyticalProcessing,OLAP）中的主要對(duì)象，是一項(xiàng)可對(duì)數(shù)據(jù)倉(cāng)庫(kù)中的數(shù)據(jù)進(jìn)行快速訪問的技術(shù)。數(shù)據(jù)立方體是一個(gè)數(shù)據(jù)集合，通常由數(shù)據(jù)倉(cāng)庫(kù)的子集構(gòu)造，并組織和匯總成一個(gè)由一組維度和度量值定義的多維結(jié)構(gòu)。數(shù)據(jù)立方體提供一種便于使用的查詢數(shù)據(jù)機(jī)制，響應(yīng)時(shí)間短面向預(yù)計(jì)算的元數(shù)據(jù)組織結(jié)構(gòu)－數(shù)據(jù)立方體數(shù)據(jù)立方體（Data數(shù)據(jù)立方體數(shù)據(jù)立方體是多維數(shù)據(jù)庫(kù)的基本結(jié)構(gòu)，并作為在多維數(shù)據(jù)庫(kù)上定義的所有操作符的輸入輸出基本單位。將它定義為一個(gè)四元組<D，M，A，f>，這四個(gè)組件分別表示數(shù)據(jù)立方體的特征數(shù)據(jù)立方體數(shù)據(jù)立方體是多維數(shù)據(jù)庫(kù)的基本結(jié)構(gòu)，數(shù)據(jù)立方體在典型的OLAP應(yīng)用中，存在一個(gè)中心關(guān)系或數(shù)據(jù)集合，稱作事實(shí)表。事實(shí)表代表感興趣的事件或?qū)ο?。事?shí)表通常有幾個(gè)表示維的屬性和一個(gè)或多個(gè)度量屬性，這些度量屬性一般是用戶想要查詢到的一些值數(shù)據(jù)立方體在典型的OLAP應(yīng)用中，存在一個(gè)中心關(guān)系或數(shù)據(jù)集合維數(shù)據(jù)立方體表示維數(shù)據(jù)立方體表示數(shù)據(jù)立方體的計(jì)算數(shù)據(jù)立方體的計(jì)算是數(shù)據(jù)倉(cāng)庫(kù)實(shí)現(xiàn)的一項(xiàng)基本任務(wù)，數(shù)據(jù)立方體計(jì)算也稱為數(shù)據(jù)立方體的物化（Materialization）簡(jiǎn)單的說，它是將常用的查詢按照各自的屬性分組（Groupby）提前計(jì)算出結(jié)果并保存起來，這樣在執(zhí)行查詢時(shí)直接利用保存的結(jié)果來返回查詢結(jié)果。數(shù)據(jù)立方體的全部或部分預(yù)計(jì)算可以大幅降低響應(yīng)時(shí)間，提高查詢效率，提高聯(lián)機(jī)分析處理性能數(shù)據(jù)立方體的計(jì)算數(shù)據(jù)立方體的計(jì)算是數(shù)據(jù)倉(cāng)庫(kù)實(shí)現(xiàn)的一項(xiàng)基本任預(yù)先計(jì)算任何方體，即完全立方體物化（FullMaterialization）

完全物化優(yōu)點(diǎn)：可以對(duì)提出的任何查詢快速響應(yīng)，快速返回預(yù)計(jì)算好的結(jié)果，不用在線等待計(jì)算結(jié)果，提高交互性。缺點(diǎn)：完全物化時(shí)間復(fù)雜度是維度的指數(shù)，隨著維度的增大，將發(fā)生困難。預(yù)先計(jì)算任何方體，即完全立方體物化（FullMateria預(yù)先計(jì)算任何方體，即完全立方體物化（FullMaterialization）計(jì)算代價(jià)非常大，而且消耗大量的存儲(chǔ)空間和系統(tǒng)資源，同時(shí)當(dāng)它的數(shù)據(jù)源發(fā)生改變時(shí)，為了保持?jǐn)?shù)據(jù)的一致性，需要重新的計(jì)算所有的方體。當(dāng)立方體的維度比較高時(shí)，對(duì)完全物化策略的立方體進(jìn)行更新維護(hù)將耗費(fèi)大量的時(shí)間和系統(tǒng)資源。完全物化主要有多路數(shù)組聚集方法預(yù)先計(jì)算任何方體，即完全立方體物化（FullMateria不預(yù)先計(jì)算任何的方體（不物化，NoMaterialization）

數(shù)據(jù)立方體中每一個(gè)方體都不對(duì)聚集度量M進(jìn)行預(yù)計(jì)算，相當(dāng)于只提供一個(gè)多維的索引，這樣對(duì)于用戶提交的查詢，需要在線計(jì)算結(jié)果，響應(yīng)時(shí)間較長(zhǎng)。不預(yù)先計(jì)算任何的方體（不物化，NoMaterializat不預(yù)先計(jì)算任何的方體（不物化，NoMaterialization）

當(dāng)總的數(shù)據(jù)量很大時(shí)，那查詢的結(jié)果集也會(huì)很大，在線計(jì)算將需要很長(zhǎng)的時(shí)間，從而導(dǎo)致無法忍受的響應(yīng)時(shí)間，在海量數(shù)據(jù)情況下，該策略是不可取的不預(yù)先計(jì)算任何的方體（不物化，NoMaterializat部分物化提供了存儲(chǔ)空間和響應(yīng)時(shí)間的有效折衷。替代計(jì)算完全立方體，可以計(jì)算立方體的一個(gè)子集，或計(jì)算由各種方體的單元組成的子立方體。優(yōu)點(diǎn)是節(jié)省了大量的計(jì)算時(shí)間和存儲(chǔ)空間；缺點(diǎn)是只能命中大部分查詢而且結(jié)果可能不太精確，對(duì)于沒命中的查詢需要在線計(jì)算部分物化提供了存儲(chǔ)空間和響應(yīng)時(shí)間的有效折衷。替代計(jì)算完全立方部分物化在許多情況下，相當(dāng)多的立方體空間可能被大量具有很低度量值的單元占據(jù)。這是因?yàn)榱⒎襟w單元在多維空間中的分布常常是相當(dāng)稀疏的。部分物化在許多情況下，相當(dāng)多的立方體空間可能被大量具有很低度部分物化某一類型的文件非常少，這樣的事件將產(chǎn)生少量非空單元，使得其他大部分立方體單元為空。在這種情況下僅物化其度量值大于某個(gè)最小閾值的方體（Groupby）單元是很有用的部分物化某一類型的文件非常少，這樣的事件將產(chǎn)生少量非空單元，物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及

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

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

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

2.所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字；

3.非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹； 如：相關(guān)研究工作:B樹、B-樹、B+樹、B*樹B樹即二叉搜索B樹

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)的關(guā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樹

B樹的搜索，從根結(jié)點(diǎn)開始，如果查詢的關(guān)鍵字與結(jié)點(diǎn)的B樹B樹

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

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

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)鍵字：K[1],K[2],…,K[M-1]；且K[i]<K[i+1]；

7.非葉子結(jié)點(diǎn)的指針：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é)點(diǎn)位于同一層； 如：（M=3）B-樹 是一種多路搜索樹（并不是二叉的）：B-樹B樹B樹 B+樹是B-樹的變體，也是一種多路搜索樹：

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

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

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

5.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；

6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)； 如：（M=3）B+樹 B+樹是B-樹的變體，也是一種多路搜索樹：B+樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹定義了非葉子結(jié)點(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)的概率比B+樹要低，空間使用率更高；B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指 B樹：二叉樹，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)；

B-樹：多路搜索樹，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)； 所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中；

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

B*樹：在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3；相關(guān)研究工作:B樹、B-樹、B+樹、B*樹 B樹：二叉樹，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走相關(guān)研究工作:R樹結(jié)構(gòu)

R樹是一個(gè)高度平衡樹，它是B樹在k維上的自然擴(kuò)展，用空間對(duì)象的MBR來近似表達(dá)空間對(duì)象，根據(jù)地物的MBR建立R樹，可以直接對(duì)空間中占據(jù)一定范圍的空間對(duì)象進(jìn)行索引。R樹的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著磁盤頁(yè)D和區(qū)域I，如果結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則該結(jié)點(diǎn)的所有子結(jié)點(diǎn)的區(qū)域都在區(qū)域I的范圍之內(nèi)，而且存儲(chǔ)在磁盤頁(yè)D中。如果結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么磁盤頁(yè)D中存儲(chǔ)的將是區(qū)域I范圍內(nèi)的一系列子區(qū)域，子區(qū)域緊緊圍繞空間對(duì)象，一般為空間對(duì)象的外接矩形。一個(gè)空間數(shù)據(jù)庫(kù)由代表對(duì)象的的集合組成。每個(gè)對(duì)象元組都有一個(gè)唯一的標(biāo)識(shí)符，可通過這些標(biāo)識(shí)符來檢索對(duì)象元組。R樹的葉節(jié)點(diǎn)按以下形式記錄索引記錄的入口比較典型的有R+樹、R·樹、壓縮R樹等。相關(guān)研究工作:R樹結(jié)構(gòu)R樹是一個(gè)高度平衡樹，它是B樹在k相關(guān)研究工作:R樹結(jié)構(gòu)特點(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é)果。相關(guān)研究工作:R樹結(jié)構(gòu)特點(diǎn)；R樹的空間分布圖R樹的空間分布圖BloomfilterBloomFilter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。BloomFilter的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（falsepositive）。因此，BloomFilter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，BloomFilter通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。BloomfilterBloomFilter是一種空間效由一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成，它只需要哈希表1/8到1/4的大小就能解決同樣規(guī)模的集合的查詢問題Bloomfilter由一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成，BlooBloomfilterBloomfilter的本質(zhì)是哈希計(jì)算，不同之處在于Bloomfilter對(duì)同一數(shù)據(jù)使用多個(gè)哈希函數(shù)進(jìn)行多次哈希，將結(jié)果保存在同一個(gè)向量數(shù)組中，所以Bloomfilter在達(dá)到相同的功能的情況下比原始的哈希結(jié)構(gòu)更節(jié)約存儲(chǔ)空間。Bloomfilter算法的一個(gè)缺點(diǎn)在于查詢一個(gè)元素是否在集合S上可能存在失誤定位(FalsePositive)BloomfilterBloomfilter的本質(zhì)是哈集合表示和元素查詢下面我們具體來看BloomFilter是如何用位數(shù)組表示集合的。初始狀態(tài)時(shí)，BloomFilter是一個(gè)包含m位的位數(shù)組，每一位都置為0。Bloomfilter集合表示和元素查詢Bloomfilter為了表達(dá)S={x1,x2,…,xn}這樣一個(gè)n個(gè)元素的集合，BloomFilter使用k個(gè)相互獨(dú)立的哈希函數(shù)（HashFunction），它們分別將集合中的每個(gè)元素映射到{1,…,m}的范圍中。對(duì)任意一個(gè)元素x，第i個(gè)哈希函數(shù)映射的位置hi(x)就會(huì)被置為1（1≤i≤k）。注意，如果一個(gè)位置多次被置為1，那么只有第一次會(huì)起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個(gè)哈希函數(shù)選中同一個(gè)位置（從左邊數(shù)第五位）。Bloomfilter為了表達(dá)S={x1,x2,…,xn}這樣一個(gè)n個(gè)元素的集合在判斷y是否屬于這個(gè)集合時(shí)，我們對(duì)y應(yīng)用k次哈希函數(shù)，如果所有hi(y)的位置都是1（1≤i≤k），那么我們就認(rèn)為y是集合中的元素，否則就認(rèn)為y不是集合中的元素。下圖中y1就不是集合中的元素。y2或者屬于這個(gè)集合，或者剛好是一個(gè)falsepositive。

算法Bloomfilter

Bloomfilter在判斷y是否屬于這個(gè)集合時(shí)，我們對(duì)y應(yīng)用k次哈希函數(shù)，如果所RBF索引結(jié)構(gòu)從B樹演變而來的R樹結(jié)構(gòu)，能有效地支持多維范圍查詢。但是，R樹不能有效地支持點(diǎn)查詢。因?yàn)槌蓡T查詢只能在葉子節(jié)點(diǎn)上進(jìn)行，相應(yīng)的操作將導(dǎo)致查詢效率很低。然而，Bloomfilter是一種空間利用率高且能有效地支持點(diǎn)查詢的結(jié)構(gòu)。RBF索引結(jié)構(gòu)從B樹演變而來的R樹結(jié)構(gòu)，能有效地支持多維范RBF索引結(jié)構(gòu)一種叫做RBF的新的空間存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)多維元數(shù)據(jù)，基本思路是是擴(kuò)展經(jīng)典的R樹結(jié)構(gòu)，將Bloomfilter插入到每個(gè)R樹結(jié)點(diǎn)上來支持點(diǎn)查詢，維持多維范圍信息并實(shí)現(xiàn)空間效率RBF索引結(jié)構(gòu)一種叫做RBF的新的空間存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)多維元數(shù)RBF索引結(jié)構(gòu)RBF索引結(jié)構(gòu)面向數(shù)據(jù)更新的結(jié)構(gòu)設(shè)計(jì)和分析R樹更新基于R樹的索引在商業(yè)上得到廣泛應(yīng)用和發(fā)展，但是它在頻繁更新操作時(shí)性能低下。R樹及其變體在空間索引結(jié)構(gòu)中占據(jù)主導(dǎo)地位，面向數(shù)據(jù)更新的結(jié)構(gòu)設(shè)計(jì)和分析R樹更新R樹更新傳統(tǒng)的空間索引的研究主要考慮靜態(tài)數(shù)據(jù)，只關(guān)注高效的查詢處理，R樹的更新性能很差，不能直接用于頻繁更新的應(yīng)用環(huán)境R樹更新傳統(tǒng)的空間索引的研究主要考慮靜態(tài)數(shù)據(jù)，R樹更新存儲(chǔ)系統(tǒng)下元數(shù)據(jù)的更新是很頻繁的，直接對(duì)索引的修改會(huì)產(chǎn)生大量的磁盤操作并可能引起索引結(jié)構(gòu)的不平衡。已經(jīng)存在的各種基于R樹索引的更新機(jī)制主要采取的是自頂向下模式R樹更新存儲(chǔ)系統(tǒng)下元數(shù)據(jù)的更新是很頻繁的，減少更新操作的方法位置預(yù)測(cè)一種減少對(duì)象更新操作次數(shù)的策略是采用線性函數(shù)來表示移動(dòng)對(duì)象的位置，保存對(duì)象的運(yùn)動(dòng)特性，包括當(dāng)前位置和速度參數(shù)等，通過這些數(shù)據(jù)可以預(yù)測(cè)將來一段時(shí)間后的位置減少更新操作的方法位置預(yù)測(cè)減少更新操作的方法容忍更新減少更新次數(shù)的另一種策略是容忍更新。并不是每次更新都需要一個(gè)至上而下的刪除操作和插入操作。當(dāng)一個(gè)對(duì)象的新位置沒有移出原來的MBR，換句話說就是該對(duì)象還在同一個(gè)葉子節(jié)點(diǎn)內(nèi)時(shí)，只要修改對(duì)應(yīng)葉子節(jié)點(diǎn)的數(shù)據(jù)信息即可，不需要?jiǎng)h除后插入，也不可能引起分裂和合并操作減少更新操作的方法容忍更新延遲更新更新操作包括刪除和插入兩個(gè)步驟，延遲更新也包括延遲刪除和延遲插入兩個(gè)方面。延遲刪除的策略是將更新信息立即插入，而舊的對(duì)象信息不會(huì)立即刪除，而是使用某種策略將未刪除的索引信息緩存起來以便區(qū)分新舊數(shù)據(jù)，直到緩沖區(qū)滿或者其它情況下才進(jìn)行刪除操作延遲更新更新操作包括刪除和插入兩個(gè)步驟，延遲更新也包括延遲批量操作R樹的批量插入策略是當(dāng)前研究的熱點(diǎn)之一。其中STLT(Small-Tree-Large-Tree)技術(shù)，首先利用輸入數(shù)據(jù)集建立一棵小R（Smalltree）樹，然后將小R樹插入到原有的大R樹（Largetree）中批量操作R樹的批量插入策略是當(dāng)前研究的熱點(diǎn)之一。批量操作GBI（GeneralizedBulkInsertion）技術(shù)利用聚類算法將輸入數(shù)據(jù)集分割為多個(gè)空間上接近的數(shù)據(jù)組，為每個(gè)數(shù)據(jù)組建立R樹結(jié)構(gòu)，最后將這些R樹結(jié)構(gòu)批量插入到目標(biāo)R樹中批量操作GBI（GeneralizedBulkInser多版本文件更新系統(tǒng)Versioning文件系統(tǒng)保存被修改的文件之前的版本，來實(shí)現(xiàn)用戶誤操作以及系統(tǒng)錯(cuò)誤后的數(shù)據(jù)恢復(fù)。Versioning文件系統(tǒng)存在的主要問題是不能有效地保存大量的version，version數(shù)