A 64-bit process may use a few small regions for code, dynamic memory, shared libraries, and thread stacks. Between those regions are enormous unmapped gaps.

A simple page table with one entry for every possible virtual page would still reserve entries for all those gaps. With a 48-bit usable virtual address and 4 KiB pages, the number of possible virtual pages is:

If every page-table entry used eight bytes, one flat table would require:

That is 512 GiB of mapping metadata for one process, even if the process uses only a few megabytes.

Multilevel page tables solve this mismatch by organizing page-table entries as a hierarchy. Lower levels are created only for virtual-address ranges that need them.

A multilevel page table is a sparse tree whose path of virtual-address indexes leads from one process's root to the entry for a virtual page.

The process still sees one virtual address space, and paging still maps virtual pages to physical frames. The hierarchy changes how the system stores and locates those mappings efficiently.

Start with a smaller 32-bit system using 4 KiB pages.

A 32-bit virtual address space contains:

A flat page table needs 1,048,576 entries. If one entry occupies four bytes:

Four MiB may sound modest, but it is overhead rather than application data. A system with 500 processes would need roughly 2 GiB merely for fully allocated flat tables:

Most processes do not map every virtual page. A small command-line program may use a few compact regions while leaving most of its 4 GiB address space empty. The corresponding flat-table entries still occupy memory even though they all say “unmapped.”

The waste becomes extreme as virtual addresses grow wider. Address-space size grows exponentially with address width, while a typical process remains sparse.

The goal is therefore not to remove page-table entries for mapped pages. Each mapped page still needs metadata. The goal is to avoid allocating entry storage for large ranges that contain no mappings at all.

A multilevel table divides the virtual page number into several indexes.

For a two-level design:

A virtual address splits into a level-1 index, a level-2 index, and a page offset.

The first index selects an entry in the root table. That entry either:

The second index selects the page-table entry within the chosen second-level table. That leaf entry identifies the physical frame and permissions for the virtual page.

If no mappings exist anywhere in the range covered by one root entry, the second-level table does not need to exist. One invalid root entry replaces an entire table of invalid leaf entries.

This is the source of the memory saving. The hierarchy behaves like a sparse tree:

The empty ranges cost one entry each rather than a whole table. That saving is the entire reason for the extra levels.

The root must exist for an active address space. Lower nodes exist only where a path toward one or more mapped pages is needed.

Consider the common teaching model:

One 4 KiB table holds:

Selecting one of 1024 entries requires 10 index bits.

The 32-bit virtual address is divided as follows:

The lower 12 bits select a byte within a 4 KiB page. The remaining 20-bit virtual page number is split into two 10-bit indexes.

The first-level table is commonly called a page directory in this model. It has 1024 entries. Each valid directory entry points to a second-level page table, which also has 1024 entries.

One second-level table maps:

The complete page directory can cover:

This exactly covers the 32-bit virtual address space.

The shape can be summarized as:

Each table occupies one physical frame in this example, but the tables do not need to be physically adjacent. Directory entries contain the information needed to locate the separate second-level tables.

Use the same two-level design to translate:

With 4 KiB pages, the lower 12 bits are the page offset:

The remaining virtual page number is:

Split that 20-bit VPN into two 10-bit indexes:

The mask 0x3ff contains ten one-bits and therefore selects the lower 10 bits.

The virtual address fields are:

Suppose:

The hardware walk is:

The physical address is:

The hierarchy changes only how the leaf entry is found. Once the leaf supplies a physical frame, forming the physical address is the same paging operation:

If directory entry 0x048 were invalid, the walk would stop immediately. The system would know that no usable lower-level entry exists for any virtual address in that directory entry's 4 MiB range.

Suppose a 32-bit process maps pages in four separate 4 MiB regions. It needs:

The flat design would require 4 MiB regardless of how few pages were mapped.

The saving is substantial, but multilevel tables do not allocate metadata with perfect one-entry granularity. Mapping one page in an otherwise empty 4 MiB range requires a whole 4 KiB second-level table:

Those unused entries are the price of grouping mappings into table-sized nodes. If more pages are later mapped in the same 4 MiB range, they reuse the existing table at little additional table-memory cost.

The memory benefit therefore depends on the shape of the process's virtual layout:

Multilevel tables are optimized for address spaces that are sparse overall but have locally clustered mappings, the usual shape of executable regions, heaps, libraries, and stacks.

A wider virtual address requires more index bits. Increasing the number of entries in one table would make each table large and difficult to allocate. Instead, hardware can add levels while keeping each table one page in size.

Consider a widely used 64-bit arrangement with:

Each table holds:

Each level therefore consumes nine virtual-address bits. Four levels consume:

Together with the 12-bit offset:

The address split is:

On conventional four-level x86-64 systems, these table levels are commonly called:

Names differ across architectures. The tree behavior is more important than the names.

For a normal 4 KiB mapping, an entry at each non-leaf level points to a table at the next level. The L1 leaf entry identifies the physical frame.

The amount of virtual space covered grows by a factor of 512 at each higher level:

The 256 TiB root coverage equals 2^48 bytes. Most processes use only a tiny portion of it, so most potential lower-level table nodes never exist.

Some 64-bit designs implement a different number of virtual-address bits or table levels. Software must follow the actual architecture and operating-system configuration rather than assuming that every 64-bit pointer implies one universal four-level format.

The processor needs a starting point for the active hierarchy. A privileged control register identifies the physical location of the current address space's root table or supplies equivalent architecture-specific context.

For a four-level walk, the hardware conceptually performs:

