Dictionary.net

A sequence of (key, pointer)pairs where each pointer points to a record in a databasewhich contains the key value in some particular field. Theindex is sorted on the key values to allow rapid searching fora particular key value, using e.g. binary search. The indexis "inverted" in the sense that the key value is used to findthe record rather than the other way round. For databases inwhich the records may be searched based on more than onefield, multiple indices may be created that are sorted onthose keys.An index may contain gaps to allow for new entries to be addedin the correct sort order without always requiring thefollowing entries to be shifted out of the way.