Patent ID: 8510499

Claim:
A method comprising: storing a mapping entry comprising a mapping of a storage volume data location to a solid state drive (SSD) memory location, wherein the mapping entry is stored in a tree data structure; storing data from the storage volume data location in the SSD memory location; storing a timestamp with the mapping entry wherein the timestamp is associated with a last time the data stored in the SSD memory location is accessed; determining an oldest timestamp of all entries stored in a node of the tree data structure; storing the oldest timestamp in association with a key entry linked to the node of the tree data structure in a parent node of the node; and finding a least recently accessed SSD memory location, wherein the least recently accessed SSD memory location has a first mapping entry stored with the oldest timestamp, and the finding comprises searching a first node of the tree data structure for the first mapping entry stored with the oldest timestamp, if the first node is a leaf node of the tree data structure, identifying the SSD memory location stored in the first mapping entry, and if the first node is not a leaf node, performing identifying the key in the first mapping entry, following the key to a child node, and repeating said searching.