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