Method and device to access auxiliary mapping data for a data structure

• US 10,445,372 B2
• Filed: 02/01/2016
• Issued: 10/15/2019
• Est. Priority Date: 02/01/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Kanaujia, Vishal, Krishnan, Manavalan, O'Krafka, Brian Walter, Chander, Ramesh, Neelakanta, Niranjan Patre
• Primary Examiner(s): Arjomandi, Noosha
• Application Number:
  US15/012,606
• Publication Number:
  US 20170220634A1
• Time in Patent Office: 1,352 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 with a processor to determine whether the auxiliary mapping data includes an indication of a key associated with a node of a single 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 in a single lookup table which indicates a mapping of a leaf node, wherein the key is associated with the leaf node, the single lookup table separate from a level 1 cache;

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

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

searching the auxiliary mapping data for the indication; and

retrying the hash operation one or more times after failing to identify the key by searching the auxiliary mapping data.

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, wherein the key points to a single data object of the data.

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

6. The method of claim 5, 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.

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

8. 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;

a second group of storage elements configured to store second data corresponding to a single lookup table associated with the tiered data structure and separate from a level 1 cache, the single 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; and

a controller configured to perform a hash operation based on the key to generate the indication, wherein the controller is configured to search an auxiliary mapping data for the indication, and wherein the controller is configured to retry the hash operation one or more times after failing to identify the key by searching the auxiliary mapping data.

9. The apparatus of claim 8, wherein the controller is configured to access the lookup table.

10. The apparatus of claim 9, 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.

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

12. The apparatus of claim 9, 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.

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

14. The apparatus of claim 8, 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 single lookup table.

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

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

17. 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 in a single look up table format, separate from a level 1 cache, and including an indication associated with the key wherein the key is associated with a leaf node and further indicating a node identification associated with the indication, wherein the controller is configured to perform a hash operation based on the key to generate the indication, wherein the controller is configured to search an auxiliary mapping data for the indication, and wherein the controller is configured to retry the hash operation one or more times after failing to identify the key by searching the auxiliary mapping data.

18. The data storage device of claim 17, 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.