Database Reference
In-Depth Information
6.4.2 Tree-Structured Indexing
Most applications require accessing data both sequentially and randomly.
The tree-structured indexing methods facilitate both of them. These index-
ing schemes are sometimes referred to as multilevel indexing schemes. A file
organization scheme, representative of a tree structured index, is the
indexed
sequential access method
(ISAM). The early commercial design and implemen-
tation of the indexed sequential access method was by IBM over 50 years ago.
The ISAM index method is a
static
index method. Many versions of tree-index
schemes that allow
dynamic
updating of the tree structure were introduced
later, including the well-known B-tree indexes and their many variations. In
order to illustrate the main concept of tree-structures indexes, we discuss next
the ISAM index using the example in Figure 6.2.
The index keys in the table shown in Figure 6.2 are first grouped into
first-level nodes, or blocks, of size
b
records per node. The idea is illustrated
in Figure 6.3, which represents the ISAM organization of the blocked indexes
shown in Figure 6.2. In Figure 6.3,
b
2. The lowest index keys (alternatively
the largest index key) of a node, each paired with its node address, are formed
into records that are organized as the next higher (or second) level index of
the first-level nodes. The process is recursively repeated until a single node
(i.e., the root node) of size
b
can contain all the index records that point to
the lower-level nodes.
Searching for a record begins at the root node and proceeds to the lowest-
level node, that is, the leaf node, where a pointer to the record can be found.
Within each node, a sequential or binary search is used to determine the
next lower level node to access. The search time for a random record is
=
Rec No
Y
X
Label
X-Vals
Rec No
1
y0
x6
A
x6
1
2
y2
x6
B
x6
2
3
y4
x3
C
x3
3
4
y5
x3
D
x3
4
5
y2
x1
E
x1
5
6
y4
x1
F
x1
6
7
y1
x7
G
x7
7
X-Index List
x0
8
y2
x5
H
x5
8
→
{
14
}
9
y1
x5
I
x5
9
x1
→
{
5, 6
B
0
}
10
y6
x4
J
x4
10
x2
→
{
11, 13
}
11
y7
x2
K
x2
11
x3
→
{
3, 4
B
1
}
12
y6
x7
L
x7
12
x4
→
{
10
}
13
y5
x2
M
x2
13
x5
→
{
8, 9, 15
B
2
}
14
y3
x0
N
x0
14
x6
→
{
1, 2
}
15
y4
x5
N
x5
15
x7
→
{
7, 12
}
B
3
Figure 6.2
An example of a single-attribute index.
