next up previous
Next: B-Tree Index Files Up: Ordered Indices Previous: Index Update

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.

  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.

Osmar Zaiane
Mon Jul 13 13:28:03 PDT 1998