KEY-VALUE STORE TREE WITH SELECTIVE USE OF KEY PORTION

• US 20200192940A1
• Filed: 12/14/2018
• Published: 06/18/2020
• Est. Priority Date: 12/14/2018
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Tomlinson, Alexander
• Granted Patent: US 11,048,755 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data

Abstract

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.

Claims

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 associated with 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 associated with 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 key, for a child node that comprises the particular key-value pair, the searching 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; 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 key, the second portion being different from the first portion.

2. The system of claim 1, wherein the first portion of the particular key comprises a prefix of the key.

3. The system of claim 2, wherein prefix of the particular key comprises a first N number of bytes of the key.

4. The system of claim 2, wherein the second portion f the particular key comprises a second prefix of the key.

5. The system of claim 1, wherein the second p n of the particular key comprise an entire portion of the 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 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 associated with 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 associated with 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 key, for a child node that comprises the particular key-value pair, the searching 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; and

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 key, the second portion being different from the first portion.

12. The method of claim 11, wherein the first portion of the particular key comprises a prefix of the key.

13. The method of claim 12, wherein the prefix of the particular key comprises a first N number of bytes of the key.

14. The method of claim 12, wherein the second portion of the particular key comprises a second prefix of the key.

15. The method of claim 11, wherein the second portion of the particular key comprises an entire portion of the 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 associated with 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 associated with 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 key, for a child node that comprises the particular key-value pair, the searching 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; 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.