Indexing

1. In order to allow fast random access, an index structure may be used.

2. Two types:

   Dense Index:

   • An index record appears for every search key value in file.
   • This record contains search key value and a pointer to the actual record.
   Sparse Index:
   • Index records are created only for some of the records.
   • To locate a record, we find the index record with the largest search key value less than or equal to the search key value we are looking for.
   • We start at that record pointed to by the index record, and proceed along the pointers in the file (that is, sequentially) until we find the desired record.

• Primary Index
• Secondary Indices