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
