Inverted List Organization

Like the indexed-sequential storage method, the inverted list organization maintains an index. The two methods differ, however, in the index level and record storage. The indexed-sequential method has a multiple index for a given key, whereas the inverted list method has a single index for each key type. In an inverted list, records are not necessarily stored in a particular sequence. They are placed in the data storage area, but indexes are updated for the record keys and location.

The flight number, flight description, and flight departure time are all defined as keys, and a separate index is maintained for each. Note that in the data location area, flight information is in no particular sequence. Assume that a passenger needs information about the Houston flight. The agent requests the record with the flight description "Houston flight." The data base management system (DBMS) then reads the single-level index sequentially until it finds the key value for the Houston flight. This value has two records associated with it: R3 and R6. The DBMS essentially tells the agent that flight #70 is departing at 10:10 A.M. (R3) and flight #169 is departing at 8:15 A.M.

Looking at inverted-list organization differently, suppose the passenger requests information on a Houston flight that departs at 8:15. The DBMS first searches the flight description index for the value of the "Houston flight.’’ It finds R3 and R6. Next it searches the flight departure index for these values. It. finds that the R3 value departs at 10:10, but the R6 value departs at 8:15. The record at location R6 in the data location area is displayed for follow-up.

It can be seen that inverted lists are best for applications that request specific data on multiple keys. They are ideal for static files because additions and deletions cause expensive pointer updating.