很多關於僞LRU算法的描述都涉及使用二叉搜索樹，並設置標誌以在您每次訪問樹時從您正在搜索的節點「指向」。僞LRU樹算法
這導致了LRU的合理近似。然而，從描述看來，所有被視爲LRU的節點都是葉節點。是否存在一種僞LRU算法來處理靜態樹，該靜態樹仍然可以相當好地運行，同時確定非葉節點是否適合LRU候選者？
編輯： 我已經使用hashmaps和linkedlists實現了一個LRU。我有興趣看到使用僞lru樹的性能影響（特別是在併發讀取上）。這就是爲什麼我特意詢問僞lru樹算法的原因，但我應該更清楚一些。
您可以隨時使用旋轉ala紅黑樹將內部節點推向葉子。
保持樹平衡，而這樣做可能會很艱難。但你可以選擇推下哪個子樹，所以也許並非不可能...
我想保持樹結構靜態，以允許併發讀取，以及出於性能原因。 （我意識到旗幟上會存在競爭條件，但我不在乎，因爲它只是僞LRU。） – patros 2010-05-03 20:20:24
如何保持樹靜態？您要刪除的節點和您添加的節點不具有相同的密鑰，因此它們會位於樹的不同部分。你的意思是「緩存命中期間的靜態」，所以你可以使用讀鎖來查找？ – 2010-05-03 22:15:09
密鑰保持不變。我將我的數據映射到任意索引（0到（2^depth）-1）。當我「刪除」某些東西時，我只是將該樹的節點添加到可用節點列表中。當我添加時，我不添加節點，我只是簡單地覆蓋節點所擁有的數據。這使樹結構保持靜態，但數據仍然是可變的。 – patros 2010-05-04 01:35:34
根據這裏提供的基準數字Study of Different Cache Line Replacement Algorithms in Embedded Systems，僞LRU（PLRUm，PLRUt，MPLRU）顯示爲實現的最佳候選。
也許這會說服你使用哈希表+鏈表：http://stackoverflow.com/questions/2504178/lru-cache-design/2504317#2504317 – 2010-05-22 13:55:55