Back to results
US 11,100,071 B2Granted
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 memory sub-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, wherein each key-value set of the node comprises at least one value block, and wherein each individual value block of the node is assigned a data generation number indicating a sequence order at which the individual value block was initially generated for the key-value store tree data structure;
- 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
- in response to determining that the set of child nodes comprises the leaf node, moving the sequence of key-value sets to the set of child nodes, the moving the sequence of key-value sets to the set of child nodes comprising:
- merging the sequence of key-value sets to produce a merged key-value set, the merged key-value set comprising a set of new key blocks that reference a set of new value blocks, and the set of new value blocks being assigned a particular largest data generation number assigned to any value block in a set of existing value blocks of the sequence of key-value sets.
6 more elements
A method comprising:
- generating, on a set of memory components of a memory sub-system, 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, wherein each key-value set of the node comprises at least one value block, and wherein each individual value block of the node is assigned a data generation number indicating a sequence order at which the individual value block was initially generated for the key-value store tree data structure;
- detecting, by a processing device of the memory sub-system, 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
- in response to determining that the set of child nodes comprises the leaf node, moving, by the processing device, the sequence of key-value sets to the set of child nodes, the moving the sequence of key-value sets to the set of child nodes comprising:
- merging the sequence of key-value sets to produce a merged key-value set, the merged key-value set comprising a set of new key blocks that reference a set of new value blocks, and the set of new value blocks being assigned a particular largest data generation number assigned to any value block in a set of existing value blocks of the sequence of key-value sets.
5 more elements
A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device of a memory sub-system, cause the processing device to:
- access, on a set of memory components of the memory sub-system, 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, wherein each key-value set of the node comprises at least one value block, and wherein each individual value block of the node is assigned a data generation number indicating a sequence order at which the individual value block was initially generated for the key-value store tree data structure;
- 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
- in response to determining that the set of child nodes comprises the leaf node, move the sequence of key-value sets to the set of child nodes, the moving the sequence of key-value sets to the set of child nodes comprising:
- merging the sequence of key-value sets to produce a merged key-value set, the merged key-value set comprising a set of new key blocks that reference a set of new value blocks, and the set of new value blocks being assigned a particular largest data generation number assigned to any value block in a set of existing value blocks of the sequence of key-value sets.
5 more elements
Dependencies are inferred from the claim text.