90 
irregular space partitions of great complexity, substantially 
depending on the inserted elements. 
On the opposite, a data structure based on a regular radix 
partition of the space (metric data structure) is 
independent of the inserted element and the actual data 
stored play a role only in the definition of the granularity of 
the regular partition. 
In any case the partition of the embedding space into 
(regular or not) cells may be defined (as extreme cases) 
• completely depending on the data (data driven 
partition); 
• without paying attention to the location of the 
geometric object in the structure (space driven 
partition). 
Fig. 2 - Region interested in a query 
2. DATA DRIVEN PARTITION BY TREES 
The first possibility of RDBMS indexing is by means of 
tree representation. The tree root corresponds to the 
whole space; passing through a node the considered 
region decreases. In this way in a query it is not 
necessary to consider the tuples corresponding to 
features not belonging to the region of interest. 
2.1 2-D Tree 
Each record of the database organized with this storage 
system has, a part from the data fields, two special fields 
also: one points to the left branch, the other to the right 
one. The structure of a record of 2-D-tree type is 
described in Fig. 3 (in C language). 
The INFO field contains generic information on the point, 
for instance the ellipsoidal height; LAT and LON are real 
numbers corresponding to the coordinates of the point 
(latitude and longitude); L and R point each to a child. 
If N is a node of our tree of data and N is even, in the left 
branch of each record there are the M nodes (records 
children of N) that have M.LAT< N.LAT, while in the right 
branch we find the L nodes that have L.LAT> N.LAT 
Vice-versa, if the N node is odd, in the branch of left of each 
record there are the records children M that have M.LON< 
N.LON, while in the branch of right there will be the L nodes 
that have L.LON> N.LON. Therefore the data insertion follows 
these rules based on the sequence order with which the points 
are inserted. 
typedef struct 
{ 
information_type 
INFO; 
real 
LAT; 
real 
LON; 
node 
L; 
node 
R; 
} node; 
Fig. 3 - Structure of a 2-D-tree record. 
We suppose now that we want to insert the points of our 
database. The order of insertion is, for instance, the one 
with which the points have been listed in Table 1. In this 
specific case we associate to the INFO field the GPS 
ellipsoidal height of the point (this value is an attribute of 
the point). 
Before the insertion of point 1, the chart is empty: this 
record is the root of the tree of data (Fig. 4). 
Fig. 4 - Example of 2-D-tree structure 
For the insertion of point 2, we must remind that this node 
is a child of node 1. So, in order to decide if we must 
connect it with the L or R field, a comparison between the 
coordinates of the record father (1) and child (2) must be 
performed. Being the level 1 (odd) of the tree, the 
comparison is done between the LON fields: 2.LON is 
larger than 1.LON, therefore the record child is connected 
with the R field. For the insertion of point 3, we begin 
analyzing the record at the zero level: 3.LON<1.LON, 
therefore this record has to be connected with the L field. 
In the same way, for the insertion of point 4 we have: 
4.LON>1.LON. Now we have to perform the comparison 
with the record child of the right branch. In this case, 
being the level 2, the comparison has to be done between 
the LAT fields: 4.LAT< 2.LAT, and the record child is 
therefore connected with the R field. 
Each time a node is inserted in the tree, the region is 
subdivided into two parts (see Fig. 5) : point 1 divides it 
into two surfaces (A and B) using the longitude X = 12°20‘ 
like discr 
two mor 
respect t 
two subr 
finally th 
correspo 
When m 
allows t< 
interest, 
(cp,A.)> as 
This type 
than two 
tree, wh< 
The stru 
LAT and 
6). 
Fi< 
2.2 
This typ 
points or 
the regio 
- east), 
structure 
where tf 
meaning 
NW, SW