物聯(lián)網(wǎng)數(shù)據(jù)存儲(chǔ)及管理分析(ppt72頁(yè))-文庫(kù)吧在線文庫(kù)
【正文】 單元為空。 不預(yù)先計(jì)算任何的方體（不物化， No Materialization） ? 當(dāng)總的數(shù)據(jù)量很大時(shí)，那查詢的結(jié)果集也會(huì)很大， ? 在線計(jì)算將需要很長(zhǎng)的時(shí)間，從而導(dǎo)致無法忍受的響應(yīng)時(shí)間， ? 在海量數(shù)據(jù)情況下，該策略是不可取的 部分物化 ? 提供了存儲(chǔ)空間和響應(yīng)時(shí)間的有效折衷。 ? 將它定義為一個(gè)四元組 D， M， A， f，這四個(gè)組件分別表示數(shù)據(jù)立方體的特征 數(shù)據(jù)立方體 ? 在典型的 OLAP應(yīng)用中，存在一個(gè)中心關(guān)系或數(shù)據(jù)集合，稱作事實(shí)表。 ? 延遲刪除的策略是將更新信息立即插入，而舊的對(duì)象信息不會(huì)立即刪除， ? 而是使用某種策略將未刪除的索引信息緩存起來以便區(qū)分新舊數(shù)據(jù)，直到緩沖區(qū)滿或者其它情況下才進(jìn)行刪除操作 批量操作 ? R樹的批量插入策略是當(dāng)前研究的熱點(diǎn)之一。 ? 但是， R樹不能有效地支持點(diǎn)查詢。 Bloom filter ? 為了表達(dá) S={x1, x2,… ,xn}這樣一個(gè) n個(gè)元素的集合，Bloom Filter使用 k個(gè)相互獨(dú)立的哈希函數(shù)（ Hash Function），它們分別將集合中的每個(gè)元素映射到{1,… ,m}的范圍中。但正因?yàn)閰^(qū)域之間有重疊，空間索引可能要對(duì)多條路徑進(jìn)行搜索后才能得到最后的結(jié)果。 ? 索引結(jié)構(gòu)是完全動(dòng)態(tài)的；插入、刪除和查找操作能同時(shí)進(jìn)行而且不需要定期地對(duì)樹的結(jié)構(gòu)進(jìn)行重新組織 相關(guān)研究工作 :B樹、 B樹、B+樹、 B*樹 ? B樹 即二叉搜索樹： （ Left和 Right）； ； 于其關(guān)鍵字的子樹，右指針 指向大于其關(guān)鍵字的子樹； 如： 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樹 是一種多路搜索樹（并不是二叉的）： M個(gè)兒子；且 M2； [2, M]； [M/2, M]； M/21（取上整）和至多 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]的子樹， 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é)點(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樹：二叉樹，每個(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*樹 相關(guān)研究工作 : R樹結(jié)構(gòu) ? R樹是一個(gè)高度平衡樹，它是 B樹在 k維上的自然擴(kuò)展，用空間對(duì)象的 MBR來近似表達(dá)空間對(duì)象，根據(jù)地物的 MBR建立 R樹，可以直接對(duì)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1