Key-value store tree data block spill with compaction

  • US 11,100,071 B2
  • Filed: 10/10/2018
  • Issued: 08/24/2021
  • Est. Priority Date: 10/10/2018
  • Status: Active Grant
First Claim
Patent Images

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

View all claims
    ×
    ×

    Thank you for your feedback

    ×
    ×