# US 2021/0279225 A1 · Method and apparatus for controlling access to trie data structure

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

- Number: US 2021/0279225 A1
- Document ID: US20210279225A1
- Status: Published application
- Kind: A1
- Application number: 17/186,205
- Filed: 2021-02-26
- Published: 2021-09-09
- Earliest claimed: 2020-03-03
- Inventors: WunBae JEON
- Web page: https://patentgrep.com/patent/US20210279225A1

## CPC

- G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A technology for controlling an access of a trie by managing node access permissions of processes that access a trie data structure and perform an operation is disclosed. Example embodiments include accessing a window initiating node in a trie, determining whether a next node is an anchor node while visiting lower nodes of the window initiating node in a predetermined traversal order, locking the next node when the next node is an anchor node, releasing a lock of the window initiating node when the window initiating node is an anchor node, and setting the next node as the window initiating node.

## Claims

### Claim 1

A method for controlling an access to a trie data structure through an iteration operation that processes at least one window, the method comprising
accessing, by at least one process driven by a processor, a window initiating node in a trie; and
determining, by the process, whether a next node is an anchor node, while visiting lower nodes of the window initiating node in a predetermined traversal order,
wherein, when the next node is an anchor node, the method comprises
locking, by the process, the next node;
releasing, by the process, a lock of the window initiating node, when the window initiating node is an anchor node; and
setting, by the process, the next node as the window initiating node.

### Claim 2 (depends on 1)

The method of claim 1 further comprising
when a traversal of the lower nodes of the window initiating node is completed,
releasing, by the process, the lock of the window initiating node, when the window initiating node is an anchor node; and
setting, by the process, a lower boundary value for a next iteration operation so as to indicate a next node of a last node among the lower nodes in the trie, based on the traversal order.

### Claim 3 (depends on 1)

The method of claim 1, wherein the determining of whether the next node is the anchor node comprises
comparing, by the process, a threshold value to the number of child nodes of the next node; and
determining, by the process, whether the next node is the anchor node based on a result of the comparison.

### Claim 4 (depends on 1)

The method of claim 1, wherein
the accessing of the window initiating node comprises searching for, by the process, the window initiating node starting from a root node in the trie, based on a lower boundary value of a range traversed by the iteration operation, and
when the anchor node is found while searching for the window initiating node, the anchor node is locked and an upper lock is released.

### Claim 5 (depends on 1)

The method of claim 1, wherein the accessing of the window initiating node comprises locking, by the process, the window initiating node, when the window initiating node is a root node.

### Claim 6 (depends on 1)

The method of claim 1, wherein the locking of the next node comprises
requesting, by the process, the lock on the next node;
waiting, by the process, until the lock is acquired, after requesting the lock; and
acquiring, by the process, the lock, in response to the request.

### Claim 7 (depends on 3)

The method of claim 3, wherein the threshold is set differently for each next node.

### Claim 8 (depends on 1)

The method of claim 1, wherein the determining of whether the next node is the anchor node, in a crabbing mode in which a plurality of processes use different anchor node conditions, wherein each of the anchor node conditions comprises a threshold value compared to the number of child nodes so as to determine whether the next node is the anchor node, comprises
so as to visit the lower nodes in the predetermined traversal order,
locking, by the process, the next node;
releasing, by the process, a lock of a current node; and
accessing, by the process, the next node, and
in the crabbing mode, when the next node is an anchor node, the locking of the next node is not performed.

### Claim 9 (depends on 8)

The method of claim 8, wherein the releasing of the lock of the current node comprises
maintaining, by the process, the lock of the current node, when the current node is a anchor node; and
releasing, by the process, the lock of the current node regardless of whether the current node is an anchor node.

### Claim 10 (depends on 9)

The method of claim 9 further comprising
maintaining, by the process, when a parent node of the next node is an anchor node, a lock of the parent node; and
releasing, by the process, the lock of the parent node regardless of whether the parent node is an anchor node, when the next node is an anchor node.

