Java Reference
In-Depth Information
Secondary
Primary
Key
Key
Jones
Index
0
Next
0
AA10
4
Smith
1
1
AX33
6
Zukowski
3
2
ZX45
3
ZQ99
4
AB12
5
5
AB39
7
6
AX35
2
7
FF37
Figure10.5
An inverted list implemented as an array of secondary keys and
combined lists of primary keys. Each record in the secondary key array contains
a pointer to a record in the primary key array. The
next
field of the primary key
array indicates the next record with that secondary key value.
primary key value and a pointer to the next element on the list. It is easy to insert
and delete secondary keys from this array, making this a good implementation for
disk-based inverted files.
10.2
ISAM
How do we handle large databases that require frequent update? The main problem
with the linear index is that it is a single, large array that does not adjust well to
updates because a single update can require changing the position of every key in
the index. Inverted lists reduce this problem, but they are only suitable for sec-
ondary key indices with many fewer secondary key values than records. The linear
index would perform well as a primary key index if it could somehow be broken
into pieces such that individual updates affect only a part of the index. This con-
cept will be pursued throughout the rest of this chapter, eventually culminating in
the B
+
-tree, the most widely used indexing method today. But first, we begin by
studying ISAM, an early attempt to solve the problem of large databases requiring
frequent update. Its weaknesses help to illustrate why the B
+
-tree works so well.
Before the invention of effective tree indexing schemes, a variety of disk-based
indexing methods were in use. All were rather cumbersome, largely because no
adequate method for handling updates was known. Typically, updates would cause
the index to degrade in performance. ISAM is one example of such an index and
was widely used by IBM prior to adoption of the B-tree.
ISAM is based on a modified form of the linear index, as illustrated by Fig-
ure 10.6. Records are stored in sorted order by primary key. The disk file is divided
