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, h_left, 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, h_left, of a node to access a left sibling of the node if the key k is less than or equal to a value k_min 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.h_left to the left sibling when kA.k_min.