### Claim 11 (depends on 1)

The method of claim 1 further comprising
receiving data to be updated in the trie;
accessing, by the process, a node corresponding to the data to be updated in the trie by searching the trie using an exclusive lock; and
updating, by the process, the node,
wherein, when an anchor node is found while searching for the node corresponding to the data to be updated, the exclusive lock is placed on the anchor node and an upper exclusive lock is released.

### Claim 12 (depends on 1)

The method of claim 1, wherein the predetermined traversal order includes an order based on a depth first search (DFS) method.

### Claim 13

A method for controlling an access to a trie data structure through an iteration operation, the method comprising
determining, by at least one process driven by a processor, an area type to which a next node belongs among a plurality of area types predetermined for the iteration operation;
requesting, by the process, a lock on the next node;
accessing, by the process, the next node, in response to acquiring the lock;
performing, by the process, a leaf check of the next node depending on the area type; and
performing, by the process, a lower edge scan of the next node, based on a scan range depending on the area type,
wherein, when the next node is an anchor node, an upper lock is released while the lock is maintained, and when the next node is not an anchor node, the lock is released while the upper lock is maintained.

### Claim 14 (depends on 13)

The method of claim 13, wherein the area type comprises at least one of:
an R type corresponding to a root node;
an L type corresponding to a node indicating a lower boundary value;
a U type corresponding to a node indicating an upper boundary value;
an O type corresponding to a node exceeding the upper boundary value;
a C type corresponding to a common node of the lower boundary value and the upper boundary value; and
an N type corresponding to a node between the lower boundary value and the upper boundary value.

### Claim 15 (depends on 13)

The method of claim 13, wherein the performing of the leaf check comprises skipping, by the process, a check of whether the next node is a leaf node that stores data, when the area type corresponds to one of an R type, an intermediate level of an L type, a final level of the L type when performing an iteration operation without an equal sign in a lower boundary value condition, a final level of a U type when performing the iteration operation without the equal sign in an upper boundary value condition, and an intermediate level of a C type.

### Claim 16 (depends on 13)

The method of claim 13, wherein, when the next node is an anchor node, the performing of the lower edge scan of the next node comprises marking, by the process, a lower edge being visited, so as to set a lower boundary value of a next iteration operation.

### Claim 17 (depends on 13)

The method of claim 13, the performing of the lower node scan comprises
visiting, by the process, a node connected to a lower edge within the scan range;
visiting, by the process, a node of a next lower edge within the scan range, when a visit to the node connected to the lower edge is completed and returned; and
releasing the upper lock and setting a lower boundary value for a next iteration operation based on edge marking information, when there is no scannable lower edge within the scan range.

### Claim 18 (depends on 13)

The method of claim 13, wherein
when the iteration operation corresponds to a write operation,
the scan range depending on the area type indicates at least one node for the write operation, and
the performing of the lower edge scan comprises
visiting, by the process, when there is a lower edge corresponding to the scan range, a node of the lower edge to set the node as a leaf node; and
creating, by the process, when there is no lower edge corresponding to the scan range, a node of the lower edge to set the node as a leaf node.

### Claim 19 (depends on 13)

The method of claim 13, wherein
when the iteration operation corresponds to a delete operation,
the scan range depending on the area type indicates at least one node for the delete operation, and
the performing of the lower edge scan comprises
visiting, by the process, when there is a lower edge corresponding to the scan range, a node of the lower edge to release a leaf node of the node;
performing, by the process, a garbage collection of the node; and
setting, by the process, a lower boundary value of a next iteration operation based on one of a lower boundary value of the iteration operation or a last lower edge without visiting a node of the last lower edge, when the next node is an anchor node.

### Claim 20 (depends on 1)

A non-transitory computer-readable medium storing computer-readable instruction that, when executed by a processor, cause the processor to perform the method of claim 1.
