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.
   • 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 all b index blocks.
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).