Secondary Indices

1. If the search key of a secondary index is not a candidate key, it is not enough to point to just the first record with each search-key value because the remaining records with the same search-key value could be anywhere in the file. Therefore, a secondary index must contain pointers to all the records.

    
   Figure 11.5:   Sparse secondary index on cname.
   

2. We can use an extra-level of indirection to implement secondary indices on search keys that are not candidate keys. A pointer does not point directly to the file but to a bucket that contains pointers to the file.
   • See Figure 11.5 on secondary key cname.
   • To perform a lookup on Peterson, we must read all three records pointed to by entries in bucket 2.
   • Only one entry points to a Peterson record, but three records need to be read.
   • As file is not ordered physically by cname, this may take 3 block accesses.
3. Secondary indices must be dense, with an index entry for every search-key value, and a pointer to every record in the file.
4. Secondary indices improve the performance of queries on non-primary keys.
5. They also impose serious overhead on database modification: whenever a file is updated, every index must be updated.
6. Designer must decide whether to use secondary indices or not.