METHOD AND DEVICE TO ACCESS AUXILIARY MAPPING DATA FOR A DATA STRUCTURE

• US 20170220634A1
• Filed: 02/01/2016
• Published: 08/03/2017
• Est. Priority Date: 02/01/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: KANAUJIA, VISHAL, KRISHNAN, MANAVALAN, O'KRAFKA, BRIAN WALTER, CHANDER, RAMESH, NEELAKANTA, NIRANJAN PATRE
• Granted Patent: US 10,445,372 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A method includes accessing, in response to initiating an operation targeting data, auxiliary mapping data to determine whether the auxiliary mapping data includes an indication of a key associated with a node of a hierarchical data structure that is associated with the data. In response to the auxiliary mapping data including the indication of the key, the data is accessed from a memory using a node identification associated with the key. In response to the auxiliary mapping data not including the indication of the key, the data is accessed from the memory using a search operation.

Claims

1. A method comprising:

in response to initiating an operation targeting data, accessing auxiliary mapping data to determine whether the auxiliary mapping data includes an indication of a key associated with a node of a hierarchical data structure that is associated with the data;

in response to the auxiliary mapping data including the indication of the key, accessing the data from a memory using a node identification associated with the key; and

in response to the auxiliary mapping data not including the indication of the key, accessing the data from the memory using a search operation.

2. The method of claim 1, wherein accessing the data using the node identification includes bypassing one or more internal nodes of the hierarchical data structure to directly access the node.

3. The method of claim 1, wherein accessing the data using the search operation includes searching one or more internal nodes of the hierarchical data structure to identify the node.

4. The method of claim 1, further comprising:

performing a hash operation based on the key to generate the indication; and

searching the auxiliary mapping data for the indication.

5. The method of claim 4, further comprising retrying the hash operation one or more times after failing to identify the key by searching the auxiliary mapping data.

6. The method of claim 1, wherein the key points to a single data object of the data.

7. The method of claim 1, wherein the key points to a group of multiple data objects of the data.

8. The method of claim 7, wherein the data corresponds to a non-relational database, and wherein the group of multiple data objects corresponds to a row key of the non-relational database.

9. The method of claim 1, wherein the data is associated with a database, a key value store, an object store, or a file system.

10. An apparatus comprising:

a first group of storage elements configured to store first data associated with a tiered data structure having a root node and a set of leaf nodes; and

a second group of storage elements configured to store second data corresponding to a lookup table associated with the tiered data structure, the lookup table indicating a mapping of a leaf node of the set of leaf nodes to an indication of a key that is associated with the leaf node.

11. The apparatus of claim 10, further comprising a controller configured to access the lookup table.

12. The apparatus of claim 11, wherein the controller is further configured to bypass one or more internal nodes of the tiered data structure by directly accessing the leaf node using a node identification indicated by the lookup table.

13. The apparatus of claim 11, wherein the controller includes a hash engine configured to perform a hash operation based on the key to generate the indication and to store the indication to the second group of storage elements.

14. The apparatus of claim 11, wherein the controller is further configured to access the node in connection with one or more of a read process associated with the leaf node, a write process associated with the leaf node, or an update process associated with the leaf node.

15. The apparatus of claim 11, wherein the controller is further configured to update the lookup table using one or more of a read operation, a write operation, an update operation, or a delete operation.

16. The apparatus of claim 10, further comprising a level one (L1) cache configured to store at least a subset of the first data, wherein the L1 cache is distinct from the lookup table.

17. The apparatus of claim 10, further comprising a non-volatile memory that includes the first group of storage elements.

18. The apparatus of claim 10, further comprising a random access memory (RAM) that includes the second group of storage elements.

19. A data storage device comprising:

a memory; and

a controller coupled to the memory, wherein the controller is configured to access data stored at the memory based on a key associated with the data, wherein the data is associated with a hierarchical data structure, and wherein the controller is further configured to access lookup information associated with the hierarchical data structure, the lookup information including an indication associated with the key and further indicating a node identification associated with the indication.

20. The data storage device of claim 19, wherein the controller is further configured to bypass one or more internal nodes of the hierarchical data structure by directly accessing a leaf node using a node identification indicated by the lookup information.