Hierarchical Page Tables
What you'll learn: How multi-level paging reduces memory overhead by breaking the page table itself into smaller, pageable pieces.
The Page Table Size Problem
As you've learned, page tables can become enormous. A 32-bit address space with 4 KB pages needs over 1 million entries per process. If each entry is 4 bytes, that's 4 MB just for one page table! Most of that table describes unused virtual memory, wasting precious physical memory.
The Hierarchical Solution
Hierarchical (or multi-level) paging solves this by organizing page tables as a tree rather than a flat array. Instead of one giant page table, you split the virtual address into multiple parts, each indexing a different level.
Think of it like a book: instead of a single 1-million-line index, you have a top-level table of contents pointing to chapter indexes, which point to actual pages. If a chapter doesn't exist, you don't need its index at all.
How It Works
In a two-level page table:
- The virtual address splits into three parts: outer page number, inner page number, and offset
- The outer page table (page directory) contains pointers to inner page tables
- Each inner page table contains the actual frame mappings
- If a chunk of virtual memory is unused, its entire inner table can be omitted—saving megabytes
For deeply virtual address spaces (64-bit), you might need three or even four levels, but the principle remains: only allocate page table structures for memory regions actually in use.
Trade-offs
Multi-level paging trades increased TLB-miss overhead (more memory accesses per translation) for dramatically reduced page table memory consumption. Modern systems accept this cost because most processes use only a tiny fraction of their virtual address space.
Key Takeaway:
Hierarchical page tables reduce memory waste by paging the page table itself—only creating table structures for actively used regions of virtual memory.