| 摘要 |
The present invention relates to a method, a corresponding system and a computer program for traversing an index tree consisting of nodes for searching data in a database of a database management system having main memory and cache, in order to find a leaf node corresponding to a search key through latch-free read operations in the database management system, where each node has contents, a version number indicating the updated status of the node contents, a latch governing concurrent access to each node, wherein the node contents further includes one or more keys, a high key denoting the upper bound of the keys, a link pointer pointing to the right sibling of the node at the same level, and one or more pointers to data items in the database in the case of a leaf node and to child nodes in the case of a non-leaf node, the method comprising the steps of:
starting from the root node; following the link pointer if the search key is greater than the high key of the node; and
following one of the pointers to a child node if the key is not greater than the high key of the node; and
repeating said steps of following the link pointer and the following one of the pointers to a child node until a leaf node corresponding to the search key is found. |
