Key-value store tree with selective use of key portion

  • US 11,048,755 B2
  • Filed: 12/14/2018
  • Issued: 06/29/2021
  • Est. Priority Date: 12/14/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 set of key-value pairs; and

    a processing device, operatively coupled to the set of memory components, configured to perform operations comprising;

    receiving a request to search the key-value store tree data structure for a particular key-value pair comprising a particular key;

    in response to receiving the request, searching a root node of the key-value store tree data structure for the particular key-value pair comprising the particular key; and

    in response to determining that the root node does not comprise the particular key-value pair, searching the key-value store tree data structure, based on the particular key, for a child node that comprises the particular key-value pair, the searching the key-value store tree data structure comprising;

    searching one or more child nodes of a first set of levels of the key-value store tree data structure based on a first portion of the particular key, the first portion being less than all of the particular key; and

    in response to determining that at least one child node of the first set of levels of the key-value store tree data structure does not comprise the particular key-value pair, searching one or more child nodes of a second set of levels of the key-value store tree data structure based on a second portion of the particular key, the second portion being different from the first portion, and the second portion overlapping at least partially with the first portion.

View all claims
    ×
    ×

    Thank you for your feedback

    ×
    ×