a hierarchical page table
Imagine a giant phone book for a whole country, but most of it is blank because most numbers are unassigned. Printing the whole thing wastes paper. Instead you print a thin 'table of regions': it lists only the regions that actually have numbers, and for each such region it points to a smaller booklet listing that region's numbers. Empty regions get no booklet at all. A HIERARCHICAL PAGE TABLE applies that trick to the page table: split the one enormous table into a top-level directory pointing to smaller second-level tables, and simply do not create the second-level tables for parts of the address space that are unused.
Here is why it is needed and how it works. A flat page table for a large address space is huge: a 32-bit space with 4 KB pages needs 2^20 entries, and a 64-bit space would need an absurd number — far too big to allocate as one contiguous array, especially since most processes use only a tiny, sparse fraction of their address space. The fix is to PAGE THE PAGE TABLE. The page number is split into several pieces: in a two-level scheme, the high piece indexes a top-level page directory whose entry points to a second-level page table; the low piece indexes that second-level table to find the frame; the offset then completes the physical address. Because directory entries for unused regions are simply marked empty, no second-level table is allocated for them, so the structure's size grows only with the memory a process actually uses. Real 64-bit CPUs use four or five levels for the same reason.
Hierarchical page tables matter because they make paging feasible for large, sparse address spaces, which is essentially all modern programs. The honest cost is in TLB misses: a miss now requires the hardware to WALK every level of the hierarchy, so a two-level table costs two extra memory accesses per walk, a four-level table costs four. This is exactly why the TLB hit ratio is so critical with deep hierarchies, and why hardware page-table walkers and intermediate caches exist. So the structure trades a slower miss for an enormous saving in table size — usually a very good trade, because hits dominate.
Two-level scheme, 32-bit address, 4 KB pages: split the 20-bit page number into a 10-bit directory index and a 10-bit table index. Address page number 0x00001 -> directory entry 0 -> second-level table -> table entry 1 -> frame. A process using only its first few pages needs just the directory plus ONE second-level table, not the full million entries.
Splitting the page number across levels lets the OS skip allocating tables for unused regions, shrinking the structure.
Multi-level tables save space for sparse address spaces, but each TLB miss must walk every level, so a four-level table costs four extra memory accesses per walk — which is why the TLB hit ratio matters even more with deep hierarchies.