International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 Inte 
EA =Jol x Another example of a hash tree is the buddy tree (Seeger & 
Fle Edt Vew Performance ? : ; Ge S uui por 
SUE Kriegel, 1990). The buddy tree is also a hierarchical tree with que 
+] directory nodes containing rectangular block regions. In . 
zd / contrast to the grid file and the BANG file, however, the 
regions do not need to cover the complete data space. Figure 5 » 
illustrates the partitioning of the buddy tree using the sinus data 
again. . 
2.4 R-Trees Ind: 
2 c ; ; Int 
The R-tree (Guttman, 1984) is a spatial access method SG 
n 17 . . SLOT 
organizing multidimensional points as well as rectangles. The M 
ib : : essc 
R-tree has similar properties as the B-tree but it does not require ACC 
a linear ordering. The block regions are minimum-bounding hot 
: ; : : Dec: 
© rectangles of all regions or data in the corresponding subtree. Er 
Scale: 1... x T N . MR vlr ; 3 MS s (Vl 
regie prime ixi These block regions may overlap and do not need to cover the co 
Fle Edt View Performance 7 =. whole data space. 
‘ redi 
= . : : Pp ia prol 
= There exist several variants of R-trees. They differ in the ont 
insertion strategy (i.e., which subtree is chosen for storing a 
new object) and the criteria used for splitting a node if an Oth 
overflow occurs. Figure 6 illustrates an R-tree: it shows the spat 
. ~ ~ ... . x € 
block region of the root node and (a part) of the partitioning of sion 
a node pointing to a data node, which illustrates the overlap Sois 
between the block regions. ie 
g spat 
wou 
$5 PolntTree Viewer - Ted 
Fle Edt Vw Performance ? He app! 
(Bri 
RC 
| | E Are RTI 
: \ {i 
Scale: 1... NO | 
\ / 3.1 
Figure 4. Example for the partitioning of a BANG file. \ / = 
$& PointTree Viewer | X / For 
Fle Edt View Performance 7 S \ / sect 
/ . 
5] Y } preg 
A j © 
zl 
| 
e. : 
| 
i 
«| | 
ij e. 
| 
Scale: 1... 
[DAE 
le Edt View Performance 7 
{ 
pas 
1 
Scde: 6,861 … 
  
  
  
  
  
  
Figure 6. Example for the partitioning of an R-tree. 
2.5 First Conclusions 
The presented spatial access methods are dynamic index 
structures supporting the insertion, the modification and the 
deletion of points. They support the persistent storage of data 
on secondary storage like hard disks. All presented spatial 
access methods are suitable of two-, three- or more dimensional 
  
Figure 5. Example for the partitioning of a buddy tree. 
100