Patent ID: 8631204

Claim:
A device comprising: an interface configured to receive a request for data that may be included in a cache memory; an information unit that has state information for the cache memory, the state information being organized in a hierarchical structure that includes a top level and a lower level, each of the top level and the lower level having identifiers that specify ranges of data addresses; and a processing unit that searches the hierarchical structure for the data, wherein the state information is balanced based at least in part upon a temporal factor that includes positioning a first range of the ranges of data addresses, which correspond to data that is more likely to be accessed from the cache memory, at a first location in the multiple searchable levels and positioning a second range of the ranges of data addresses, which correspond to data that is less likely to be accessed from the cache memory, at a second location in the multiple searchable levels, the first location requiring fewer comparisons to locate than the second location.