A method to store a data value onto a cache of a storage hierarchy. A range of a collection of values that resides on a first tier of the hierarchy is initialized. The range is partitioned into disjointed range partitions; a first subset of which is designated as cached; a second subset is designated as uncached. The collection is partitioned into a subset of uncached data and cached data and placed into respective partitions. The range partition to which the data value belongs (i.e. the target range partition) is identified as being cached. If the cache is full all cached range partitions that do not contain the data value are designated as uncached. All values that lie in the cached range partitions designated as uncached are evicted. The data value is then inserted into the target range partition, and copied to the first tier.