91 
h of left of each 
have M.LON< 
I be the L nodes 
insertion follows 
‘vhich the points 
INFO; 
LAT; 
LON; 
L; 
R; 
ord. 
e points of our 
tance, the one 
'able 1. In this 
field the GPS 
an attribute of 
is empty: this 
Root 
Leven 
Level 2 
ture 
that this node 
de if we must 
n between the 
Id (2) must be 
the tree, the 
Ids: 2.LON is 
i is connected 
t 3, we begin 
}.LON<1 .LON, 
r ith the L field, 
it 4 we have: 
le comparison 
In this case, 
done between 
ecord child is 
the region is 
nt 1 divides it 
ide X = 12°20' 
like discriminating; point 2 divides the right surface (B) into 
two more regions: northern (C) and southern (D) with 
respect to cp = 43°60'; point 3 divides the left region into 
two subregions northern and southern (F) of (p = 42°50'; 
finally the point 4 divides the D surface into two parts 
corresponding to East (G) and West (H) of X = 16°10'. 
When we perform a query on the database, the structure 
allows to access only the points of the subregion of 
interest, avoiding of take into account the whole interval 
((p,Jt), as it happened in the first example (Fig. 2). 
This type of structure can be used also for data with more 
than two dimensions; in this case the tree is named k-D- 
tree, where k is the number of dimensions of the data. 
The structure of the record changes and instead of the 
LAT and LON fields there is a matrix with k columns (Fig. 
6). 
Fig. 5- Example of a 2-D-tree space partition 
typedef struct 
{ 
information_type INFO; 
real VAL[k]; 
node L; 
node R; 
} node; 
Fig. 6 - Structure of a k-D-tree record 
2.2 Point quadtree 
This type of structure may be used for represent the 
points only in two spatial dimensions. Each node divides 
the region in four quadrants: NW (north - west), NE (north 
- east), SW (south - west), SE (south - east). The 
structure of a point quadtree record is given in Fig. 7, 
where the INFO fields, LAT and LON have the same 
meaning we have already seen for the 2-D-tree. The fields 
NW, SW, NE and SE point to four children records. 
[typedef struct] 
{ 
information_type 
INFO; 
real 
LAT; 
real 
LON; 
node 
NW 
node 
NE 
node 
SW 
node 
SE 
} node; 
Fig. 7 - Structure of a point-quadtree record. 
Given a node N the branch in which we insert a new M 
point depends on its coordinates; respectively it is 
• NE , if M.LAT> N.LAT and M.LON> N.LON ; 
• NW, if M.LAT> N.LAT and M.LON< N.LON; 
• SE, if M.LAT< N.LAT and M.LON> N.LON; 
• SW, if M.LAT< N.LAT and M.LON< N.LON. 
Regarding to the insertion, we have that (considering 
Table 1) the record corresponding to point 1 is the root of 
the tree (Fig. 8). For the insertion of point 2, we have that 
2. LAT<1.LAT and 2.LON>1.LON: the child is connected 
with the field SE.. For the insertion of point 3, 
3. LAT<1.LAT and 3.LON<1.LON: the child is connected 
with the field SW. Finally for the insertion of point 4, as 
first step we observe that 4.LAT<1.LAT and 
4. LON>1.LON and the corresponding node is SE. 
Because this node has already a child (point 2) and we 
have that 4.LAT<2.LAT and 4.LON>2.LON, the record 
corresponding to point 4 is connected with the SE field of 
point 2. 
Fig. 8 - Example of point- quadtree structure 
Each insertion divides the region into four subregions (Fig. 
9): point 1 divides it into four zones (A, B, C, D) using the 
longitude 12°20' and the latitude 44°50' like discriminating; 
point 2 divides the D region into four more regions (E, F, 
G, H); point 3 divides the C region into (I, L, M, N); point 4 
divides the H region into the four (O, P, Q, R). 
With respect to the 2-D-tree each node divides the current 
region in four parts instead of two; this allows to have 
trees with less levels and, as a consequence, a faster 
access to the data. But, at the same time we have a more 
complex structure with four pointers instead of the two we 
have in the previous case.