Data tree with order-based node traversal

Patent metadata

Field	Value
Publication number	US-11657092-B2
Application number	US-202117164299-A
Country	US
Kind code	B2
Filing date	Feb 1, 2021
Priority date	Dec 26, 2018
Publication date	May 23, 2023
Grant date	May 23, 2023

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).

First claim

What is claimed is:

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:
generating a new node associated with a particular key of a key-value pair, 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;
inserting the new node into the binary tree data structure to generate an updated binary tree data structure;
receiving a search request comprising an initial search key;
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, the initial node identified being the new node; and
traversing from the initial node to a 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 a 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 initial search key comprises a key prefix.

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

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

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

9. 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.

10. The system of claim 1 , comprising:
a set of memory components for persistent storage of key-value pair data;
wherein the operations 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.

11. A method comprising:
generating, by a processing device, for a binary tree data structure, a new node associated with a particular key of a key-value pair, 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;
inserting, by the processing device, the new node into the binary tree data structure to generate an updated binary tree data structure;
receiving, by the processing device, a search request comprising an initial search key;
in response to the search request, performing, by the processing device, 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, the initial node identified being the new node; and
traversing, by the processing device, from the initial node to a 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.

12. The method of claim 11 , wherein the new node comprises a pointer to the particular key of the key-value pair.

13. The method of claim 11 , wherein the new node comprises a pointer to a particular value of the key-value pair.

14. The method of claim 11 , 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.

15. The method of claim 11 , wherein the initial search key comprises a key prefix.

16. The method of claim 11 , wherein the binary tree data structure comprises a bonsai tree data structure.

17. The method of claim 11 , 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.

18. The method of claim 17 , wherein the inserting the new node into the binary tree data structure comprises using the read-copy-update mechanism.

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

20. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to perform operations comprising:
generating for a binary tree data structure, a new node associated with a particular key of a key-value pair, 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;
inserting the new node into the binary tree data structure to generate an updated binary tree data structure;
receiving a search request comprising an initial search key;
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, the initial node identified being the new node; and
traversing from the initial node to a 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.

Assignees

• Micron Technology Inc

Inventors

• Burton David
• Becker Greg A
• Tomlinson Alexander

Classifications

• G06F16/9027 Primary

  Trees · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/903

  Querying (for retrieval from the web G06F16/953) · CPC title