Systems and methods of managing an index

Patent metadata

Field	Value
Publication number	US-11269956-B2
Application number	US-201916373124-A
Country	US
Kind code	B2
Filing date	Apr 2, 2019
Priority date	Feb 7, 2019
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

Abstract

Disclosed is a computer program stored in a computer readable storage medium according to an exemplary embodiment of the present disclosure. The computer program executes operations for enhancing search performance of data when the computer program is executed by one or more processors and the operations may include: setting a traverse time stamp of an index search for searching a target index key; searching the index tree along a link connected from a root node of the index tree to a leaf node; writing in a time stamp table at least one index time stamp of the root node and the leaf node passed in the index search; determining whether a path of the index search needs to be changed; and determining a start node of re-search at least partially based on the time stamp table.

First claim

What is claimed is:

1. A non-transitory computer-readable storage medium storing a computer program, wherein the computer program executes operations for enhancing search performance of data when the computer program is executed by one or more processors, the operations comprising:
setting a traverse time stamp of an index search for searching a target index key;
searching an index tree along a link connected from a root node of the index tree to a leaf node;
writing in a time stamp table at least one index time stamp of the root node, a branch node, and the leaf node read in the index search; and
determining whether to change a search path for the target index key based on the traverse time stamp and the index time stamp, wherein the determining of whether to change the search path for the target index key based on the traverse time stamp and the index time stamp includes:
determining whether to change the search path for the target index key based on contents of a search node when the traverse time stamp is smaller than the index time stamp of the search node, and
updating the traverse time stamp based on the index time stamp of a current search node when determining to maintain the search path for the target index key, wherein an updated traverse time stamp is issued so as to be equal to or larger than the index time stamp of the current search node.

2. The computer program of claim 1 , wherein the index time stamp is assigned for each node included in the index tree and generated based on information on a time when each node is modified.

3. The computer program of claim 1 , wherein the writing in the time stamp table of at least one index time stamp of the root node, the branch node, and the leaf node read in the index search, further comprises:
matching the index time stamp read in at least one of the root node, the branch node, and the leaf node with each node identifier and writing the matched index time stamp and node identifier in the time stamp table.

4. The computer program of claim 1 , wherein the writing in the time stamp table of at least one index time stamp of the root node, the branch node, and the leaf node read in the index search, further comprises:
writing in the time stamp table the index time stamp from a current search node up to a predetermined number of previous search nodes among search nodes read in the index search.

5. The computer program of claim 4 , wherein the writing in the time stamp table of at least one index time stamp of the root node, the branch node, and the leaf node read in the index search, further comprises:
deleting the one or more index time stamps written in the time stamp table based on a predetermined criterion.

6. The computer program of claim 1 , wherein the determining of whether to change the search path for the target index key based on the traverse time stamp and the index time stamp, further comprises:
determining to maintain the search path for the target index key when the traverse time stamp is equal to or larger than the index time stamp of the search node, and
determining to change the search path for the target index key when the traverse time stamp is smaller than the index time stamp of the search node.

7. The computer program of claim 1 , wherein the determining of whether to change the search path for the target index key based on contents of the search node when the traverse time stamp is smaller than the index time stamp of the search node, further comprises:
determining whether the search path for the target index key needs to be changed based on bound information including at least one information of a minimum value and a maximum value of an index key which may be included in the search node for the search node and the target index key.

8. The computer program of claim 7 , wherein the determining of whether the search path for the target index key needs to be changed based on the bound information including at least one information of the minimum value and the maximum value of the index key which may be included in the search node for the search node and the target index key, further comprises:
determining to maintain the search path for the target index key when a value of the target index key falls within the bound information, and
determining to change the search path for the target index key when the value of the target index key does not fall within the bound information.

9. The computer program of claim 1 , further comprising:
updating the traverse time stamp when determining to change the search path for the target index key.

10. The computer program of claim 9 , wherein the updating of the traverse time stamp, further comprises:
updating the traverse time stamp based on a time information when comparing the traverse time stamp and the index time stamp of the search node or updating the traverse time stamp based on a time information when an index search threads starts reading of a start node of re-search.

11. The computer program of claim 1 , further comprising:
determining a start node of re-search at least partially based on the time stamp table.

12. The computer program of claim 11 , wherein the determining of the start node of the re-search at least partially based on the time stamp table, further comprises:
determining whether each previous search node written in the time stamp table is changed after the search, and
determining as the start node of the re-search one of previous search nodes which are not changed after the search among the previous search nodes.

13. The computer program of claim 12 , wherein the determining of whether each previous search node written in the time stamp table is changed after the search, further comprises:
determining whether the previous search node is changed after the search by comparing each index time stamp of the previous search node written in the time stamp table and the index time stamp of each previous search node read at the time of the re-search.

14. The computer program of claim 12 , wherein the determining as the start node of the re-search of one of previous search nodes which are not changed after the search among the previous search nodes, further comprises:
determining as the start node of the re-search a nearest node of the current search node among the previous search nodes which are not changed after the search.

15. A method for enhancing search performance of data, the method comprising:
setting a traverse time stamp of an index search for searching a target index key;
searching an index tree along a link connected from a root node of the index tree to a leaf node;
writing in a time stamp table at least one index time stamp of the root node, a branch node, and the leaf node read in the index search; and
determining whether to change a search path for the target index key based on the traverse time stamp and the index time stamp, wherein the determining of whether to change the search path for the target index key based on the traverse time stamp and the index time stamp includes:
determining whether to change the search path for the target index key based on contents of a search node when the traverse time stamp is smaller than the index time stamp of the search node, and
updating the traverse time stamp based on the index time stamp of a current search node when determining to maintain the search path for the target index key, wherein an updated traverse time stamp is issued so as to be equal to or larger than the index time stamp of the current search node.

16. A computing device for enhancing search performance of data, t

Assignees

• Tmaxdata Co Ltd
• Tmaxdataco Ltd

Inventors

• Oh Jaemin
• Kim Taikyoung
• Cho Jaehyeong

Classifications

• G06F16/9027 Primary

  Trees · CPC title

• G06F16/2246 Primary

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

• G06F16/2322 Primary

  using timestamps · CPC title

• G06F16/90348

  by searching ordered data, e.g. alpha-numerically ordered data · CPC title