ASSOCIATING KEY-VALUE PAIR SETS WITH LEAF NODES
In some implementations, a memory device may identify a key-value pair set associated with a root node, wherein the key-value pair set includes a plurality of key-value pairs, and wherein the root node is associated with a log-structured merge-tree. The memory device may determine that a plurality of keys in the key-value pair set are associated with a leaf node based on the plurality of keys corresponding to an edge key associated with the leaf node, wherein the leaf node is associated with the log-structured merge-tree. The memory device may associate the key-value pair set with the leaf node based on a metadata update of the key-value pair set, wherein the key-value pair set becomes decoupled from the root node.
1 . A memory device, comprising:
one or more components configured to:
identify a plurality of key-value pair sets stored in a memory of the memory device and associated with a root node;
determine that a plurality of keys in a first key-value pair set, of the plurality of key-value pair sets, are associated with a leaf node in a plurality of leaf nodes based on an edge key associated with the leaf node;
associate the first key-value pair set with the leaf node based on a renaming of the first key-value pair set, wherein the first key-value pair set becomes decoupled from the root node;
determine that different keys in a second key-value pair set, of the plurality of key-value pair sets, are associated with different leaf nodes in the plurality of leaf nodes based on different edge keys associated with the different leaf nodes; and
create new key-value pair sets in the different leaf nodes based on the different keys in the second key-value pair set, wherein the new key-value pair sets are created based on reading the second key-value pair set and writing portions of the second key-value pair set to the different leaf nodes.
2 . The memory device of claim 1 , wherein the renaming of the first key-value pair set involves updating metadata associated with the first key-value pair set.
3 . The memory device of claim 2 , wherein updating the metadata causes the first key-value pair set to be associated with the leaf node and to no longer be associated with the root node.
4 . The memory device of claim 2 , wherein updating the metadata involves a near-zero read amplification and a near-zero write amplification.
5 . The memory device of claim 1 , wherein all keys in the first key-value pair set are associated with a same leaf node in the plurality of leaf nodes.
6 . The memory device of claim 1 , wherein a beginning key in the first key-value pair set and an end key in the first key-value pair set are both associated with the leaf node, and wherein the root node is associated with newer data than data associated with the plurality of leaf nodes.
7 . The memory device of claim 1 , wherein the root node and the plurality of leaf nodes are associated with non-volatile memory storage.
8 . The memory device of claim 1 , wherein the root node and the plurality of leaf nodes are associated with a log-structured merge-tree.
9 . A method, comprising:
identifying a first key-value pair set stored in a memory of a memory device and associated with a root node, wherein the first key-value pair set includes a plurality of key-value pairs, and wherein the root node is associated with a log-structured merge-tree;
determining that a plurality of keys in the first key-value pair set are associated with a leaf node based on the plurality of keys corresponding to an edge key associated with the leaf node, wherein the leaf node is associated with the log-structured merge-tree, wherein the plurality of keys in the first key-value pair set are ordered by age, and wherein a beginning key in the first key-value pair set and an end key in the first key-value pair set are both associated with the leaf node; and
associating the key-value pair set with the leaf node based on a metadata update of the first key-value pair set without copying the key-value pair set between different memory locations of the memory, wherein the first key-value pair set becomes decoupled from the root node;
determining that different keys in a second key-value pair set are associated with different leaf nodes based on the different keys corresponding to different edge keys associated with the different leaf nodes; and
creating new key-value pair sets in the different leaf nodes based on the different keys in the second key-value pair set, wherein the new key-value pair sets are created based on reading the second key-value pair set and writing portions of the second key-value pair set to the different leaf nodes.
10 . The method of claim 9 , wherein the plurality of keys in the first key-value pair set that are associated with the leaf node are all keys in the first key-value pair set.
11 . The method of claim 9 , wherein the leaf node is a single leaf node from a plurality of leaf nodes associated with the log-structured merge-tree.
12 . The method of claim 9 , wherein the metadata update of the first key-value pair set involves a near-zero read amplification and a near-zero write amplification.
13 . The method of claim 9 , wherein the log-structured merge-tree is a two-level tree, and wherein the root node is associated with newer data than data associated with the leaf node.
14 . A system, comprising:
memory; and
a controller configured to:
determine that a size of data in the memory satisfies a first threshold;
write, to the memory, the data as a key-value pair set in a root node, wherein the root node is associated with a log-structured merge-tree;
determine that a plurality of key-value pair sets in the root node satisfy a second threshold;
determine, for each key-value pair set in the plurality of key-value pair sets, whether the key-value pair set satisfies a condition; and
perform a first action or a second action involving the key-value pair set and one or more leaf nodes depending on whether the key-value pair set stored in the memory satisfies the condition, wherein the one or more leaf nodes are associated with the log-structured merge-tree,
wherein the controller, when performing the first action, is configured to:
associate the key-value pair set with a leaf node of the one or more leaf nodes based on a metadata update of the key-value pair set without copying the key-value pair set between different memory locations of the memory, wherein the metadata update of the key-value pair set excludes reading the key-value pair set from the root node and writing the key-value pair set to the leaf node, and
wherein the controller, when performing the second action, is configured to:
determine that different keys in the key-value pair set are associated with different leaf nodes based on the different keys corresponding to different edge keys associated with the different leaf nodes; and
create new key-value pair sets in the different leaf nodes based on the different keys in the key-value pair set, wherein the new key-value pair sets are created based on reading the key-value pair set and writing portions of the key-value pair set to the different leaf nodes.
15 . The system of claim 14 , wherein the controller, when performing the first action, is configured to:
determine that a plurality of keys in the key-value pair set are associated with the leaf node based on the plurality of keys corresponding to an edge key associated with the leaf node.
16 . The system of claim 14 , wherein a first subset of the plurality of key-value pair sets is associated with the first action, and wherein a second subset of the plurality of key-value pair sets is associated with the second action.
17 . The system of claim 14 , wherein the memory is non-volatile memory storage.
18 . The system of claim 17 , wherein the root node and the one or more leaf nodes are associated with the non-volatile memory storage.
19 . The system of claim 14 , wherein the metadata update causes the key-value pair set to be associated with the leaf node and to no longer be associated with the root node.
20 . The system of claim 14 , wherein the metadata update involves a near-zero read amplification and a near-zero write amplification.