第五章索引技術(shù)-資料下載頁
2025-09-19 13:39本頁面
【導(dǎo)讀】被搜索對(duì)象的組織結(jié)構(gòu)。去代替搜索較大的主數(shù)據(jù)集合。訪問記錄的過程稱為散列。大多數(shù)散列方法根。碼值的順序來放置。這兩種方法的不同之處在與將沖。內(nèi)另一個(gè)槽內(nèi)（閉散列）。索引文件本身不排序。那么，隔N項(xiàng)抽出。一項(xiàng)而建立起來的。其定位誤差小于N。的順序進(jìn)行排序。指針指向磁盤中完整?？紤]一個(gè)有關(guān)職工記錄的大型數(shù)據(jù)庫。個(gè)或多個(gè)標(biāo)識(shí)號(hào)關(guān)聯(lián)起來。這樣組織起來的次關(guān)。鍵碼索引稱為倒排表或稱為倒排文件。2）若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則至少有兩棵子樹；3）除根之外的所有非葉子節(jié)點(diǎn)至少有[m/2]棵子樹；5）樹中所有葉節(jié)點(diǎn)都出現(xiàn)在同一層上。平衡性保證了1≤搜索步數(shù)≤B樹高度。從而避免了搜索效率因記錄而異引起的“貧富不均”。節(jié)點(diǎn)上裝載因子永遠(yuǎn)過半。它將數(shù)據(jù)看作是處于一個(gè)高維空間中。容易的得到每一維的值的范圍。每一層都根據(jù)當(dāng)前層的特定檢索關(guān)鍵碼做出分支決策，這個(gè)檢索關(guān)鍵碼可稱為識(shí)別器。
【正文】 IdxItem IA[MaxItem]。 /*索引項(xiàng)數(shù)組 */ }。 實(shí)有項(xiàng)數(shù) 坐標(biāo) 2 A 1 , ( x 1,y 1 ,x2 , y2) A2, ( ... . ) 子區(qū)域 1 節(jié)點(diǎn)指針 子區(qū)域 2 節(jié)點(diǎn)指針 一種典型的 R樹查詢就是 “ 我在哪？ ” 這個(gè)查詢可找到一特定的點(diǎn) P和該點(diǎn)所在的區(qū)域（或數(shù)據(jù)區(qū)域）之間的關(guān)系。 我們可以從查找根結(jié)點(diǎn)的每個(gè)孩子開始，找到包含 P的相應(yīng)區(qū)域（注意：可能這樣的區(qū)域有一個(gè)或很多個(gè)，也可能一個(gè)也沒有）。假如我們找不到這樣的區(qū)域，那么查找過程就結(jié)束，點(diǎn) P不在任何區(qū)域內(nèi)，如果找到至少一個(gè)包含 P的區(qū)域，那么我們必須查找每一個(gè)這樣的結(jié)點(diǎn)的孩子結(jié)點(diǎn)。當(dāng)查詢到達(dá)一個(gè)或多個(gè)葉子時(shí)，我們便可找到一些實(shí)際的數(shù)據(jù)區(qū)域，它們是一些由指針指向的完整的記錄。 R樹查詢 如果要插入一個(gè)新區(qū)域 P（包含實(shí)體 P）到R樹中，可以從根結(jié)點(diǎn)開始尋找適合條件的子區(qū)域。假如有多個(gè)滿足這一條件的區(qū)域，那么選擇其中的一個(gè)，到達(dá)相應(yīng)的子結(jié)點(diǎn)，然后再從這個(gè)子結(jié)點(diǎn)開始重復(fù)這樣的過程。假如找不到這樣的子區(qū)域可包含區(qū)域 P，那么我們就必須擴(kuò)大其中的某個(gè)子區(qū)域 . 一般來說，我們只想對(duì)某個(gè)區(qū)域的擴(kuò)大程度變得很小，因此可以找這樣的一個(gè)子區(qū)域：對(duì)它進(jìn)行最少的擴(kuò)展便可包含區(qū)域 P，然后改變此區(qū)域的大小直到可以包含 P，然后把 P插入其子結(jié)點(diǎn)。 R樹上的操作 (1) 假如此結(jié)點(diǎn)中的區(qū)域數(shù)超過規(guī)定，就必須分裂這個(gè)葉子結(jié)點(diǎn)。怎樣分裂又是一個(gè)大問題。 一般來說，我們要求分裂成的這兩個(gè)子區(qū)域越小越好 ,但又要求它們能覆蓋原結(jié)點(diǎn)所表示的數(shù)據(jù)區(qū)域。分裂之后必須保證在它們的父結(jié)點(diǎn)中有相應(yīng)的區(qū)域包含它們和相應(yīng)的指針指向它們。如果在父結(jié)點(diǎn)中有空位置可以插入這樣的區(qū)域，那么操作便結(jié)束。這和 B樹從葉子到根進(jìn)行分裂的情況相似。 R樹上的操作 (2) DFCPEGHBQA 增加一個(gè)天線點(diǎn)。這個(gè)天線點(diǎn)落在 A區(qū)域內(nèi)。因?yàn)?，所有?jié)點(diǎn)最多含 4個(gè)子節(jié)點(diǎn)。所以， A節(jié)點(diǎn)必須分裂在二個(gè)子結(jié)點(diǎn)中 。 同樣，當(dāng)刪除空間對(duì)象時(shí)，會(huì)引起 R樹的合并 。 A B Q D F C D G H P E分裂后的 R樹 作業(yè) ? 實(shí)現(xiàn) R樹程序 . (所用語言 ,平臺(tái)不限 .)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1