Method and apparatus for searching node by using tree index

Patent metadata

Field	Value
Publication number	US-9697243-B2
Application number	US-201414260190-A
Country	US
Kind code	B2
Filing date	Apr 23, 2014
Priority date	Feb 10, 2014
Publication date	Jul 4, 2017
Grant date	Jul 4, 2017

Abstract

A node search method, comprising: setting a current time value as a traversing time value; searching descendent nodes to perform a traversing from a root node to a leaf node according to a tree index data structure; determining whether a preset traversing condition is satisfied by comparing an update time value, which indicates a time when a change to a searched descendent node is made, with the traversing time value; depending on whether the traversing proceeding condition is satisfied, re-performing a traversing from a parent node or continuing traversing to the searched descendent node; and terminating the traversing at a leaf node where no descendent node exists.

First claim

What is claimed is:

1. A node searching method based on a query performed by a processor, the method comprising:
setting a current time value as a traversing time value;
searching, based on the query, descendent nodes of a root node to perform a traversing from the root node to at least one leaf node among the descendent nodes according to a tree index data structure for organizing data in a database system;
determining at a currently-being-investigated node whether a preset traversing condition is satisfied by comparing an update time value of the currently-being-investigated node among the descendent nodes, which indicates a time when a change to the currently-being-investigated node is made, with the traversing time value;
traversing to a descendent node of the currently-being-investigated node when the preset traversing condition is satisfied; and
terminating the traversing from the root node to the at least one leaf node at the at least one leaf node where no descendent node exists,
wherein if the update time value of the currently-being-investigated node is later than the traversing time value, the preset traversing condition is not satisfied and a re-traversing from at least one parent node is performed, the at least one parent node being at least one level higher than the currently-being-investigated node in view of hierarch in the tree index data structure, and
wherein the re-traversing from the at least one parent node is performed and traverses back to the currently-being-investigated node, a preset traversing condition of the re-traversed currently-being-investigated node is satisfied without comparing an update time value with a traversing time value at the re-traversed currently-being-investigated node.

2. The node searching method of claim 1 ,
wherein when the re-traversing from the at least one parent node is started, the traversing time value is reset as time when the re-traversing is started.

3. A node searching apparatus having a processor, comprising:
a time setting unit configured to set a current time value as a traversing time value;
a node searching unit configured to search, based on a query, descendent nodes of a root node to perform a traversing from the root node to at least one leaf node among the descendent nodes according to a tree index data structure for organizing data in a database s system;
a traversing condition determining unit configured to determine at a currently-being-investigated node whether a preset traversing condition is satisfied by comparing an update time value of the currently-being-investigated node, which indicates a time when a change to the currently-being-investigated node is made, with the traversing time value; and
a traversing unit configured to, when the preset traversing condition is satisfied, traverse to a descendent node of the currently-being-investigated node, and terminate the traversing from the root node to the at least one leaf node at the at least one leaf node where no descendent node exists,
wherein if the update time value of the currently-being-investigated node is later than the traversing time value, the preset traversing condition is not satisfied and a re-traversing from at least one parent node is performed, the at least one parent node being at least one level higher than the currently-being-investigated node in view of hierarchy in the tree index data structure, and
wherein the re-traversing from the at least one parent node is performed and traverses back to the currently-being-investigated node, a preset traversing condition of the re-traversed currently-being-investigated node is satisfied without comparing an update time value with a traversing time value at the re-traversed currently-being-investigated node.

4. The node searching apparatus of claim 3 ,
wherein when the re-traversing from the at least one parent node is started, the traversing time value is reset as time when the re-traversing is started.

5. A non-transitory computer-readable medium for searching a node based on a query for performing a process to be executed on a computer, the process comprising:
setting, by a time setting unit, a current time value as a traversing time value;
searching, based on the query, by a node searching unit, descendent nodes of a root node to perform a traversing from the root node to at least one leaf node among the descendent nodes according to a tree index data structure for organizing data in a database system;
determining, by a traversing condition determining unit, at a currently-being-investigated node whether a preset traversing condition is satisfied by comparing an update time value of the currently-being-investigated node, which indicates a time when a change to the currently-being-investigated node is made, with the traversing time value; and
traversing, by a traversing unit, when the preset traversing condition is satisfied, to a descendent node of the currently-being-investigated node, and terminating the traversing from the root node to the at least one leaf node at the at least one leaf node where no descendent node exists,
wherein if the update time value of the currently-being-investigated node is later than the traversing time value, the preset traversing condition is not satisfied and a re-traversing from at least one parent node is performed, the at least one parent node being at least one level higher than the currently-being-investigated node in view of hierarchy in the tree index data structure, and
wherein the re-traversing from the at least one parent node is performed and traverses back to the currently-being-investigated node, a preset traversing condition of the re-traversed currently-being-investigated node is satisfied without comparing an update time value with a traversing time value at the re-traversed currently-being-investigated node.

6. The non-transitory computer-readable medium of claim 5 ,
wherein when the re-traversing from the at least one parent node is started, the traversing time value is reset as time when the re-traversing is started.

Assignees

• Tibero Co Ltd
• Tmaxdata Co Ltd

Inventors

• Kang Ingyu
• Park Sangyoung
• An Jae Seok
• Kim Jooho

Classifications

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F40/14 Primary

  Tree-structured documents (parsing G06F40/205; validation G06F40/226) · CPC title

• G06F16/2477

  Temporal data queries · CPC title

• G06F17/30551

  Physics · mapped topic

• G06F17/30327 Primary

  Physics · mapped topic