Back to results
US 10,915,546 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, and each key-value set in the sequence of key-value sets is associated with an individual count value;
- and
- a processing device, operatively coupled to the set of memory components, configured to perform operations comprising:
- accessing, on the set of memory components, the key-value store tree data structure;
- detecting whether the sequence of key-value sets comprises a first sub-sequence of key-value sets comprising a predetermined number of key-value sets where each key-value set is associated with a similar count value;
- and
- in response to detecting that the sequence of key-value sets comprises the first sub-sequence of key-value sets:
- 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.
8 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, and each key-value set in the sequence of key-value sets is associated with an individual count value;
- detecting, by a processing device, whether the sequence of key-value sets comprises a sub-sequence of key-value sets comprising a predetermined number of key-value sets where each key-value set is associated with a similar count value;
- and
- in response to detecting that the sequence of key-value sets comprises the sub-sequence of key-value sets:
- merging, by the processing device, the 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 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.
5 more elements
A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to:
- generate, on a set of memory components, an index data structure comprising an index to store a sequence of sub-indexes, each sub-index in the sequence storing a set of key-value pairs;
- update the index by appending a new sub-index to the sequence of sub-indexes, the new sub-index comprising a new set of key-value-pairs;
- associate the new sub-index with an initial count value;
- detecting whether the sequence of sub-indexes comprises a sub-sequence of sub-indexes comprising a predetermined number of sub-indexes where each sub-index is associated with a similar count value;
- in response to detecting that the sequence of sub-indexes comprises the sub-sequence of sub-indexes:
- merging the 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 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.
6 more elements
Dependencies are inferred from the claim text.