Efficient Cache Utilization in a Tiered Data Structure

摘要

A computer system detects a request to access a first data object stored in a tiered data structure that includes internal nodes and leaf nodes. In response to detecting the request, the computer system determines whether the first data object is stored in a cache that includes a plurality of data objects from the tiered data structure that are stored separately from their corresponding leaf node in the cache. When the first data object is stored in the cache, the computer system returns the first data object from the cache and when the first data object is not stored in the cache, the computer system traverses the tiered data structure to a leaf node that includes the first data object and returns the first data object from the leaf node for the first data object in the tiered data structure.

主权项

1. A method, performed by a computer system having one or more processors and memory, the method comprising:
detecting a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes; in response to detecting the request to access the first data object, determining whether the first data object is stored in a cache that includes a plurality of data objects from the tiered data structure, wherein the data objects stored in the cache are stored separately from the leaf node to which they correspond in the tiered data structure; and after determining whether the first data object is stored in the cache:
in accordance with a determination that the first data object is stored in the cache, returning the first data object from the cache to the requestor; andin accordance with a determination that the first data object is not stored in the cache, traversing the tiered data structure to a leaf node that includes the first data object and returning the first data object from the leaf node for the first data object in the tiered data structure to the requestor.