# US 2021/0133208 A1 · Counter-based compaction of key-value store tree data block

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0133208 A1
- Document ID: US20210133208A1
- Status: Published application
- Kind: A1
- Application number: 17/146,222
- Filed: 2021-01-11
- Published: 2021-05-06
- Earliest claimed: 2018-10-10
- Assignees: Micron Technology, Inc.
- Applicants: Micron Technology, Inc.
- Inventors: Alexander Tomlinson
- Web page: https://patentgrep.com/patent/US20210133208A1

## CPC

- G06F 16/258: {Data format conversion from or to a database}
- G06F 7/14: Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 2207/222: Binary data tree
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Aspects of the present disclosure provide for operations of a key-value tree data structure that merges key-value pair data of a node, in a key-value tree data structure using counter values.

## Claims

### Claim 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 sequence of key value sets, each key-value set in the sequence of key-value sets is associated with an individual count value, and the sequence of key-value sets comprising a first sub-sequence of key-value sets that comprises a predetermined number of key-value sets where each key-value set is associated with a similar count value; and
a processing device, operatively coupled to the set of memory components, configured to perform operations comprising:
merging the first sub-sequence of key-value sets to produce a merged key-value set;
associating the merged key-value set with a first new count value, the first new count value being generated based on the similar count value; and
replacing the first sub-sequence of key-value sets, within the sequence of key-value sets, with the merged key-value set to produce an updated sequence of key-value sets.

### Claim 2 (depends on 1)

The system of claim 1, wherein generating the first new count value based on the similar count value comprises setting the first new count value to be equal to the similar count value incremented by a specific value.

### Claim 3 (depends on 2)

The system of claim 2 , erein the specific value comprises a value of one.

### Claim 4 (depends on 1)

The system of claim 1, wherein the merged key-value set comprises a set of new key blocks that reference a set of existing value blocks of the first sub-sequence of key-value sets, and the set of new key blocks is generated based o a set of existing key blocks of the first sub-sequence of key-value sets.

### Claim 5 (depends on 4)

The system of claim 4, wherein the set of new key blocks is generated based on the set of existing key blocks of the first sub-sequence of key-value sets by copying values of the set of existing key blocks to the set of new key blocks such that the set of new key blocks comprising one or more references to the set of existing value blocks.

### Claim 6 (depends on 1)

The system of claim 1, wherein the merge key-value set comprises a set of new value blocks and a set of new key blocks that reference the set of new value blocks, the set of new value blocks is generated based on a set of existing value blocks of the first sub-sequence of key-value sets, and the set of new key blocks is generated based on a set of existing key blocks of the sequence of key-value sets.

### Claim 7 (depends on 6)

The system of claim 6, wherein the set of new value blocks is generated based on the set of value key blocks of the first sub-sequence of key-value sets by copying values of the set of existing value blocks to the set of new value blocks, and the set of new key blocks is generated based on the set of existing key blocks of the first sub-sequence of key-value sets by copying values of the set of existing key blocks to the set of new key blocks.

### Claim 8 (depends on 1)

The system of claim 1, wherein the replacing the first sub-sequence of key-value sets, in the sequence of key-value sets, with the merged key-value set to produce the updated sequence of key-value sets comprises:
deleting, from the node, each particular key-value set in the first sub-sequence of key-value sets.

### Claim 9 (depends on 1)

The system of claim 1, wherein the replacing the first sub-sequence of key-value sets, in the sequence of key-value sets, with the merged key-value set to produce the updated sequence of key-value sets comprises:
deleting one or more key blocks of each particular key-value set in the first sub-sequence of key-value sets.

### Claim 10 (depends on 1)

The system of claim 1, wherein the replacing the first sub-sequence of key-value sets, in the sequence of key-value sets, with the merged key-value set to produce the updated sequence of key-value sets comprises:
deleting one or more value blocks of each particular key-value set in the first sub-sequence of key-value sets.

### Claim 11 (depends on 1)

The system of claim 1, wherein the operations further comprise:
merging a second sub-sequence of key-value sets, in the updated sequence of key-value sets, to produce a second merged key-value set;
associating the second merged key-value set with a second new count value, the second new count value being generated based on a second similar count value; and
replacing the second sub-sequence of key-value sets, within the updated sequence of key-value sets, with the merged key-value set to produce a second updated sequence of key-value sets.

### Claim 12 (depends on 1)

The system of claim 1, wherein the first sub-sequence of key-value sets comprises one or more key-value sets within the node.

### Claim 13 (depends on 1)

The system of claim 1, wherein the key-value store tree data structure implements an index data structure, the sequence of key value sets comprises a sequence of sub-indexes, each key-value set comprising a sub-index, the operations further comprising:
updating the index data structure by appending a new sub-index to the sequence of sub-indexes, the new sub-index comprising a new set of key-value sets; and
associating the new sub-index with an initial count value.

### Claim 14

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 sequence of key value sets, each key-value set in the sequence of key-value sets is associated with an individual count value, and the sequence of key-value sets comprising a first sub-sequence of key-value sets that comprises a predetermined number of key-value sets where each key-value set is associated with a similar count value;
merging, by a processing device, the first sub-sequence of key-value sets to produce a merged key-value set;
associating, by the processing device, the merged key-value set with a first new count value, the first new count value being generated based on the similar count value; and
replacing, by the processing device, the first sub-sequence of key-value sets, within the sequence of key-value sets, with the merged key-value set to produce an updated sequence of key-value sets.

### Claim 15 (depends on 14)

The method of claim 14, wherein generating the first new count value based on the similar count value comprises setting the first new count value to be equal to the similar count value incremented by a specific value.

### Claim 16 (depends on 15)

The method of claim 15, wherein the specific value comprises a value of one.

### Claim 17 (depends on 14)

The method of claim 14, wherein the first sub-sequence of the key-value sets comprises a last key-value set in the sequence of key-value sets.

### Claim 18 (depends on 14)

The method of claim 14, further comprising:
updating the node by appending a new key-value set to the sequence of the key-value sets; and
associating the new key-value set with an initial count value.

### Claim 19 (depends on 14)

The method of claim 14, further comprising:
detecting whether an update to the node results in a new key-value set being appended to the sequence of key-value sets; and
in response to detecting the update to the node, associating the new key-value set with an initial count value.

### Claim 20

A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to perform operations 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 sequence of key value sets, each key-value set in the sequence of key-value sets is associated with an individual count value, and the sequence of key-value sets comprising a first sub-sequence of key-value sets that comprises a predetermined number of key-value sets where each key-value set is associated with a similar count value;
merging the first sub-sequence of sub-indexes to produce a merged sub-index;
associating the merged sub-index with a first new count value, the first new count value being generated based on the similar count value; and
replacing the first sub-sequence of sub-indexes, within the sequence of sub-indexes, with the merged sub-index set to produce an updated sequence of sub-indexes.
