# US 2020/0004859 A1 · Method for managing index

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

- Number: US 2020/0004859 A1
- Document ID: US20200004859A1
- Status: Published application
- Kind: A1
- Application number: 16/021,531
- Filed: 2018-06-28
- Published: 2020-01-02
- Earliest claimed: 2018-06-27
- Assignees: TmaxData Co., Ltd.
- Applicants: TmaxData Co., Ltd.
- Inventors: Jaemin OH; Taikyoung KIM; Jaehyeong CHO
- Web page: https://patentgrep.com/patent/US20200004859A1

## CPC

- G06F 16/24542: {Plan optimisation}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

According to one exemplary embodiment of the present disclosure, disclosed is a computer program stored in a computer readable storage medium. The computer program causes operations for improving data retrieval performance to be performed when the computer program is executed by one or more processors of a computing device, and the operations include: an operation of initiating an index search for retrieving a target index key from a root node of an index tree; an operation of performing an index tree search to a child node along a link connected to the child node; and an operation of reading a currently searched node and determining whether to change an index search route.

## Claims

### Claim 1

A non-transitory computer readable storage medium including instructions that when executed by one or more processors perform a method for improving data retrieval performance method comprising:
initiating an index search for retrieving a target index key from a root node of an index tree;
performing an index tree search to a child node along a link connected to the child node;
reading a currently searched node: and
determining whether to change an index search route.

### Claim 2 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the performing the index tree search to the child node along the link connected to the child node includes:
performing the index search to a low-direction lower child node connected to a low-direction lower link when the target index key has a value smaller than a smallest value of a key among values of keys in the currently searched node;
performing the index search to a high-direction lower child node connected to a high-direction lower link when the target index key has a value larger than a largest value of a key among the values of the keys in the currently searched node, or
performing the index search to a center-direction lower child node connected to a center-direction lower link when the target index key has a value larger than the smallest value of the key among the values of the keys in the currently searched node and smaller than the largest value of the key among the values of the keys in the currently searched node, and has a value not included in the currently searched node.

### Claim 3 (depends on 2)

The non-transitory computer readable storage medium of claim 2, wherein the low-direction lower link is a link connected to a child node including a key having a value smaller than the smallest value of the key included in the currently searched node among the child nodes,
the high-direction lower link is a link connected to a child node including a key having a value larger than the largest value of the key included in the currently searched node among the child nodes, and
the center-direction lower link is a link connected to a child node including a key having a value, which is larger than the smallest value of the key and is smaller than the largest value of the key included in the currently searched node among the child nodes, and which is not included in the currently searched node.

### Claim 4 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the reading the currently searched node and the determining whether to change the index search route include
comparing an upper bound key and a lower bound key of the currently searched node with the target index key; and
determining whether the index search route needs to be changed.

### Claim 5 (depends on 4)

The non-transitory computer readable storage medium of claim 4, wherein the upper bound key is the largest value of the index key includable in the currently searched node, and the lower bound key is the smallest value of the index key includable in the currently searched node.

### Claim 6 (depends on 4)

The non-transitory computer readable storage medium of claim 4, wherein the comparing the upper bound key and the lower bound key of the currently searched node with the target index key and the determining whether the index search route needs to be changed includes at least one of:
determining to maintain the index search route when the target index key has a value smaller than the upper bound key; and
determining to maintain the index search route when the target index key has a value larger than the lower bound key.

### Claim 7 (depends on 1)

The non-transitory computer readable storage medium of claim 1, further comprising:
reading a parent node connected with the currently searched node through a link, and
determining to perform the index search from the parent node when it is determined that the index search route needs to be changed.

### Claim 8 (depends on 7)

The non-transitory computer readable storage medium of claim 7, wherein the reading the parent node connected with the currently searched node through the link and the determining to perform the index search from the parent node when it is determined that the index search route needs to be changed include:
comparing an upper bound key and a lower bound key of the parent node with the target index key; and
determining to perform the index search from the parent node.

### Claim 9

A method of improving data retrieval performance performed by one or more processors of a computing device, the method comprising:
initiating an index search for retrieving a target index key from a root node of an index tree;
performing an index tree search to a child node along a link connected to the child node; and
reading a currently searched node and determining whether to change an index search route.

### Claim 10

A computing device, comprising:
one or more processors; and
a memory configured to store commands executable by the one or more processors,
wherein the one or more processors are configured to:
initiate an index search for retrieving a target index key from a root node of an index tree;
perform an index tree search to a child node along a link connected to the child node; and
read a currently searched node and determines whether to change an index search route.
