Database Reference
In-Depth Information
N
data items where an average index record size is
b
. The storage utilization
is defined as
.
Another metric, sometimes considered, is the time to update the index.
This is sometimes considered as two independent metrics: the
insertion
time
and the
deletion
time. In scientific data management, deletions are hardly of
concern.
There is a large body of literature on index structures. It is one of the highly
researched subjects in computer science. Extensive coverage of the subject is
given by References 25, 39, 47, 79, 99. Together, these topics cover most of
the indexing structures used in datasets and databases of various application
domains. Index schemes may be classified into various classes. Figure 6.1 shows
a taxonomy used to guide our review of known indexing methods.
Each class is partitioned into three subclasses based on whether accessing
the data is by
direct access
method,
tree-structured
index, or some combina-
tion of tree-structured index and a direct access method, which we term as a
hybrid index
. Each of these subclasses can be subsequently grouped according
to whether the search key is a
single attribute
or a combination of
multiple
attributes
of the data item. Such combined
multiattribute
index schemes are
also referred to as
multidimensional
index schemes.
Since the classification of hybrid indexes is fuzzy, we will discuss them un-
der direct access methods in this chapter. Further, to restrict the classification
space to a relatively small size, we will not distinguish between single-attribute
μ(
G
)
=
bN
/
S
(
G
)
External Memory Index
Direct Access
Tree Based
Single−Attr/
Multi−Attr
Single−Attr/
Multi−Attr
Scan
Hash
Hybrid
Single−Attr
Multi−Attr
Seq−Scan
VA−File
Grid−File
Ext.−Hash
Linear−Hash
Inverted
Transposed
Bitmaps
Signature
QTM/SQC
HTM
B+Tree
ISAM/VSAM
Tries
PATRICIA
Sux−Tree
K−D−B−Tree
R−Tree
SS−Tree
LSD−Tree
K−D−Tree
Figure 6.1
A taxonomy of indexed access methods.
