next up previous
Next: Multi-Level Indices Up: Primary Index Previous: Primary Index

Dense and Sparse Indices

  1. There are Two types of ordered indices:

    Dense Index:

    Sparse Index:
  2. Figures 11.2 and 11.3 show dense and sparse indices for the deposit file.

    Figure 11.2:   Dense index.

  3. Notice how we would find records for Perryridge branch using both methods. (Do it!)

    Figure 11.3:   Sparse index.

  4. Dense indices are faster in general, but sparse indices require less space and impose less maintenance for insertions and deletions. (Why?)
  5. A good compromise: to have a sparse index with one entry per block.

    Why is this good?

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