a multi-level page table

A single flat page table for a 64-bit address space would be impossibly large — most of it covering addresses no program ever touches. The fix is the same one a library uses instead of one gigantic index card: a tree of smaller tables, where you only create the branches you actually visit. A multi-level page table is a hierarchy of tables, each level narrowing down the address until the last level names the frame.

Here is how the lookup walks, in plain steps, using the common 4-level scheme on x86-64. The virtual page number is split into several chunks, one per level. The top register (cr3) points at the level-1 table; the first chunk of the address indexes into it to find the physical address of a level-2 table; the next chunk indexes into that to find a level-3 table; and so on, until the final chunk indexes the last table and yields the frame, which is then combined with the offset. The win is sparsity: if a whole region of the address space is unused, the upper-level entry for it is simply marked empty and no lower tables exist at all, so a process that uses a few megabytes needs only a handful of small tables rather than a giant flat one.

The cost is that a full translation now requires several memory reads (one per level) — a 'page-table walk'. That is precisely why the TLB exists: it caches the final answer so the multi-level walk is skipped on the common path. You rarely think about levels in everyday programming, but the structure explains why touching wildly scattered addresses is slower (more TLB misses, more walks) than touching nearby ones.