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