# US 2026/0169915 A1 · Storage system and operating method of mapping conversion based on average length of extents allocated to mapping tree

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

- Number: US 2026/0169915 A1
- Document ID: US20260169915A1
- Status: Published application
- Kind: A1
- Application number: 19/529,711
- Filed: 2026-02-04
- Published: 2026-06-18
- Earliest claimed: 2024-01-29
- Assignees: Samsung Electrics Co., Ltd.
- Applicants: Samsung Electrics Co., Ltd.
- Inventors: Joo Young HWANG
- Web page: https://patentgrep.com/patent/US20260169915A1

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 3/0638: {Organizing or formatting or addressing of data}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 2212/651: Multi-level translation tables
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for operating a storage system including a storage includes calculating an average length of extents allocated to a logical address region corresponding to a particular node of an address mapping tree, the address mapping tree being associated with the storage, and a mapping information format of the particular node being a first format and, based on the average length, converting the mapping information format of the particular node from the first format to a second format.

## Claims

### Claim 1

A storage system comprising:
one or more processors; and
a storage implemented as a non-volatile memory,
wherein the one or more processors are configured to:
for a particular node of an address mapping tree associated with the storage, determine (i) a size of a logical address region corresponding to the particular node and (ii) a number of extents allocated to the logical address region; and
based on a value derived from the size of the logical address region and the number of extents, perform a format conversion that converts a mapping information format of the particular node between an extent-based format and a page-based format.

### Claim 2 (depends on 1)

The storage system of claim 1,
wherein determining the number of extents comprises counting a number of page sets each comprising consecutive valid pages by using bitmap information of the particular node.

### Claim 3 (depends on 1)

The storage system of claim 1,
wherein performing the format conversion comprises comparing the value derived from the size of the logical address region and the number of extents with a threshold,
and wherein the threshold is determined based on an entry size of the extent-based format and an entry size of the page-based format.

### Claim 4 (depends on 1)

The storage system of claim 1,
wherein, in response to a number of entries of the particular node being a maximum number and a new extent entry being inserted into the particular node, splitting for the particular node is deferred and the format conversion is performed.

### Claim 5 (depends on 1)

The storage system of claim 1,
wherein the address mapping tree is a B+ tree and the particular node is a leaf node of the address mapping tree.

### Claim 6 (depends on 1)

The storage system of claim 1,
wherein determining the size of the logical address region comprises determining the size based on a difference between first logical address information of a first entry of the particular node and second logical address information of a first entry of a sibling node of the particular node.

### Claim 7 (depends on 1)

The storage system of claim 1,
wherein the particular node is a node of the page-based format, and wherein determining the number of extents comprises determining the number of extents according to a number of entries included in the particular node.

### Claim 8 (depends on 1)

The storage system of claim 1,
wherein a threshold of the value is adjusted based on a request processing performance associated with a storage client.

### Claim 9 (depends on 1)

The storage system of claim 1, further comprising a volatile memory,
wherein the format conversion is performed while mapping information of the particular node is being loaded from the storage into the volatile memory, or while the mapping information of the particular node is being evicted from the volatile memory to the storage.

### Claim 10

A method for operating a storage system including a storage implemented as a non-volatile memory, the method comprising:
for a particular node of an address mapping tree associated with the storage, determining (i) a size of a logical address region corresponding to the particular node and (ii) a number of extents allocated to the logical address region; and
based on a value derived from the size of the logical address region and the number of extents, performing a format conversion that converts a mapping information format of the particular node between an extent-based format and a page-based format.

### Claim 11 (depends on 10)

The method of claim 10,
wherein determining the number of extents comprises counting a number of page sets each comprising consecutive valid pages by using bitmap information of the particular node.

### Claim 12 (depends on 10)

The method of claim 10,
wherein performing the format conversion comprises comparing the value derived from the size of the logical address region and the number of extents with a threshold,
and wherein the threshold is determined based on an entry size of the extent-based format and an entry size of the page-based format.

### Claim 13 (depends on 10)

The method of claim 10,
wherein, in response to a number of entries of the particular node being a maximum number and a new extent entry being inserted into the particular node, splitting for the particular node is deferred and the format conversion is performed.

### Claim 14 (depends on 10)

The method of claim 10,
wherein the address mapping tree is a B+ tree and the particular node is a leaf node of the address mapping tree.

### Claim 15 (depends on 10)

The method of claim 10,
wherein determining the size of the logical address region comprises determining the size based on a difference between first logical address information of a first entry of the particular node and second logical address information of a first entry of a sibling node of the particular node.

### Claim 16 (depends on 10)

The method of claim 10,
wherein the particular node is a node of the page-based format, and wherein determining the number of extents comprises determining the number of extents according to a number of entries included in the particular node.

### Claim 17 (depends on 10)

The method of claim 10,
wherein a threshold of the value is adjusted based on request processing performance associated with a storage client.

### Claim 18 (depends on 10)

The method of claim 10,
wherein the format conversion is performed while mapping information of the particular node is being loaded from the storage into a volatile memory, or while the mapping information of the particular node is being evicted from the volatile memory to the storage.

### Claim 19 (depends on 10)

The method of claim 10, further comprising, during or prior to the format conversion:
receiving a write request from a storage client, a logical address region of the write request including a first region associated with a first node of the address mapping tree;
removing an entry of an extent having a region that overlaps the first region, among entries included in the first node; and
inserting a new entry including address mapping information of the first region into the first node.

### Claim 20 (depends on 10)

The method of claim 10,
wherein the storage does not support in-place update, and
wherein, when mapping information of a first node included in the address mapping tree is updated, the method further comprises:
generating a second node including the mapping information that has been updated;
generating a new ancestor node of the second node corresponding to an ancestor node of the first node; and
persisting mapping information of the second node and mapping information of the new ancestor node in the storage.
