Java Reference
In-Depth Information
JONES
AA10
AB12
AB39
FF37
SMITH
AX33
AX35
ZX45
ZUKOWSKI
ZQ99
Figure10.3 A two-dimensional linear index. Each row lists the primary keys
associated with a particular secondary key value. In this example, the secondary
key is a name. The primary key is a unique four-character code.
Secondary
Key
Primary
Key
Jones
AA10
Smith
AB12
Zukowski
AB39
FF37
AX33
AX35
ZX45
ZQ99
Figure10.4 Illustration of an inverted list. Each secondary key value is stored
in the secondary key list. Each secondary key value on the list has a pointer to a
list of the primary keys whose associated records have that secondary key value.
Consider a large database of employee records. If the primary key is the em-
ployee's ID number and the secondary key is the employee's name, then each
record in the name index associates a name with one or more ID numbers. The
ID number index in turn associates an ID number with a unique pointer to the full
record on disk. The secondary key index in such an organization is also known
as an inverted list or inverted file. It is inverted in that searches work backwards
from the secondary key to the primary key to the actual data record. It is called a
list because each secondary key value has (conceptually) a list of primary keys as-
sociated with it. Figure 10.4 illustrates this arrangement. Here, we have last names
as the secondary key. The primary key is a four-character unique identifier.
Figure 10.5 shows a better approach to storing inverted lists. An array of sec-
ondary key values is shown as before. Associated with each secondary key is a
pointer to an array of primary keys. The primary key array uses a linked-list im-
plementation. This approach combines the storage for all of the secondary key lists
into a single array, probably saving space. Each record in this array consists of a
Search WWH ::




Custom Search