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.
If index is too large to be kept in main memory, a search results in
several disk reads.
If there are no overflow blocks in the index, we can use binary search.
This will read as many as blocks (as many as 7 for
our 100 blocks).
If index has overflow blocks, then sequential search typically used,
reading allb index blocks.
Solution: Construct a sparse index on the index
Figure 11.4: Two-level sparse index.
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.
For very large files, additional levels of indexing may be required.
Indices must be updated at all levels when insertions or deletions
Frequently, each level of index corresponds to a unit of physical
storage (e.g. indices at the level of track, cylinder and disk).