Patent attributes
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 portions. 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, the target range partition is divided into two partitions, the partition that excludes the data value is designated as uncached; the values therein are evicted. If the cache has space, the data value is copied onto the cache; otherwise the division/eviction are repeated until the cache has space.
