R樹空間索引

R 樹利用空間實體外接矩形建立空間索引。R 樹空間索引建立每個實體的外接矩形(rectangles,R)，通過外接矩形的最大、最小坐標檢索空間實體。對這些虛擬矩形建立空間索引，設計虛擬的矩形目錄，將空間對象包含它含在矩形內，以虛擬矩形為空間索引，它包含指向所包圍的空間實體的指針。為提高檢索效率，R 樹空間索引還將空間位置相近的實體外接矩形重新組織為更大的虛擬矩形，形成多級空間索引。 R 樹空間索引就是按包含實體的矩形來確定的，樹的層次表達了解析度信息，每個實體與R 樹結點相聯繫，這點與四叉樹相同。矩形數據結構為RECT (rectangle-ID,type,min-X,min-Y，max- x，max-y )其中: rectangle-ID 為矩形標識符; type 為矩形類別(實體外接矩形還是虛擬矩形) ;min-X、min-Y 為該矩形左下角坐標; max-X，max-Y 為該矩形右上角坐標。

在構造R 樹時，要求虛擬矩形之間儘量不要相互重疊，而且一個空間實體通常僅被一個同級虛擬矩形所包圍。但由於空間對象的複雜性，虛擬矩形難免重疊。R+樹是對R 樹索引的一種改進，它允許虛擬矩形可以相互重疊，並分割下層虛擬矩形，允許一個空間實體被多個虛擬矩形包圍。在構造虛擬矩形時，儘量保持每個虛擬矩形包含相同個數的下層虛擬矩形或實體外接矩形，以保證任一實體具有相近的檢索時間。