a multilevel page table

Imagine you must keep a directory for a building with a billion possible room numbers, but only a few thousand rooms actually exist. Writing out a billion rows — most saying 'empty' — would be absurd. Instead you keep a slim top-level index of neighbourhoods, and only for neighbourhoods that contain real rooms do you bother to create a detailed sub-directory. A multilevel page table is exactly this nested, only-where-needed structure for translations.

Concretely, the virtual page number is split into several fields, one per level. The first field indexes a top-level table whose entry points to a second-level table; the next field indexes that; and so on until the last level gives the physical frame. Crucially, sub-tables are created only for regions of the address space that are actually used — an unused branch is just a single empty entry at the level above, not a giant table of empties. So a 64-bit address space, whose flat page table would be astronomically large, is represented compactly because most of it is never mapped. Real machines use three, four, or five levels.

Why it matters: multilevel page tables are how virtual memory scales to enormous address spaces without spending all of RAM on the page table itself — they trade space for time. The honest cost is exactly that time: a TLB miss now requires a page-table walk that touches memory once per level (four levels means up to four extra memory accesses to translate one address). That is why the TLB matters so much, and why some systems cache intermediate walk steps or use larger pages to shorten the walk. Sparse address spaces are the win; deep walks on a TLB miss are the price.