【正文】 ? 當(dāng)立方體的維度比較高時(shí)，對(duì)完全物化策略的立方體進(jìn)行更新維護(hù)將耗費(fèi)大量的時(shí)間和系統(tǒng)資源。并不是每次更新都需要一個(gè)至上而下的刪除操作和插入操作。 ? Bloom filter算法的一個(gè)缺點(diǎn)在于查詢(xún)一個(gè)元素是否在集合 S上可能存在失誤定位 (False Positive) ? 集合表示和元素查詢(xún) ? 下面我們具體來(lái)看 Bloom Filter是如何用位數(shù)組表示集合的。 ? 如果索引是磁盤(pán)駐留的，則每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)磁盤(pán)頁(yè)，以節(jié)點(diǎn)為單位讀取和寫(xiě)入。 ? 現(xiàn)在的爬行算法（ crawling method）非常慢而且消耗系統(tǒng)資源 海量元數(shù)據(jù)查詢(xún)需求分析 ? 快速可擴(kuò)展的索引查詢(xún)和更新 ? 查詢(xún)必須快速，甚至隨著系統(tǒng)規(guī)模的擴(kuò)大，性能依舊能保持很好，能夠快速周期性的對(duì)元數(shù)據(jù)索引進(jìn)行更新。物聯(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ù)查詢(xún)需求分析 ? 物聯(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)狀分析 ? 大規(guī)模存儲(chǔ)系統(tǒng)的應(yīng)用越來(lái)越廣泛，存儲(chǔ)容量也從以前的 TB（ Terabyte）級(jí)上升到 PB（ Petabyte）級(jí)甚至 EB（ Exabyte）級(jí)。 ? 但是，現(xiàn)存的系統(tǒng)一般都采用通用型的關(guān)系型數(shù)據(jù)庫(kù)來(lái)索引元數(shù)據(jù)。 ? 該結(jié)構(gòu)設(shè)計(jì)使得空間搜索只需要訪(fǎng)問(wèn)一小部分的節(jié)點(diǎn)，大大提高檢索效率。初始狀態(tài)時(shí)， Bloom Filter是一個(gè)包含 m位的位數(shù)組，每一位都置為 0。 ? 當(dāng)一個(gè)對(duì)象的新位置沒(méi)有移出原來(lái)的 MBR，換句話(huà)說(shuō)就是該對(duì)象還在同一個(gè)葉子節(jié)點(diǎn)內(nèi)時(shí)， ? 只要修改對(duì)應(yīng)葉子節(jié)點(diǎn)的數(shù)據(jù)信息即可，不需要?jiǎng)h除后插入，也不可能引起分裂和合并操作 延遲更新 ? 更新操作包括刪除和插入兩個(gè)步驟，延遲更新也包括延遲刪除和延遲插入兩個(gè)方面。完全物化主要有多路數(shù)組聚集方法 不預(yù)先計(jì)算任何的方體（不物化， No Materialization） ? 數(shù)據(jù)立方體中每一個(gè)方體都不對(duì)聚集度量 M進(jìn)行預(yù)計(jì)算， ? 相當(dāng)于只提供一個(gè)多維的索引，這樣對(duì)于用戶(hù)提交的查詢(xún)， ? 需要在線(xiàn)計(jì)算結(jié)果，響應(yīng)時(shí)間較長(zhǎng)。 預(yù)先計(jì)算任何方體，即完全立方體物化（ Full Materialization） ? 計(jì)算代價(jià)非常大，而且消耗大量的存儲(chǔ)空間和系統(tǒng)資源， ? 同時(shí)當(dāng)它的數(shù)據(jù)源發(fā)生改變時(shí)，為了保持?jǐn)?shù)據(jù)的一致性，需要重新的計(jì)算所有的方體。 ? 已經(jīng)存在的各種基于 R樹(shù)索引的更新機(jī)制主要采取的是自頂向下模式 減少更新操作的方法 ? 位置預(yù)測(cè) ? 一種減少對(duì)象更新操作次數(shù)的策略是采用線(xiàn)性函數(shù)來(lái)表示移動(dòng)對(duì)象的位置， ? 保存對(duì)象的運(yùn)動(dòng)特性，包括當(dāng)前位置和速度參數(shù)等， ? 通過(guò)這些數(shù)據(jù)可以預(yù)測(cè)將來(lái)一段時(shí)間后的位置 減少更新操作的方法 ? 容忍更新 ? 減少更新次數(shù)的另一種策略是容忍更新。 ? 由一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成， ? 它只需要哈希表 1/8 到 1/4 的大小就能解決同樣規(guī)模的集合的查詢(xún)問(wèn)題 Bloom filter Bloom filter ? Bloom filter的本質(zhì)是哈希計(jì)算，不同之處在于Bloom filter對(duì)同一數(shù)據(jù)使用多個(gè)哈希函數(shù)進(jìn)行多次哈希，將結(jié)果保存在同一個(gè)向量數(shù)組中， ? 所以 Bloom filter在達(dá)到相同的功能的情況下比原始的哈希結(jié)構(gòu)更節(jié)約存儲(chǔ)空間。 ? 系統(tǒng)耗費(fèi)一定的存儲(chǔ)空間維護(hù)空間索引結(jié)構(gòu)，在提供各種復(fù)雜查詢(xún)服務(wù)時(shí)可以有效的減少查詢(xún)時(shí)間延遲 相關(guān)研究工作 : R樹(shù)結(jié)構(gòu) ? 與 B樹(shù)相似， R樹(shù)是一種高度平衡的樹(shù)，它的葉子節(jié)點(diǎn)的記錄包含數(shù)據(jù)對(duì)象的指針。 ? 現(xiàn)在大多數(shù)的元數(shù)據(jù)查詢(xún)系統(tǒng)都需要專(zhuān)門(mén)的CPU、內(nèi)存以及磁盤(pán)， ? 使得它們非常昂貴而且很難部署，這就限制它們的擴(kuò)展性 海量元數(shù)據(jù)查詢(xún)需求分析 ? 快速的元數(shù)據(jù)收集 ? 必須從幾十億、幾百億個(gè)文件中周期性的收集發(fā)生改變的元數(shù)據(jù)， ? 而不會(huì)給整個(gè)存儲(chǔ)系統(tǒng)帶來(lái)額外負(fù)載，使得系統(tǒng)變慢。 ? 隨著存儲(chǔ)系統(tǒng)規(guī)模不斷增大，在大規(guī)模文件系統(tǒng)中，文件的數(shù)量高達(dá)幾十億個(gè)，在這種海量數(shù)據(jù)中查找和管理文件變得異常困難。 ? DBMS常常使用重量級(jí)的鎖和事務(wù)，這給系統(tǒng)增加負(fù)載 海量元數(shù)據(jù)查詢(xún)需求分析 ? 易用的查詢(xún)接口 ? 大多數(shù)系統(tǒng)輸出簡(jiǎn)單的查詢(xún)應(yīng)用程序接口， ? 但是研究表明專(zhuān)門(mén)設(shè)計(jì)的接口能夠很好表達(dá)且容易使用， ? 這會(huì)大大提升查詢(xún)體驗(yàn)。 ? 索引結(jié)構(gòu)是完全動(dòng)態(tài)的；插入、刪除和查找操作能同時(shí)進(jìn)行而且不需要定期地對(duì)樹(shù)的結(jié)構(gòu)進(jìn)行重新組織 相關(guān)研究工作 :B樹(shù)、 B樹(shù)、B+樹(shù)、 B*樹(shù) ? B樹(shù) 即二叉搜索樹(shù)： （ Left和 Right）； ； 于其關(guān)鍵字的子樹(shù)，右指針 指向大于其關(guān)鍵字的