物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析(ppt72頁(yè))-文庫(kù)吧資料
2025-01-25 19:18本頁(yè)面
【正文】 算法 Bloom filter Bloom filter RBF索引結(jié)構(gòu) ? 從 B樹(shù)演變而來(lái)的 R樹(shù)結(jié)構(gòu)，能有效地支持多維范圍查詢。下圖中 y1就不是集合中的元素。在下圖中， k=3，且有兩個(gè)哈希函數(shù)選中同一個(gè)位置（從左邊數(shù)第五位）。對(duì)任意一個(gè)元素 x，第 i個(gè)哈希函數(shù)映射的位置 hi(x)就會(huì)被置為 1（ 1≤i≤k）。初始狀態(tài)時(shí)， Bloom Filter是一個(gè)包含 m位的位數(shù)組，每一位都置為 0。 ? 由一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)組和一系列隨機(jī)映射函數(shù)組成， ? 它只需要哈希表 1/8 到 1/4 的大小就能解決同樣規(guī)模的集合的查詢問(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ǔ)空間。因此， Bloom Filter不適合那些“ 零錯(cuò)誤 ” 的應(yīng)用場(chǎng)合。 R樹(shù)的空間分布圖 Bloom filter ? Bloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。 相關(guān)研究工作 : R樹(shù)結(jié)構(gòu) R 1 R 2R 3 R 4 R 5 R 6R 7 R 8 R 9 R 1 0 R 1 1 R 1 2 R 1 3 R 1 4 R 1 5? 特點(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樹(shù)兄弟結(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域可以重疊，可以較容易地進(jìn)行插入和刪除操作。 ? R樹(shù)的葉節(jié)點(diǎn)按以下形式記錄索引記錄的入口 比較典型的有 R+樹(shù)、 R ? 一個(gè)空間數(shù)據(jù)庫(kù)由代表對(duì)象的的集合組成。 R樹(shù)的每一個(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é)構(gòu)設(shè)計(jì)使得空間搜索只需要訪問(wèn)一小部分的節(jié)點(diǎn)，大大提高檢索效率。 ? 系統(tǒng)耗費(fèi)一定的存儲(chǔ)空間維護(hù)空間索引結(jié)構(gòu)，在提供各種復(fù)雜查詢服務(wù)時(shí)可以有效的減少查詢時(shí)間延遲 相關(guān)研究工作 : R樹(shù)結(jié)構(gòu) ? 與 B樹(shù)相似， R樹(shù)是一種高度平衡的樹(shù)，它的葉子節(jié)點(diǎn)的記錄包含數(shù)據(jù)對(duì)象的指針。 ? 基于數(shù)據(jù)的分割方法有 R樹(shù)， Cell樹(shù)等，按照數(shù)據(jù)的分布特性逐層劃分空間 多維元數(shù)據(jù)組織結(jié)構(gòu) ? 如果系統(tǒng)基于每個(gè)維度單獨(dú)建立索引，則需要對(duì)每個(gè)維度進(jìn)行查找之后將結(jié)果做交集。 ? 目前存在大量的空間數(shù)據(jù)索引方法 多維元數(shù)據(jù)組織結(jié)構(gòu) ? 一般來(lái)說(shuō)，常見(jiàn)的多維空間數(shù)據(jù)索引有兩種數(shù)據(jù)組織方式：基于規(guī)則的分割方法和基于數(shù)據(jù)的分割方法。 ? 第五、良好的伸縮性及可用性。 ? 第四、接口靈活好用。 物聯(lián)網(wǎng)元數(shù)據(jù)管理系統(tǒng)設(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ù)的管理和訪問(wèn)等問(wèn)題； ? 第二、查找和更新速度必須快且可靠。 ? 但是，現(xiàn)存的系統(tǒng)一般都采用通用型的關(guān)系型數(shù)據(jù)庫(kù)來(lái)索引元數(shù)據(jù)。 ? 現(xiàn)在大多數(shù)的元數(shù)據(jù)查詢系統(tǒng)都需要專門的CPU、內(nèi)存以及磁盤， ? 使得它們非常昂貴而且很難部署，這就限制它們的擴(kuò)展性 海量元數(shù)據(jù)查詢需求分析 ? 快速的元數(shù)據(jù)收集 ? 必須從幾十億、幾百億個(gè)文件中周期性的收集發(fā)生改變的元數(shù)據(jù)， ? 而不會(huì)給整個(gè)存儲(chǔ)系統(tǒng)帶來(lái)額外負(fù)載，使得系統(tǒng)變慢。 ? 認(rèn)識(shí)到現(xiàn)有文件系統(tǒng)的不足，學(xué)術(shù)界和工業(yè)界都做了大量的工作來(lái)研究如何利用豐富的元數(shù)據(jù)信息來(lái)提高文件的管理和搜索效率 海量元數(shù)據(jù)查詢需求分析 ? 在大規(guī)模存儲(chǔ)系統(tǒng)中查找和管理文件顯得更加困難， ? 元數(shù)據(jù)查詢可以很好的解決點(diǎn)查詢、范圍查詢、 topk查詢以及聚集查詢， ? 便于進(jìn)行一些復(fù)雜、特殊的查詢。 ? 訪問(wèn)某個(gè)文件必須通過(guò)層次型的目錄樹(shù)結(jié)構(gòu)到達(dá)文件的保存位置， ? 如果不知道文件保存位置，就必須遍歷整個(gè)目錄或使用操作系統(tǒng)的搜索功能， ? 而操作系統(tǒng)僅能依靠文件名來(lái)檢索和查找數(shù)據(jù)。 物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析 ? 從而使得一些復(fù)雜查詢非常耗時(shí)、效率低下， ? 不能有效地支持用戶或管理者查找到想要的文件，或得到想要的數(shù)據(jù)。 ? 準(zhǔn)確地回答這些問(wèn)題能夠極大的提高用戶和管理者管理大規(guī)模存儲(chǔ)系統(tǒng)中的文件。 ? 利用文件屬性，元數(shù)據(jù)查詢?cè)试S點(diǎn)查詢、范圍查詢、 topk查詢和聚集查詢， ? 這些使得復(fù)雜的、特定的查詢變得簡(jiǎn)單。 物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)現(xiàn)狀分析 ? 這與互聯(lián)網(wǎng)環(huán)境形成了鮮明的對(duì)比： ? 由于搜索引擎技術(shù)的發(fā)展，在互聯(lián)網(wǎng)的環(huán)境下查找信息很方便
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1