Back to results
US 11,599,552 B2Granted
Counter-based compaction of key-value store tree data block
AssigneeMicron Technology, Inc.
InventorAlexander Tomlinson
Life of this patent
Estimating the term…
Abstract
Aspects of the present disclosure provide for operations of a key-value tree data structure that merges key-value pair data of a node, in a key-value tree data structure using counter values.
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, each key-value set in the sequence of key-value sets is associated with an individual count value, and the sequence of key-value sets comprising a first sub-sequence of key-value sets that comprises a predetermined number of key-value sets where each key-value set is associated with a similar count value;
- and
- a processing device, operatively coupled to the set of memory components, configured to perform operations comprising:
- merging the first sub-sequence of key-value sets to produce a merged key-value set;
- associating the merged key-value set with a first new count value, the first new count value being generated based on the similar count value;
- and
- replacing the first sub-sequence of key-value sets, within the sequence of key-value sets, with the merged key-value set to produce an updated sequence of key-value sets.
4 more elements
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, each key-value set in the sequence of key-value sets is associated with an individual count value, and the sequence of key-value sets comprising a first sub-sequence of key-value sets that comprises a predetermined number of key-value sets where each key-value set is associated with a similar count value;
- merging, by a processing device, the first sub-sequence of key-value sets to produce a merged key-value set;
- associating, by the processing device, the merged key-value set with a first new count value, the first new count value being generated based on the similar count value;
- and
- replacing, by the processing device, the first sub-sequence of key-value sets, within the sequence of key-value sets, with the merged key-value set to produce an updated sequence of key-value sets.
2 more elements
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, 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, each key-value set in the sequence of key-value sets is associated with an individual count value, and the sequence of key-value sets comprising a first sub-sequence of key-value sets that comprises a predetermined number of key-value sets where each key-value set is associated with a similar count value;
- merging the first sub-sequence of sub-indexes to produce a merged sub-index;
- associating the merged sub-index with a first new count value, the first new count value being generated based on the similar count value;
- and
- replacing the first sub-sequence of sub-indexes, within the sequence of sub-indexes, with the merged sub-index set to produce an updated sequence of sub-indexes.
2 more elements
Dependencies are inferred from the claim text.