Slide 13.15: A better solution: an inverted list Slide 14.1: B-tree evloution Home

Implementation of an Inverted List

---

A record in the secondary key index of composers points to a relative number (RRN) in the Label ID List file, which is a fixed-length file. The following shows an example of record addition:

To add a Prokofiev record: ANG 36193, the Label ID of this record is the last one because the Label ID List file is an entry sequenced file. Further, Label ID lists are kept in order by ASCII characters.

The figure on the right shows an example of associating the secondary index file with a new file containing linked lists of references. Advantages

• Rearrangement of the secondary index file is needed only when a new composer's name is added or an existing composer's name is changed.
• Deleting or adding records for a composer already in the index, involves changing only the Label ID List file.
• The Label ID List file never needs to be sorted.
• Space from deleted records of the Label ID List file can be reused.

Disadvantages
Locality (in the secondary index) has been lost. Example: The list of Label IDs for Prokofiev consist of the very first and the very last records in the file. More seeking may be necessary.