Database Reference
In-Depth Information
The R-Tree representation of the rectangular regions of Figure 6.10a is
shown in Figure 6.10b. Since the introduction of the R-Tree, several variants
have been introduced. The R-Tree portal
94
gives implementation codes and
papers of the different variants. It has had numerous applications in spatial
databases, geographic information systems (GIS), very large scale integration
(VLSI) design and applications that depend on nearest-neighbor searching
in low multidimensional space. The R-Tree and its variants use rectilinear
bounding boxes. The use of other geometric shapes as bounding boxes, such
as circles/spheres, has led to the development of similar index schemes such
as the SR-Tree.
46
6.5.2 Multidimensional Direct Access Methods
The conceptualized optimal multidimensional access method is one that
can be correctly defined as a
dynamic order-preserving multidimensional ex-
tendible hashing method
. The idea is that the location where a record is stored
is derived by a simple computation; the utilized data space of the dataset will
grow and shrink with insertions and deletions of data items, and accessing
records in consecutive key order should be just as ecient as a simple sequen-
tial scan of the data items given the first key value. Such a storage scheme is
impossible to realize. However, numerous close approximations to it have been
realized. Notable among these is the
Grid-File
.
62
Other related multidimen-
sional storage schemes are the optimal partial-match retrieval method,
2
the
multidimensional extendible hashing,
69
and the BANG-file.
32
Other similar
methods are also presented in References 33 and 79.
Consider the mapping of the dataset of Figure 6.7, as points in a two di-
mensional space shown in Figure 6.8. The mapping is based on the Y- and
X-values. A two-dimensional Grid-File partitions the space rectilinearly into
a first-level structure of a grid directory. The Y-values define a Y-axis that is
split into
I
Y
segments. Similarly the X-values define an X-axis that is split into
I
X
segments. The grid directory is comprised of an array of
I
Y
I
X
elements.
An element of the grid directory array stores the bucket address of the data
buckets where the data item is actually stored. Given a key value
×
, the
y
-value is mapped onto a y-coordinate value
i
y
, and the
x
-value is mapped
onto an x-coordinate value
i
x
. A lookup of the grid-directory array entry
y
,
x
i
x
gives the bucket address where the record can be found or inserted. Since grid-
directory and data buckets are disk resident, accessing an element using the
grid directory requires at most two disk accesses. The basic idea, illustrated
with a two-dimensional key space, can easily be generalized to arbitrary num-
ber of dimensions. For a dataset of n-buckets, a partial-match retrieval that
specifies
s
out of
k
-dimensional values can be performed in
O
i
y
,
n
1
−
s
/
k
(
+
r
)
time,
where
r
is the number of records in the response set.
6.5.3 Hybrid Indexing Methods
The term
hybrid index
refers to index structures that are composed of two or
more access structures such as hashing (or direct access method), tree-based
