Method for managing index
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.
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, 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;
reading a currently searched node;
comparing an upper bound key and a lower bound key of the currently searched node with the target index key, wherein at least one of the upper bound key or the lower bound key of each node, which corresponds to an index structure change, is updated; and
determining whether the index search route needs to be changed;
wherein when the index structure is changed during the index search process, the index structure change is detected based on the upper bound key and the lower bound key, and
when the structure of the index tree is changed during the index search process and the change of the index search route is determined, the index search is retried from a close node based on the upper bound key and the lower bound key.
2. 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.
3. 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.
4. The non-transitory computer readable storage medium of claim 1 , 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.
5. The non-transitory computer readable storage medium of claim 1 , wherein 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.
6. 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, or higher node of the parent node when it is determined that the index search route needs to be changed.
7. The non-transitory computer readable storage medium of claim 6 , 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.
8. 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;
reading a currently searched node;
comparing an upper bound key and a lower bound key of the currently searched node with the target index key, wherein at least one of the upper bound key or the lower bound key of each node, which corresponds to an index structure change, is updated; and
determining whether the index search route needs to be changed;
wherein when the index structure is changed during the index search process, the index structure change is detected based on the upper bound key and the lower bound key, and
when the structure of the index tree is changed during the index search process and the change of the index search route is determined, the index search is retried from a close node based on the upper bound key and the lower bound key.
9. 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;
read a currently searched node;
compare an upper bound key and a lower bound key of the currently searched node with the target index key, wherein at least one of the upper bound key or the lower bound key of each node, which corresponds to an index structure change, is updated; and
determine whether the index search route needs to be changed;
wherein when the index structure is changed during the index search process, the index structure change is detected based on the upper bound key and the lower bound key, and
when the structure of the index tree is changed during the index search process and the change of the index search route is determined, the index search is retried from a close node based on the upper bound key and the lower bound key.