next up previous
Next: Index Update Up: Primary Index Previous: Dense and Sparse Indices

Multi-Level Indices

  1. Even with a sparse index, index size may still grow too large. For 100,000 records, 10 per block, at one index record per block, that's 10,000 index records! Even if we can fit 100 index records per block, this is 100 blocks.
  2. If index is too large to be kept in main memory, a search results in several disk reads.
  3. Solution: Construct a sparse index on the index (Figure 11.4).

    Figure 11.4:   Two-level sparse index.

  4. Use binary search on outer index. Scan index block found until correct index record found. Use index record as before - scan block pointed to for desired record.
  5. For very large files, additional levels of indexing may be required.
  6. Indices must be updated at all levels when insertions or deletions require it.
  7. Frequently, each level of index corresponds to a unit of physical storage (e.g. indices at the level of track, cylinder and disk).

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