Secondary Indices

1. Secondary indices may have different structure. Figure 8.5 shows a secondary index with an extra level.

    
   Figure 8.5:   Secondary index.
   

   • Pointers point to buckets containing pointers to the file.
   • This allows all pointers for one secondary search key value to be stored together (useful for certain types of queries).

   • Sequential scan in primary key order may be efficient because records are often stored in an order close to this.

   • To scan the file sequentially in a secondary key order, we may have to read in a new block for each record.
   • By storing pointers in a bucket (Figure 8.6), we do not need extra pointers in the records themselves.

      
     Figure 8.6:   Sparse secondary index on .
     

2. The secondary index may be dense or sparse.
   • See Figure 8.6 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.
   • If we use a dense secondary index we eliminate the need to read records with a different cname.
   • Secondary indices improve the performance of queries on non-primary keys.
   • They also impose serious overhead on database modification.
   • Designer must decide whether to use secondary indices or not.