Course contentsShow
← Computer Science
Lesson 1358 of 2,87231. Memory ManagementFree lesson

Hierarchical Page Tables

Learning multi-level paging where page tables are themselves paged to reduce memory overhead.

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.