Многие описания алгоритмов псевдо-LRU включают использование бинарного дерева поиска и установку флагов, чтобы «указывать» от узла, который вы ищете, каждый раз, когда вы получаете доступ к дереву.
Это приводит к разумному приближению LRU. Однако из описаний видно, что все узлы, которые считаются LRU, будут конечными узлами. Существует ли алгоритм псевдо-LRU, который имеет дело со статическим деревом, которое все еще будет работать достаточно хорошо, при этом определяя, что неконечные узлы являются подходящими кандидатами LRU?
редактировать:
Я уже реализовал LRU с использованием хэш-карт и связанных списков. Я заинтересован в том, чтобы увидеть влияние производительности на использование дерева псевдо-lru (особенно при одновременном чтении).
Вот почему я специально спросил об алгоритмах псевдоструйного дерева, но мне следовало бы прояснить это.