One embodiment of the present invention provides a system that manages an
LRU list such that the rank, or position, of data records in the sequence
can be determined efficiently. The system initializes an index field in
each record to the record's initial rank. When a record is accessed, the
system moves it to the beginning of the LRU list and appends the value of
the record's index field to a "change list." The system then sets the
record's index field to zero. The change list effectively tracks the
records accessed since initialization, and combined with the records'
index fields can be used to efficiently compute the rank of any record in
the list. This ability to efficiently compute the rank of the data record
in the LRU list reduces the frequency with which the
computationally-expensive initialization operation must be executed on
the LRU list.