Database Reference
In-Depth Information
0
2
4
6
000
010
100
110
0
000
2
010
4
100
6
110
(a) Row-major order
(b) Morton or Z-order
0
2
4
6
000
011
110
101
000
0
2
011
4
110
101
6
(c) Hilbert order
(d) Gray-code order
Figure 6.11
Examples of two-dimensional space curves.
indexes, and simple sequential scans. In the preceding section on
Grid-File
,
we saw that in the two-dimensional grid-directory mapping, the key value of
the form
y
,
x
is first translated into a
i
y
,
i
x
coordinate index that is used as
an index of an array entry. The use of the
coordinate index is actually
a mapping onto a one-dimensional array, which in a two-dimensional array
happens to be either a row-major or a column-major addressing method. In
general, given a
k
-dimensional index
K
i
y
,
i
x
, one can generate a
one-dimensional mapping denoted as
I
K
,ofthe
k
-dimensional key, and then
use this in any of the tree-based index schemes described in the preceding
sections. There are different methods by which one-dimensional mapping can
be formed. These are formally referred to as
space-filling curves
.
78
Figure 6.11
gives some typical space-filling curves generated from a two-dimensional index
and mapped onto one-dimensional codes.
The most popular of the space-filling curves that have been used in numer-
ous applications is the Morton or Z-order mapping. It is generated simply by
k-cyclic interlacing of the bits of the binary representation of the k-dimensional
=
i
0
,
i
1
...
i
k
−
1