Page-table entries themselves reside in physical memory. Each non-leaf entry supplies a physical location for the next table, so the hardware does not need another virtual translation to find that next table. The kernel can separately map those table frames into its own virtual address space when it needs to edit them.

At every level, the hardware checks whether the entry is usable. If an upper-level entry is absent, the walk stops; the entire range below that entry lacks a current translation path.

Permissions can also be restricted along the path. The effective permission cannot exceed what the hierarchy allows. If an upper level prohibits user access, a leaf entry below it cannot independently grant user-mode access.

A complete walk requires several metadata reads before the requested instruction or data access can proceed. That is the main runtime cost introduced by adding levels.

Processors avoid performing a full memory-resident walk for every access by keeping recently used translation results in a specialized hardware cache. A full page-table walk is needed when the required translation is not already available there. The hierarchy and the cache solve different problems: the hierarchy reduces page-table memory, while the cache reduces repeated walk time.

It is useful to distinguish two entry types.

A non-leaf entry points to another page-table node:

a virtual-address index that resolves to the physical location of the next-level table

A leaf entry completes the translation:

a virtual-page index that resolves to a physical frame together with its permissions and status

An entry's bit layout is defined by the processor architecture. Typical information includes:

Not every architecture encodes the same permissions at every level, and some permissions may be represented inversely, for example an execute-disable bit rather than an execute-allow bit. The conceptual outcome is the same: the walk produces both a physical frame and effective access rights.

The page offset is never used to select a page-table entry. It passes through the walk unchanged and is combined with the final frame number.

When the operating system maps a virtual page, part of the required path may not exist.

Suppose a process first uses a virtual address whose L4 entry exists but whose L3 entry does not lead to a lower table. The kernel must create the missing nodes before installing the leaf mapping:

Starting from the existing L4 table, the kernel allocates L3, L2, and L1 nodes as required, then installs the leaf entry pointing at the physical frame.

New table pages must begin in a safe state with entries that do not accidentally grant access. The kernel links each node into the hierarchy using privileged updates and synchronizes changes when multiple CPUs or threads could interact with the same address space.

Unmapping a page clears or invalidates its leaf entry. If a lower-level table becomes completely empty, the kernel may reclaim that table page after ensuring that no hardware user can still rely on the old path.

The exact update protocol is architecture- and kernel-specific. The important lifecycle is:

This dynamic growth and pruning is how the hierarchy follows the sparse shape of a process over time.

Different processes normally have different root page tables or different root contexts.

The same virtual page number follows different trees and reaches different leaf entries. When the scheduler switches between processes, the kernel selects the translation root for the incoming address space.

Threads in the same process share the address-space root because they share virtual memory. Switching between those threads does not require a different process page-table hierarchy.

Some portions of a hierarchy can be intentionally shared. Operating systems may reuse structures for common kernel mappings or arrange selected user mappings to reach the same physical frames. Sharing a table node or frame is an explicit kernel decision; it does not weaken the rule that user code cannot install arbitrary paths into another process's memory.

The root is therefore part of a process's hardware-visible memory identity. A virtual address by itself is insufficient; the active root determines which hierarchy interprets it.

Multilevel page tables reduce waste, but their allocated nodes occupy real physical frames.

This overhead grows with:

Two processes with the same resident data size can use different amounts of page-table memory if one has a few dense mappings and the other has thousands of sparse mappings spread across the address space.

Table nodes needed for hardware translation must be accessible in physical memory. They are kernel-managed resources even though they describe user-space mappings. A process cannot safely edit its own raw entries.

Multilevel organization makes the overhead proportional to the used portions of the tree rather than the full theoretical address space. It does not make the overhead zero.

Linux exposes a process's page-table memory in /proc/<pid>/status. For the current shell:

A result might resemble:

VmPTE reports memory used by the process's page-table structures. It is not the number of mapped pages and not the size of the process's data. It is mapping metadata maintained by the kernel.

System-wide page-table memory is visible in /proc/meminfo:

Available fields vary with kernel version and architecture, but PageTables commonly reports the aggregate memory used for page-table structures.

/proc/<pid>/maps answers a different question. It shows virtual memory regions and their permissions:

It does not display the hierarchy of page-table nodes or one line per PTE. A virtual region is a kernel-level description of an address range; the page tables are the hardware-facing mappings used to enforce accesses within that range.

Multilevel page tables trade execution work for memory efficiency.

The benefit is sparse allocation. An absent upper-level entry represents a large unmapped range without allocating all lower-level entries beneath it.

The costs are:

Adding more levels extends the address range without making each node enormous, but it lengthens a full walk. Using fewer levels shortens the walk, but each table or entry must cover more of the address space.

The hierarchy works well because application address spaces are usually sparse and locally clustered, while hardware avoids repeating full walks for translations used frequently.

A flat page table reserves one entry for every possible virtual page, making it wasteful for large, sparse address spaces. A multilevel page table splits the virtual page number into indexes and uses them to walk a hierarchy from a process-specific root to a leaf entry.

Absent upper-level entries represent large unmapped ranges without allocating lower tables. Dense nearby mappings reuse existing nodes, while scattered mappings may require additional mostly empty nodes. This makes page-table memory follow the used shape of the address space instead of its full theoretical size.

The tradeoff is a longer lookup path. A full walk reads one entry at each level before obtaining the physical frame and permissions, while allocated table nodes consume physical memory of their own. Multilevel page tables make modern wide, sparse virtual address spaces practical by balancing mapping-memory cost against translation work.