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 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 of the disjointed range partitions are deleted. A first new cached partition range that contains the data value is created; it excludes at least one value that had been cached. The remaining values are placed in uncached range partitions; contents of the cache are updated to reflect the new range partition.
