Indexing Mechanisms
In the case of indexing, a data value (or values, if the index is composite) from a row acts as an index key to that row. The index associates the index key with a relative row address that reports the location of the row on disk. Indexes are stored in order of their index key values and are said to be value-ordered.
Think of an index on a database table as you would think of the index to a book. A book index typically provides two data values: a character string indicating the indexed topic and a page number or numbers indicating the location of that information in the book.
If the topic is unique, then there is only one page number listed for it. If the topic is nonunique, then there might be several pages listed for it.
To find a piece of information in a book, you can either consult the index, find the topic you need, and then turn directly to the appropriate page (think of this as an indexed retrieval) or you can start reading the book from the beginning and stop only when you find the information you seek (think of this as a full‑table scan).