Key-value store tree with selective use of key portion
Aspects of the present disclosure provide various embodiments for selective use of a portion of a key, such as a prefix of the key (also referred to as a key prefix of a key), with respect to a key-value store (KVS) tree data structure, such as when storing a key-value pair (associated with the key) within the KVS tree data structure or navigating through the KVS tree data structure. For some embodiments, when navigating a KVS tree based on a key, a first set of levels (e.g., a first series of levels) of the KVS tree is navigated by a first portion (e.g., a prefix) of the key, and a second set of levels (e.g., a second series of levels) of the KVS tree is navigated by a second portion (e.g., an entire portion) of the key.
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.
2. The system of claim 1 , wherein the first portion of the particular key comprises a prefix of the particular key.
3. The system of claim 2 , wherein the prefix of the particular key comprises a first N number of bytes of the particular key.
4. The system of claim 2 , wherein the second portion of the particular key comprises a second prefix of the particular key.
5. The system of claim 1 , wherein the second portion of the particular key comprises all of the particular key.
6. The system of claim 1 , wherein the first set of levels comprises a first series of levels of the key-value store tree data structure, the second set of levels comprises a second series of levels, and the first series of levels does not overlap with the second series of levels.
7. The system of claim 1 , wherein the searching the one or more child nodes of the first set of levels of the key-value store tree data structure based on the first portion of the particular key comprises:
navigating to a first child node of the first set of levels based on the first portion of the particular key;
searching the first child node for the particular key-value pair; and
in response to determining that the first child node does not comprise the particular key-value pair:
navigating from the first child node to a second child node of the first set of levels based on the first portion of the particular key; and
searching the second child node for the particular key-value pair.
8. The system of claim 1 , wherein the searching the one or more child nodes of the first set of levels of the key-value store tree data structure based on the first portion of the particular key comprises:
searching the one or more child nodes of the first set of levels of the key-value store tree data structure based on a hash of the first portion of the particular key.
9. The system of claim 8 , wherein the searching the one or more child nodes of the second set of levels of the key-value store tree data structure based on the second portion of the particular key comprises:
searching the one or more child nodes of the second set of levels of the key-value store tree data structure based on a hash of the second portion of the particular key.
10. The system of claim 1 , wherein the first portion of the particular key comprises a particular portion of the particular key offset from a start of the particular key.
11. 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 set of key-value pairs;
receiving a request to search the key-value store tree data structure for a particular key-value pair with 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.
12. The method of claim 11 , wherein the first portion of the particular key comprises a prefix of the particular key.
13. The method of claim 12 , wherein the prefix of the particular key comprises a first N number of bytes of the particular key.
14. The method of claim 12 , wherein the second portion of the particular key comprises a second prefix of the particular key.
15. The method of claim 11 , wherein the second portion of the particular key comprises all of the particular key.
16. The method of claim 11 , wherein the first set of levels comprises a first series of levels of the key-value store tree data structure, the second set of levels comprises a second series of levels, and the first series of levels does not overlap with the second series of levels.
17. The method of claim 11 , wherein the searching the one or more child nodes of the first set of levels of the key-value store tree data structure based on the first portion of the particular key comprises:
navigating to a first child node of the first set of levels based on the first portion of the particular key;
searching the first child node for the particular key-value pair; and
in response to determining that the first child node does not comprise the particular key-value pair:
navigating from the first child node to a second child node of the first set of levels based on the first portion of the particular key; and
searching the second child node for the particular key-value pair.
18. The method of claim 11 , wherein the searching the one or more child nodes of the first set of levels of the key-value store tree data structure based on the first portion of the particular key comprises:
searching the one or more child nodes of the first set of levels of the key-value store tree data structure based on a hash of the first portion of the particular key.
19. The method of claim 18 , wherein the searching the one or more child nodes of the second set of levels of the key-value store tree data structure based on the second portion of the particular key comprises:
searching the one or more child nodes of the second set of levels of the key-value store tree data structure based on a hash of the second portion of the particular key.
20. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to:
access, 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 set of key-value pairs;
receive a request to search the key-value store tree data structure for a particular key-value pair comprising a particular key;
in response to the request, search 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:
search 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.