Algorithm for tree traversals using left links

Abstract

An information management system includes a computer and a database comprising a B-Tree data structure comprising a plurality of nodes associated with disk blocks and handles stored in the nodes. At least one left-link handle, hleft, stored in each node points to a left sibling of that node. A mechanism for performing a lookup operation with respect to a key, k, traverses the B-Tree and refers to the left-link handle, hleft, of a node to access a left sibling of the node if the key k is less than or equal to a value kmin stored in the node. Mechanisms are also provided for performing insert and delete operations, and the lookup, insert, and delete operations detect if the key range of an index node, A, does not include the key k that the operation is trying to locate, and follow a handle A.hleft to the left sibling when k≦A.kmin.

Dependencies are inferred from the claim text.