第五章索引技術(shù)(編輯修改稿)
2024-11-03 13:39 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 索引項(xiàng)，處于該項(xiàng)左邊的項(xiàng)及左邊的一切子樹(shù)中最大關(guān)鍵字 ≤ 本關(guān)鍵字 ≤ 右邊的項(xiàng)及右邊的一切子樹(shù)中最小關(guān)鍵字。 順序性保證了在搜索時(shí)，可通過(guò)比較而確定下一步的搜索方向。 B樹(shù)的價(jià)值在于動(dòng)態(tài)性能好。 多維索引技術(shù) 我們考慮兩種多維應(yīng)用問(wèn)題 : 地理信息系統(tǒng) 一個(gè)地理信息系統(tǒng)存儲(chǔ)二維空間中的對(duì)象。通常這些數(shù)據(jù)庫(kù)中存儲(chǔ)的對(duì)象包括房屋，道路，橋梁，管道和其它實(shí)物 . 立體數(shù)據(jù)系統(tǒng) 它將數(shù)據(jù)看作是處于一個(gè)高維空間中。許多公司收集多維數(shù)據(jù)以支持決策支持系統(tǒng)類型的應(yīng)用，他們分析各種銷售信息以更好的理解公司的運(yùn)作。比如，一個(gè)連鎖店可以記錄每一筆買賣，其中包括如下信息： ?日期和時(shí)間 ?商店名 ?所購(gòu)物品名 ?物品的顏色 ?物品的尺寸 也許還有其它一些信息。 查詢關(guān)于在二維空間中的一組點(diǎn)的最近鄰居。我們可以用一對(duì)實(shí)數(shù)來(lái)描述點(diǎn) Points(x, y)，也就是說(shuō)，用兩個(gè)實(shí)數(shù)來(lái)描述點(diǎn)的兩個(gè)坐標(biāo)。假設(shè)我們要求距離（ ， ）最近的那個(gè)點(diǎn)。 SQL中的多維查詢 SELECT * FROM POINTS P WHERE NOT EXISTS( SELECT * FROM POINTS WHERE()*（ ） + （ ） *（ ） （ ） *（ ） + （ ） *(） X方向索引 Y方向索引 . (10,20) 用 B索引計(jì)算最近鄰居查詢 考慮一下對(duì)第 4章所討論的索引進(jìn)行怎樣的擴(kuò)充才能幫助實(shí)現(xiàn)這些查詢。對(duì)每個(gè)維用 B+樹(shù)，這樣一來(lái)就可以非常容易的得到每一維的值的范圍。 例如，如果我們確信有點(diǎn)在離點(diǎn)（ ， ）不到 D遠(yuǎn)的范圍內(nèi)，我們可以用關(guān)于 X坐標(biāo)的 B樹(shù)來(lái)得到指向那些 X坐標(biāo)在 10D和 10+D之間的點(diǎn)的記錄的指針，然后我們又可以用關(guān)于 Y的 B樹(shù)來(lái)得到指向那些 Y坐標(biāo)在 20D和 20+D之間的點(diǎn)的記錄的指針，最后取這些指針的交集，如果這些指針都在內(nèi)存中的話，整個(gè)讀寫(xiě)磁盤的次數(shù)約為要檢查的 B樹(shù)的葉子結(jié)點(diǎn)數(shù)，再加上一些搜索 B樹(shù)過(guò)程的磁盤讀寫(xiě)次數(shù)。 如果我們有一個(gè)或多個(gè)處在交集中的點(diǎn)的話，我們可以通過(guò)指針記錄下它們的 X， Y坐標(biāo)，然后我們就有了交集中所有點(diǎn)的坐標(biāo)。我們可以確定這些點(diǎn)中哪一個(gè)最靠近點(diǎn)（ ， ），并只取出它的記錄。 支持多維數(shù)據(jù)的索引方法 kd樹(shù) 每一層都根據(jù)當(dāng)前層的特定檢索關(guān)鍵碼做出分支決策，這個(gè)檢索關(guān)鍵碼可稱為識(shí)別器。 下面是 kd樹(shù)檢索的一個(gè)實(shí)現(xiàn)：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1