Patent ID: 7383276

Claim:
A method for storing one or more data records in a B link -tree data structure comprising at least two nodes, said nodes comprising at least one index node and at least one leaf node, where each of said data records is associated with a key, the method comprising: storing at least one delete state, where said at least one delete state is associated with one or more of said nodes; performing a node operation on a target node from among said nodes, where said node operation is a delete node operation for a given target node, and where said step of performing said node operation on a target node from among said nodes comprises: determining whether a remembered parent node may have been deleted using said delete state associated with said remembered parent node and aborting said delete node operation if said delete state indicates that said remembered parent node may have been deleted; traversing said B link -tree data structure to find a connect parent node corresponding to the parent for said target node and a left sibling for said target node; latching said parent node; deleting an index term for said target node from said parent node; latching said left sibling node; performing a side traversal of said left sibling; latching said target node, if found by said side traversal; unlatching said parent node; determining if said target node is under-utilized and if the contents of said target node can be consolidated with the contents of said left sibling in said left sibling; if said target node is under-utilized and the contents of said target node can be consolidated with the contents of said left sibling, copying data from said target node comprising a side pointer, a key space description associated with said side pointer and key values to said left sibling; unlatching said left sibling node and target node, and deleting said target node; and updating said at least one delete state in response to said node operation.