物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析(ppt72頁(yè))(編輯修改稿)
2025-02-08 19:18 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 多 M1個(gè)關(guān)鍵字；（至少 2個(gè)關(guān)鍵字） =指向兒子的指針個(gè)數(shù) 1； ： K[1], K[2], … , K[M1]；且 K[i] K[i+1]； ： P[1], P[2], … , P[M]；其中 P[1]指向關(guān)鍵字小于 K[1]的子樹(shù)， P[M]指向關(guān)鍵字大于 K[M1]的子樹(shù)，其它 P[i]指向關(guān)鍵字屬于 (K[i1], K[i])的子樹(shù)； ； 如：（ M=3） B樹(shù) B樹(shù) B+樹(shù)是 B樹(shù)的變體，也是一種多路搜索樹(shù)： B樹(shù)同，除了： ； P[i]，指向關(guān)鍵字值屬于 [K[i], K[i+1])的子樹(shù)（ B樹(shù)是開(kāi)區(qū)間）； ； ； 如：（ M=3） B+樹(shù) ? 是 B+樹(shù)的變體，在 B+樹(shù)的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針； ? B*樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為 (2/3)*M，即塊的最低使用率為 2/3（代替 B+樹(shù)的 1/2）； B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿(mǎn)時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針； B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針； B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿(mǎn)時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿(mǎ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)鍵字范圍改變了）；如果兄弟也滿(mǎ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*樹(shù)分配新結(jié)點(diǎn)的概率比 B+樹(shù)要低，空間使用率更高； B*樹(shù) ? B樹(shù)：二叉樹(shù)，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)； ? B樹(shù)：多路搜索樹(shù)，每個(gè)結(jié)點(diǎn)存儲(chǔ) M/2到 M個(gè)關(guān)鍵字，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)； ? 所有關(guān)鍵字在整顆樹(shù)中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中； ? B+樹(shù)：在 B樹(shù)基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引； B+樹(shù)總是到葉子結(jié)點(diǎn)才命中； ? B*樹(shù)：在 B+樹(shù)基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從 1/2提高到 2/3； 相關(guān)研究工作 :B樹(shù)、 B樹(shù)、B+樹(shù)、 B*樹(shù) 相關(guān)研究工作 : R樹(shù)結(jié)構(gòu) ? R樹(shù)是一個(gè)高度平衡樹(shù)，它是 B樹(shù)在 k維上的自然擴(kuò)展，用空間對(duì)象的 MBR來(lái)近似表達(dá)空間對(duì)象，根據(jù)地物的 MBR建立 R樹(shù)，可以直接對(duì)空間中占據(jù)一定范圍的空間對(duì)象進(jìn)行索引。 R樹(shù)的每一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)著磁盤(pán)頁(yè) D和區(qū)域 I，如果結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則該結(jié)點(diǎn)的所有子結(jié)點(diǎn)的區(qū)域都在區(qū)域 I的范圍之內(nèi)，而且存儲(chǔ)在磁盤(pán)頁(yè) D中。如果結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么磁盤(pán)頁(yè) D中存儲(chǔ)的將是區(qū)域 I范圍內(nèi)的一系列子區(qū)域，子區(qū)域緊緊圍繞空間對(duì)象，一般為空間對(duì)象的外接矩形。 ? 一個(gè)空間數(shù)據(jù)庫(kù)由代表對(duì)象的的集合組成。 ? 每個(gè)對(duì)象元組都有一個(gè)唯一的標(biāo)識(shí)符，可通過(guò)這些標(biāo)識(shí)符來(lái)檢索對(duì)象元組。 ? R樹(shù)的葉節(jié)點(diǎn)按以下形式記錄索引記錄的入口 比較典型的有 R+樹(shù)、 R樹(shù)、壓縮 R樹(shù)等。 相關(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)行插入和刪除操作。但正因?yàn)閰^(qū)域之間有重疊，空間索引可能要對(duì)多條路徑進(jìn)行搜索后才能得到最后的結(jié)果。 R樹(shù)的空間分布圖 Bloom filter ? Bloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。 Bloom Filter的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（ false positive）。因此， Bloom Filter不適合那些“ 零錯(cuò)誤 ” 的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下， Bloom Filter通過(guò)極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。 ? 由一個(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ǔ)空間。 ? Bloom filter算法的一個(gè)缺點(diǎn)在于查詢(xún)一個(gè)元素是否
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1