Patent ID: 7293028

Claim:
A method of 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 while reducing coherence cache misses 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 the pointer 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 the pointer until a leaf node corresponding to the search key is found.