Compaction of Information in Tiered Data Structure
First Claim
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;
two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and
the first data object is uniquely identified by a first key;
in response to detecting the request to access the first data object;
retrieving a leaf node that includes the first data object; and
identifying the first data object in the leaf node, including;
combining unique key information of the first data object with a key prefix that is stored separately in the leaf node to generate a combined key; and
determining that the combined key matches the first key that uniquely identifies the first data object; and
after identifying the first data object, providing access to the first data object to the requestor.
3 Assignments
0 Petitions
Accused Products
Abstract
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, where data objects in the leaf nodes include unique key information and corresponding values, and the first data object is uniquely identified by a first key. In response to detecting the request to access the first data object, the computer system retrieves a leaf node that includes the first data object and identifies the first data object in the leaf node by combining unique key information of the first data object with a key prefix that is stored separately in the leaf node to generate a combined key and determining that the combined key matches the first key that uniquely identifies the first data object. After identifying the first data object, the computer system provides access to the first data object.
-
Citations
25 Claims
-
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; two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and the first data object is uniquely identified by a first key; in response to detecting the request to access the first data object; retrieving a leaf node that includes the first data object; and identifying the first data object in the leaf node, including; combining unique key information of the first data object with a key prefix that is stored separately in the leaf node to generate a combined key; and determining that the combined key matches the first key that uniquely identifies the first data object; and after identifying the first data object, providing access to the first data object to the requestor. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer system, comprising:
-
one or more processors; memory; and one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for; 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; two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and the first data object is uniquely identified by a first key; in response to detecting the request to access the first data object; retrieving a leaf node that includes the first data object; and identifying the first data object in the leaf node, including; combining unique key information of the first data object with a key prefix that is stored separately in the leaf node to generate a combined key; and determining that the combined key matches the first key that uniquely identifies the first data object; and after identifying the first data object, providing access to the first data object to the requestor. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
20. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer system with one or more processors, cause the computer system to:
-
detect 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; two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and the first data object is uniquely identified by a first key; in response to detecting the request to access the first data object; retrieve a leaf node that includes the first data object; and identify the first data object in the leaf node, including; combining unique key information of the first data object with a key prefix that is stored separately in the leaf node to generate a combined key; and determining that the combined key matches the first key that uniquely identifies the first data object; and after identifying the first data object, provide access to the first data object to the requestor. - View Dependent Claims (21, 22, 23, 24, 25)
-
Specification