DATA TREE WITH ORDER-BASED NODE TRAVERSAL
First Claim
Patent Images
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; and
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.
5 Assignments
0 Petitions
Accused Products
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).
14 Citations
20 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; and 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A method comprising:
-
receiving a key-value pair comprising a particular key and a particular value; and 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. - View Dependent Claims (16, 17, 18, 19)
-
-
20. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to:
-
receive a key-value pair comprising a particular key and a particular value; and in response to receiving the key-value pair; generate, for a tree data structure, a new node associated with the particular key, the new node comprising a set of child pointers to point to one or more child nodes of the new node in the tree data structure, and a set of linked-listed pointers to point to one or more adjacent nodes of linked lists associated with the set of linked-listed pointers; and insert the new node into the tree data structure to generate an updated tree data structure.
-
Specification