18章中遗留的2个问题，转换速度和内存开销，我们在19章中找到了TLB，通过缓存解决这个问题。剩下的就是内存开销，我们在第20章讨论这个问题。
最简单的方式，将页变大
转换页表的数量和虚拟页以及物理页的数量有关。在地址空间长度一定的情况下，页的大小越大，页码使用的bit就更少，自然页码范围就更小了。需要用来表达虚拟页和物理页映射关系的页表也就更小了。
但是这种方法违背了我们的初衷，把页变大会导致页内部有大量的碎片（按页分配，但是实际进程只使用了某页中极小一部分内存）。
混合（杂交）方式，页+段
这种方式综合了段+页来处理页占用空间的问题，并且也提到了平时处理问题的一种方式：将两种方法混合起来一起使用，可能会有意想不到的效果。
具体逻辑也比较简单，在定位到页表的某条映射记录时，通过段+VPN来定位到页表中的那个元素PTE（page table entry）。
如上面2个图，第一个图表示这种实现下虚拟地址的分布，第二张图则表示如何获得PTE的实际物理地址，获取到PTE后，就可以通过PTE中的PPN+虚拟地址的offset获得需要的实际物理地址了。
这种方式不无缺点，他解决的页层面的外部碎片，但是又带来了段内部可能的碎片。这也是段一直有的问题，不过段内部的碎片我们可以通过压缩的方式去减少。
参考上图，你会发现code，heap，stack之间在页表中的碎片，如果使用段来分别描述3段，让他抽象成3张页表。比如转化为base,bound=[1,1]，[5,1],[15,2]，然后让他们直接在物理上就可以是不连续的，这样就可以使碎片消失。
但是内部碎片呢？我们假设[5,1],[15,2]假如都是堆，也就是合并成[5,11]，那么内部依旧有很多碎片，段的问题就显现了。
多级页表
另外一种减少页表内存占用的方式，就是使用多级页表，多级页表使用另外的数据结构代替线性页表来存储页表，已达到节省空间的目的。其核心的思路是时间换空间，通过额外的查询搜索时间开销，来节省页表所使用的空间。
多级页表如何运作
多级页表首先改变了虚拟地址的定义，如下图
原先的虚拟地址定义，VPN直接表示虚拟的页码，或者段的信息，在多级页表下，VPN则由页表的目录和页表的Index组成。
我们看下页表目录的结构
其中左边的结构就是目录Page Directory，右边就是PageTableIndex需要检索到的Index。定位的方法也很简单，首先通过VPN前段的目录Index，得到PageDirectory中的某个节点，该节点中保存了下一级PageTable的物理地址，然后在下一级物理PageTable中，使用VPN后段的PageTableIndex，找到对应的节点，这样的话，最后获取到的节点中保存的，就是我们实际需要访问的物理地址页的存在，加上虚拟地址中的offset，我们就可以访问到我们需要的那块内存了。
更多级的页表，以及可以思考的一些地方
首先，例子中的页表可以有多级，但是既然出现了这样的结构，我们可以很容易联想到：红黑树，B+树等等用于存储树的结构。用类似的结构去优化搜索的效率和存储的性能。
我们还会发现，这样做的一个好处是，我们可以把页表中目录和每个节点以及最后的子节点，合理的也使用页去维护。即我们可以有多个PageDirectory，每个PageDirectory的大小也是页的大小，因为PageTable也得到了拆分，所以每个PageTable也可以是页的大小。通过这种设计，我们贯彻了内存中全部都是页的思路。可以想想按照最初的设计，内存中只有页表不是页，那是多么违和。
在操作系统的层面，页表按照这种方式规划以后，还有另外一个好处，OS可以进行一定的控制，让页表也使用虚拟内存来管理，并且可以让它的信息尽可能常驻在TLB中，以提升检索效率。这里其实还有一点需要再次回忆一下，虽然我们的VPN现在里面包含了多级页表的信息，但是实际上TLB依旧只缓存VPN-PPN的信息，TLB并不需要去计算这个过程。但是OS可以通过把页表的内存也虚拟化，来通过TLB加速这个多节点搜索中寻址的开销~
倒置页表
这是一种比较特殊的实现，即将索引关系倒置过来。这种实现只维护一个物理页表，但是在每个物理页页表元素的后面，使用一个数组来维护使用了这个物理页的进程列表，其中的每个进程元素，又保存了这个进程中的第几个虚拟页使用了这个物理页。书中没图，自己简单画了个。可以看到这种倒置的页表，搜索的性能也是倒置的，想要找到对应的进程，就已经需要n了，再找到请求的虚拟页，如果虚拟页和物理页大小一样的话还没开销，否则如果一个进程多个虚拟页映射到了同一个物理页，此时又要付出一个n去找到发起转义请求的那个虚拟页了
页表交换到硬盘
这个在上面也提到过，多级页表有个好处就是它可以天然把所有节点简单的分割成页的大小，这样结合到后面讲到的页会交换到硬盘，那么页表本身也就可以交换到硬盘了（因为页表的结构现在也是一个树状的页，只是每个叶子节点和非叶子节点的代销都是页大小）。
