多層分頁表（hierarchical page table）

想像一整個國家的巨型電話簿，但大部分是空白的，因為多數號碼未配發。整本印出來只是浪費紙。換個做法：你印一本薄薄的「地區索引」，只列出真正有號碼的地區，並為每個這樣的地區指向一本較小的小冊子，列出該地區的號碼。空白地區則完全沒有小冊子。多層分頁表把這個招數套用到分頁表上：把那一張龐大的表拆成一本指向多本第二層表的頂層目錄，而位址空間中未使用的部分，乾脆就不建立其第二層表。

它為何需要、又如何運作。針對大位址空間的平面分頁表非常龐大：4 KB 頁的 32 位元空間需要 2^20 筆項目，64 位元空間更要荒謬的數量——大到無法配置成一個連續陣列，尤其多數行程只用到自己位址空間中極小、極稀疏的一小塊。解法是「把分頁表也分頁」。頁號被拆成數段：在兩層方案中，高位段索引一本頂層分頁目錄，其項目指向一張第二層分頁表；低位段索引那張第二層表以找出頁框；偏移再補完實體位址。由於未使用地區的目錄項目只是被標為空，便不會為它們配置第二層表，因此整個結構的大小只隨行程實際用到的記憶體增長。真實的 64 位元 CPU 基於同樣理由使用四或五層。

多層分頁表之所以重要，是因為它讓分頁對大型、稀疏的位址空間變得可行，而那基本上就是所有現代程式。誠實的代價在 TLB 失誤：如今一次失誤要硬體「走訪」階層的每一層，所以兩層表每次走訪多花兩次記憶體存取、四層表多花四次。這正是為何在深階層下 TLB 命中率如此關鍵，也是硬體走表器與中間快取存在的原因。所以這個結構以較慢的失誤，換取表大小上的巨大節省——通常是非常划算的交易，因為命中佔了主導。