Multilevel Index

Suppose we have an index on id column for a table with 10 million rows. The index will eventually become too large that can’t be fit in memory, so we would have to store it somewhere in disk blocks.

The search for an entry in the index would require several disk blocks access. One way to improve this is to use multilevel index. We treat the index just as a database table, and construct another index (outer index) on this index (inner index).

We can repeat this process as many times as needed, until the outer index has small size that can be kept in memory. This would reduce the number of disk accesses significantly.