Slide 13.14: Improving the secondary index structures Slide 13.16: Implementation of an inverted list Home

A Better Solution: An Inverted List

---

Each secondary key points to a different list of primary key references. Each of these lists could grow to be as long as it needs to be and no space would be lost to internal fragmentation.

Such secondary index file is called an inverted list. It is a sequence of (key, pointer) pairs where each pointer points to a record in a data file which contains the key value in some particular field. The index is sorted on the key values to allow rapid searching for a particular key value, using e.g., a binary search. The index is “inverted” in the sense that the key value is used to find the record rather than the other way round.

^†In our case, another key layer, the primary key, is added between the secondary key and a data file.

Linked lists are used to set up an unbounded number of different lists, each of varying length, without creating a large number of small files. In the linked lists, the secondary index will consist of records with two fields:

• a secondary key field, and
• a field (link field) containing the relative record number of the first corresponding primary key reference (Label ID) in the list.