空間數據索引

空間索引的提出是由兩方面決定的:其一是由於計算機的體系結構將存貯器分為內存、外存 兩種，訪問這兩種存儲器一次所花費的時間一般為30~40ns，8~10ms，可以看出兩者相差十 萬 倍以上，儘管現在有“內存數據庫”的説法，但絕大多數數據是存儲在外存磁盤上的，如果 對磁盤上數據的位置不加以記錄和組織，每查詢一個數據項就要掃描整個數據文件，這種訪 問磁盤的代價就會嚴重影響系統的效率，是GIS 所表現的地理數據多維性使得傳統的B?樹索引並不適用，因為B?樹所針對的字符、數字等 傳統數據類型是在一個良序集之中，即都是在一個維度上，集合中任給兩個元素，都可以在 這個維度上確定其關係只可能是大於、小於、等於三種，若對多個字段進行索引，必須指定 各個字段的優先級形成一個組合字段，而地理數據的多維性，在任何方向上並不存在優先級 問題，因此B?樹並不能對地理數據進行有效的索引，所以需要研究特殊的能適應多維特性 的空間索引方式。

1984年Guttman發表了《R樹:一種空間查詢的動態索引結構》，它是一種高度平衡的樹 ，由中間節點和頁節點組成，實際數據對象的最小外接矩形存儲在頁節點中，中間節點通過 聚集其低層節點的外接矩形形成，包含所有這些外接矩形。其後，人們在此基礎上針對不同 空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是目前流行的空間索引。