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.