伪LRU树算法

Question

伪LRU算法的许多描述都涉及到使用二叉树，并在每次访问树时将标志设置为“指向”要搜索的节点。

这导致了LRU的合理近似值。然而，从描述中看，所有被认为是LRU的节点都将是叶节点。有没有一种伪LRU算法可以处理静态树，在确定非叶子节点是合适的LRU候选者的同时，仍然可以很好地执行？

编辑:我已经使用hashmap和linkedlist实现了一个LRU。我对使用伪lru树的性能影响很感兴趣(特别是在并发读取时)。这就是为什么我特别询问伪lru树算法的原因，但我应该说得更清楚。

Answer 1

您始终可以使用旋转红黑树将内部节点向下推到叶。

在这样做的同时保持树的平衡可能是困难的。但是你确实可以选择下推哪个子树，所以也许不是不可能的……

Answer 2

根据这里给出的基准数字，伪Study of Different Cache Line Replacement Algorithms in Embedded Systems (PLRUm，PLRUt，MPLRU)似乎是实现的最佳候选者。