为什么我们使用基树(或xarray)来存储页面缓存？

Question

我现在正在学习linux内核，了解linux内核(第3版)，我非常困惑为什么使用基树来存储整个页面缓存的原因是使用基树。(我听说在4.20版本之后，内核使用xarray)。

所以，我的问题是：

一旦我们想要某些特定的i-节点的信息，我们就应该查看"address_space“指向的整个页面缓存。

这本书说，他们使用基树快速搜索页面缓存，但我不明白这一点。

搜索什么页面缓存？难道我们不都需要吗？

请给我一些例子，为什么我们使用基树快速搜索页面缓存。

并跟进问题：

如果某些“i-节点”是address_space的主机，并且它保存了radix_tree_root和这个基树，那么所有的页面缓存都包含与文件相关的所有数据(这个i节点所指向的数据)？

Answer 1

基树是一个压缩的trie，其中trie是一个数据结构，它实现了一个关联数组的接口，并允许将值存储为键值。键通常是字符串，但任何数据类型都可以使用。trie与n-树不同，因为它的节点。trie的节点不存储键；相反，trie的节点存储单个字符标签。与给定节点相关的密钥是通过从树根遍历到该节点来导出的。例如：

    +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

在这个例子中，我们可以看到带键的trie，go和cat。压缩的trie或基树不同于trie，因为所有只有一个子节点的中间节点都被删除。

根树在主线内核树中有几个用户。PowerPC体系结构使用树在真实和虚拟IRQ数字之间进行映射。NFS代码将树附加到相关的inode结构，以跟踪未执行的请求。然而，基数树最广泛的使用是在内存管理代码中。用于跟踪备份存储的address_space结构包含一个基树，它跟踪绑定到映射的核心页。除其他外，此树允许内存管理代码快速查找脏页或正在写回的页。

下面是一个纸，它非常清楚地描述了这种设计机制。