inverted index

    A sequence of (key, pointer)
   pairs where each pointer points to a record in a database
   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. 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.  For databases in
   which the records may be searched based on more than one
   field, multiple indices may be created that are sorted on
   those keys.

   An index may contain gaps to allow for new entries to be added
   in the correct sort order without always requiring the
   following entries to be shifted out of the way.

   (1995-02-08)