Counter-based compaction of key-value store tree data block

  • US 10,915,546 B2
  • Filed: 10/10/2018
  • Issued: 02/09/2021
  • Est. Priority Date: 10/10/2018
  • Status: Active Grant
First Claim
Patent Images

1. 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.

View all claims
    ×
    ×

    Thank you for your feedback

    ×
    ×