Key-value store tree data block spill with compaction
AssigneeMicron Technology, Inc.
InventorsAlexander Tomlinson, Greg A. Becker, Gaurav Sanjay Ramdasi
Life of this patent
Estimating the term…
Abstract
Aspects of the present disclosure provide for operations of a key-value tree data structure that: merge key-value sets within a given node by merging and rewriting key blocks of the key-value sets while rewriting or deferring rewrite of value blocks of the merged key-value sets based on whether one or more child nodes of the given node comprise a leaf node; and move one or more portions of the merged key-value set into one or more child nodes of the given node.
Claims20
A system comprising:
- a set of memory components storing a key-value store tree data structure, the key-value store tree data structure comprising a set of nodes, wherein a node in the set of nodes comprises a sequence of key value sets;
- and
- a processing device, operatively coupled to the set of memory components, configured to perform operations comprising:
- detecting for a condition to merge and move the sequence of key-value sets from the node of the key-value store tree data structure to a set of child nodes of the node;
- and
- in response to detecting the condition:
- determining whether the set of child nodes of the node comprises a leaf node;
- and
- moving the sequence of key-value sets to the set of child nodes based on the determining whether the set of child nodes comprises the leaf node.
A method comprising:
- generating, on a set of memory components, a key-value store tree data structure, the key-value store tree data structure comprising a set of nodes, wherein a node in the set of nodes comprises a sequence of key value sets;
- detecting, by a processing device, for a condition to merge and move the sequence of key-value sets from the node to a set of child nodes of the node;
- and
- in response to detecting the condition:
- determining, by the processing device, whether the set of child nodes of the node comprises a leaf node;
- and
- moving, by the processing device, the sequence of key-value sets to the set of child nodes based on the determining whether the set of child nodes comprises the leaf node.
A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to:
- access, on a set of memory components, a key-value store tree data structure, the key-value store tree data structure comprising a set of nodes, wherein a node in the set of nodes comprises a sequence of key value sets;
- detect for a condition to merge and move the sequence of key-value sets from the node to a set of child nodes of the node;
- and
- in response to detecting the condition:
- determine whether the set of child nodes of the node comprises a leaf node;
- and
- move the sequence of key-value sets to the set of child nodes based on the determining whether the set of child nodes comprises the leaf node.
Dependencies are inferred from the claim text.