Data tree with order-based node traversal

• US 10,936,661 B2
• Filed: 12/26/2018
• Issued: 03/02/2021
• Est. Priority Date: 12/26/2018
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Burton, David, Becker, Greg A., Tomlinson, Alexander
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US16/232,422
• Publication Number:
  US 20200210482A1
• Time in Patent Office: 797 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953

Abstract

Aspects of the present disclosure provide for operations for a tree data structure that provides order-based node traversal. For some embodiments, the tree data structure stores one or more key-value pairs, implements at least one linked-list data structure, and enables traversal of nodes within the tree data structure based on a key order (e.g., forward or reverse key order).

Claims

1. A system comprising:

volatile memory storing a binary tree data structure; and

a processing device, operatively coupled to the volatile memory, configured to perform operations comprising;

receiving a key-value pair comprising a particular key and a particular value;

in response to receiving the key-value pair;

generating a new node associated with the particular key, the new node comprising a first pointer to point to a first child node of the new node, a second pointer to point to a second child node of the new node, a previous pointer to point to a previous node, and a next pointer to point to a next node, wherein based on a key order, the particular key is adjacent to both a first key associated with the previous node and a second key associated with the next node; and

inserting the new node into the binary tree data structure to generate an updated binary tree data structure;

receiving a request to traverse from the new node of the updated binary tree data structure to a subsequent node of the updated binary tree data structure based on the key order; and

based on the request to traverse, traversing to the subsequent node of the updated binary tree data structure by at least one of the previous pointer of the new node or the next pointer of the new node.

2. The system of claim 1, wherein the new node comprises a pointer to the particular key of the key-value pair.

3. The system of claim 1, wherein the new node comprises a pointer to the particular value of the key-value pair.

4. The system of claim 1, wherein the key order comprises a consecutive key order, the first key comprises a higher value than the particular key, and the second key comprises a lower value than the particular key.

5. The system of claim 1, wherein the operations further comprise:

receiving a search request comprising an initial search key; and

in response to the search request, performing a binary search on the binary tree data structure to identify an initial node associated with the initial search key, the binary search being performed using at least one of a particular first pointer of a root node of the binary tree data structure or a particular second pointer of the root node.

6. The system of claim 5, wherein the initial search key comprises a key prefix.

7. The system of claim 1, wherein the key order comprises a consecutive key order, the first key comprises a higher value than the particular key, the second key comprises a lower value than the particular key, and the traversing to the subsequent node by at least one of the previous pointer or the next pointer is determined based on whether the traversing comprises at least one of a scan up request or a scan down request.

8. The system of claim 1, wherein the traversing to the subsequent node is performed without applying a lock on the updated binary tree data structure.

9. The system of claim 1, wherein the binary tree data structure comprises a bonsai tree data structure.

10. The system of claim 1, wherein the binary tree data structure comprises a read-copy-update mechanism to control concurrent data access to the binary tree data structure by a plurality of processes.

11. The system of claim 10, wherein the inserting the new node into the binary tree data structure comprises using the read-copy-update mechanism.

12. The system of claim 1, wherein the binary tree data structure implements a key-value set in a sequence of key-value sets stored on the volatile memory.

13. The system of claim 1, further comprising:

a set of memory components for persistent storage of key-value pair ata;

wherein the operations further comprise;

determining whether a condition is satisfied to move key-value pair data from the binary tree data structure; and

in response to determining that the condition is satisfied, moving key-value pair data from the binary tree data structure to a new key-value set stored on persistent data storage space.

14. A method comprising:

receiving a key-value pair comprising a particular key and a particular value;

in response to receiving the key-value pair;

generating, by a processing device, for a binary tree data structure, a new node associated with the particular key, the new node comprising a first pointer to point to a first child node of the new node, a second pointer to point to a second child node of the new node, a previous pointer to point to a previous node, and a next pointer to point to a next node, wherein based on a key order, the particular key is adjacent to both a first key associated with the previous node and a second key associated with the next node; and

inserting, by the processing device, the new node into the binary tree data structure to generate an updated binary tree data structure;

receiving a request to traverse from the new node of the updated binary tree data structure to a subsequent node of the updated binary tree data structure based on the key order; and

based on the request to traverse, traversing to the subsequent node of the updated binary tree data structure by at least one of the previous pointer of the new node or the next pointer of the new node.

15. The method of claim 14, wherein the key order comprises a consecutive key order, the first key comprises a higher value than the particular key, and the second key comprises a lower value than the particular key.

16. The method of claim 14, further comprising:

receiving a search request comprising an initial search key; and

in response to the search request, performing a binary search on the binary tree data structure to identify an initial node associated with the initial search key, the binary search being performed using at least one of a particular first pointer of a root node of the binary tree data structure or a particular second pointer of the root node.

17. The method of claim 14, wherein the key order comprises a consecutive key order, the first key comprises a higher value than the particular key, the second key comprises a lower value than the particular key, and the traversing to the subsequent node by at least one of the previous pointer or the next pointer is determined based on whether the traversing comprises at least one of a scan up request or a scan down request.

18. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to perform operations comprising:

receiving a key-value pair comprising a particular key and a particular value;

in response to receiving the key-value pair;

generating, for a binary tree data structure, a new node associated with the particular key, the new node comprising a first pointer to point to a first child node of the new node, a second pointer to point to a second child node of the new node, a previous pointer to point to a previous node, and a next pointer to point to a next node, wherein based on a key order, the particular key is adjacent to both a first key associated with the previous node and a second key associated with the next node; and

inserting the new node into the binary tree data structure to generate an updated binary tree data structure;

receiving a request to traverse from the new node of the updated binary tree data structure to a subsequent node of the updated binary tree data structure based on the key order; and

based on the request to traverse, traversing to the subsequent node of the updated binary tree data structure by at least one of the previous pointer of the new node or the next pointer of the new node.

19. The non-transitory machine-readable storage medium of claim 18, wherein the key order comprises a consecutive key order, the first key comprises a higher value than the particular key, the second key comprises a lower value than the particular key, and the traversing to the subsequent node by at least one of the previous pointer or the next pointer is determined based on whether the traversing comprises at least one of a scan up request or a scan down request.

20. The non-transitory machine-readable storage medium of claim 18, wherein the traversing to the subsequent node is performed without applying a lock on the updated binary tree data structure.