1、Pseudo-LRU 和 LRU

缓存替换策略是用于确定在缓存空间已满时应该替换哪些缓存项。Pseudo-LRU（Pseudo-Least Recently Used）和LRU（Least Recently Used）都是常见的缓存替换策略，它们之间有以下区别：

原理：

  • LRU：LRU 策略基于最近访问的时间来判断缓存项的使用频率。当缓存空间已满时，它会选择最长时间未被访问的缓存项进行替换。
  • Pseudo-LRU：Pseudo-LRU 也被称为近似 LRU。它使用一个二叉树或类似的数据结构来维护缓存项的访问历史。每个节点表示一个缓存项，树的叶子节点表示缓存项的状态（被使用或未被使用）。通过比较叶子节点的状态，Pseudo-LRU 策略选择未被使用的缓存项进行替换。

实现复杂度：

  • LRU：LRU 算法相对简单，不需要维护额外的数据结构，只需使用一个数据结构（如双向链表）来记录访问顺序。
  • Pseudo-LRU：Pseudo-LRU 实现相对复杂，需要维护一个额外的数据结构（如二叉树）来跟踪缓存项的访问状态。

准确性：

  • LRU：LRU 策略准确地跟踪每个缓存项的访问时间，并选择最长时间未被访问的缓存项进行替换。
  • Pseudo-LRU：Pseudo-LRU 策略是一种近似算法，它通过维护一个二叉树来估计缓存项的访问时间，因此可能会在某些情况下做出不太准确的替换决策。