物聯(lián)網(wǎng)數(shù)據(jù)存儲及管理分析(ppt72頁)-在線瀏覽
2025-02-22 19:18本頁面
【正文】 全適合各種應用場合，比如元數(shù)據(jù)查找，特別是支持各種復雜的元數(shù)據(jù)查詢，熱點數(shù)據(jù)查詢等；而且在大規(guī)模存儲系統(tǒng)中會限制其性能和擴展性。保證元數(shù)據(jù)查詢不需要占用太多的存儲空間，且不會降低系統(tǒng)的性能?，F(xiàn)有的文件系統(tǒng)接口不能很好的支持各種復雜文件查詢。隨著存儲系統(tǒng)的規(guī)模越來越大，必須保證系統(tǒng)具有良好的伸縮性和可用性 多維元數(shù)據(jù)組織結(jié)構 ? 傳統(tǒng)的索引方法已不能滿足多維數(shù)據(jù)的索引和查詢要求， ? 比如哈希表是數(shù)據(jù)的精確匹配而不能進行范圍查詢， ? 而 B樹索引一維數(shù)據(jù)而不能搜索多維空間。 ? 基于規(guī)則分割的索引結(jié)構按照特定算法對數(shù)據(jù)空間進行劃分，包括 KD樹、網(wǎng)格等， ? 這種方法僅適用于數(shù)據(jù)分布均勻的情況，在數(shù)據(jù)分布不均勻時會引起索引結(jié)構的不平衡。 ? 如果系統(tǒng)按照多維屬性信息建立了空間索引結(jié)構，則可以同時在文件大小、創(chuàng)建時間和修改時間這個三個屬性維度上做約束，大大減少了查詢的數(shù)據(jù)量和查詢的時間代價。 ? 如果索引是磁盤駐留的，則每個節(jié)點對應一個磁盤頁，以節(jié)點為單位讀取和寫入。 ? 索引結(jié)構是完全動態(tài)的；插入、刪除和查找操作能同時進行而且不需要定期地對樹的結(jié)構進行重新組織 相關研究工作 :B樹、 B樹、B+樹、 B*樹 ? B樹 即二叉搜索樹： （ Left和 Right）； ； 于其關鍵字的子樹，右指針 指向大于其關鍵字的子樹； 如： B樹 ? B樹的搜索，從根結(jié)點開始，如果查詢的關鍵字與結(jié)點的關鍵字相等，那么就命中；否則，如果查詢關鍵字比結(jié)點關鍵字小，就進入左兒子；如果比結(jié)點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字； ? 如果 B樹的所有非葉子結(jié)點的左右子樹的結(jié)點數(shù)目均保持差不多（平衡），那么 B樹的搜索性能逼近二分查找；但它比連續(xù)內(nèi)存空間的二分查找的優(yōu)點是，改變 B樹結(jié)構（插入與刪除結(jié)點）不需要移動大段的內(nèi)存數(shù)據(jù)，甚至通常是常數(shù)開銷； B樹 是一種多路搜索樹（并不是二叉的）： M個兒子；且 M2； [2, M]； [M/2, M]； M/21（取上整）和至多 M1個關鍵字；（至少 2個關鍵字） =指向兒子的指針個數(shù) 1； ： K[1], K[2], … , K[M1]；且 K[i] K[i+1]； ： P[1], P[2], … , P[M]；其中 P[1]指向關鍵字小于 K[1]的子樹， P[M]指向關鍵字大于 K[M1]的子樹，其它 P[i]指向關鍵字屬于 (K[i1], K[i])的子樹； ； 如：（ M=3） B樹 B樹 B+樹是 B樹的變體，也是一種多路搜索樹： B樹同，除了： ； P[i]，指向關鍵字值屬于 [K[i], K[i+1])的子樹（ B樹是開區(qū)間）； ； ； 如：（ M=3） B+樹 ? 是 B+樹的變體，在 B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針； ? B*樹定義了非葉子結(jié)點關鍵字個數(shù)至少為 (2/3)*M，即塊的最低使用率為 2/3（代替 B+樹的 1/2）； B+樹的分裂：當一個結(jié)點滿時，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針； B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點，所以它不需要指向兄弟的指針； B*樹的分裂：當一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿，那么將一部分數(shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關鍵字，最后修改父結(jié)點中兄弟結(jié)點的關鍵字（因為兄弟結(jié)點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復制 1/3的數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點的指針； 所以， B*樹分配新結(jié)點的概率比 B+樹要低，空間使用率更高； B*樹 ? B樹：二叉樹，每個結(jié)點只存儲一個關鍵字，等于則命中，小于走左結(jié)點，大于走右結(jié)點； ? B樹：多路搜索樹，每個結(jié)點存儲 M/2到 M個關鍵字，非葉子結(jié)點存儲指向關鍵字范圍的子結(jié)點； ? 所有關鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點可以命中； ? B+樹：在 B樹基礎上，為葉子結(jié)點增加鏈表指針，所有關鍵字都在葉子結(jié)點中出現(xiàn)，非葉子結(jié)點作為葉子結(jié)點的索引； B+樹總是到葉子結(jié)點才命中； ? B*樹：在 B+樹基礎上，為非葉子結(jié)點也增加鏈表指針，將結(jié)點的最低利用率從 1/2提高到 2/3； 相關研究工作 :B樹、 B樹、B+樹、 B*樹 相關研究工作 : R樹結(jié)構 ? R樹是一個高度平衡樹，它是 B樹在 k維上的自然擴展，用空間對象的 MBR來近似表達空間對象，根據(jù)地物的 MBR建立 R樹，可以直接對空間中占據(jù)一定范圍的空間對象進行索引。如果結(jié)點是葉結(jié)點，那么磁盤頁 D中存儲的將是區(qū)域 I范圍內(nèi)的一系列子區(qū)域，子區(qū)域緊緊圍繞空間對象，一般為空間對象的外接矩形。 ? 每個對象元組都有一個唯一的標識
環(huán)評公示相關推薦
鄂ICP備17016276號-1