Concurrency control for b-trees with node deletion

Abstract

A data structure, added to a modified form of the B link -tree data structure, tracks delete states for nodes. The index delete state (D X ) indicates whether it is safe to directly access an index node without re-traversing the B-tree. The D X state is maintained globally, outside of the tree structure. The data delete state (D D ) indicates whether it is safe to post an index term for a new leaf node. A D D state is maintained in each level 1 node for its leaf nodes. Delete states indicate whether a specific node has not been deleted, or whether it may have been deleted. Delete states are used to remove the necessity for atomic node splits and chains of latches for deletes, while not requiring retraversal. This property of not requiring a retraversal is exploited to simplify the tree modification operations.

1 . 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; and    updating said at least one delete state based on said node operation.    
   
   
       2 . The method of  claim 1 , where said storing at least one delete state comprises: 
 storing a delete state associated with each of said nodes;    and where said delete state comprises a binary function in which one possible value of said binary function indicates that said associated node has not been deleted.    
   
   
       3 . The method of  claim 1 , where said storing at least one delete state comprises storing a counter value, where said counter value remaining constant over time indicates that none of said associated nodes have been deleted.  
   
   
       4 . The method of  claim 1 , where said storing at least one delete state comprises: 
 for each index node of level one, storing one delete state in said index node associated with all of said leaf nodes that are children of said index node.    
   
   
       5 . (canceled)  
   
   
       6 . The method of  claim 1 , where said step of performing a node operation on a target node from among said nodes further comprises: 
 determining if said parent node is under-utilized; and if said parent node is under-utilized, enqueueing a delete node operation for said parent node.    
   
   
       7 . (canceled)  
   
   
       8 . (canceled)  
   
   
       9 . The method of  claim 1 , where said node operation is an update node operation for a given target node, and where said step of performing a node operation on a target node from among said nodes comprises: 
 traversing said B link -tree data structure to find said target node;    attempting an update of said target node;    if said update fails due to said target node being full, performing a split node operation on said target node; and    if split node operation has been performed, retrying said update of said target node.    
   
   
       10 . The method of  claim 9 , where said step of performing a node operation on a target node from among said nodes further comprises: 
 determining if said target node is under-utilized; and    if said target node is under-utilized, enqueueing a delete node operation for said target node.    
   
   
       11 . The method of  claim 1 , where said node operation is an split node operation for a given target node, and where said step of performing a node operation on a target node from among said nodes comprises: 
 copying a side pointer of said target node and a portion of key data of said target node to a new target node;    setting said side pointer of said target node to point to said new target node; and    adding a post operation for said target node to a work queue.    
   
   
       12 . (canceled)  
   
   
       13 . (canceled)  
   
   
       14 . (canceled)  
   
   
       15 . At least one of an operating system, a computer readable medium having stored thereon a plurality of computer-executable instructions, a co-processing device, a computing device, and a modulated data signal carrying computer executable instructions for performing the method of  claim 1 .  
   
   
       16 . A system 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 system comprising: 
 delete state storage for storing at least one delete state, where said at least one delete state is associated with one or more of said nodes;    node operation logic for performing a node operation on a target node from among said nodes; and    delete state logic for updating said at least one delete state based on said node operation.    
   
   
       17 . The system of  claim 16 , where said delete state storage stores a delete state associated with each of said nodes, and where said delete state comprises a binary function in which one possible value of said binary function indicates that said associated node has not been deleted.  
   
   
       18 . The system of  claim 16 , where said delete state storage storing at least one delete state comprises counter value storage for storing a counter value, where said counter value remaining constant over time indicates that none of said associated nodes have been deleted.  
   
   
       19 . The system of  claim 16 , where said delete state storage storing at least one delete state comprises: 
 index node delete state storage for, for each index node of level one, storing one delete state in said index node associated with all of said leaf nodes that are children of said index node.    
   
   
       20 . (canceled)  
   
   
       21 . (canceled)  
   
   
       22 . (canceled)  
   
   
       23 . (canceled)  
   
   
       24 . The system of  claim 16 , where said node operation is an update node operation for a given target node, and where said node operation logic comprises: 
 traversal logic for traversing said B link -tree data structure to find said target node;    first update attempt logic for attempting an update of said target node; and    split node logic for, if said update fails due to said target node being full, performing a split node operation on said target node; and    second update attempt logic for, if split node operation has been performed, retrying said update of said target node.    
   
   
       25 . The system of  claim 24 , where said node operation logic further comprises: 
 target node utilization logic for determining if said target node is under-utilized; and    delete enqueueing logic for, if said target node is under-utilized, enqueueing a delete node operation for said target node.    
   
   
       26 . The system of  claim 16 , where said node operation is an split node operation for a given target node, and where said node operation logic comprises: 
 target node data copying logic for copying a side pointer of said target node and a portion of key data of said target node to a new target node;    side pointer setting logic for setting said side pointer of said target node to point to said new target node; and    post operation enqueueing logic for adding a post operation for said target node to a work queue.    
   
   
       27 . (canceled)  
   
   
       28 . (canceled)  
   
   
       29 . (canceled)  
   
   
       30 . A memory for storing data for access by an application program comprising a data structure stored in said memory, said data structure adapted for storing one or more data records stored in data nodes, where each of said data records is associated with a key, said data structure comprising a tree comprising at least one index node associated with an associated node range, where each index node from among said index nodes comprises: 
 at least one key value dividing said associated node range into at least two sub-ranges;    at least one child node pointer pointing to another one of said index nodes or one of said data nodes;    at least one side pointer set to a null value or pointing to an index node corresponding to a successive node range; and    a delete state with information regarding whether a data node may have been deleted.    
   
   
       31 . The memory of  claim 30 , where said delete state comprises a counter which is incremented when an action occurs which indicates that a data node may have been deleted.  
   
   
       32 . A computer-readable medium 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, said computer-readable medium comprising computer executable modules having computer executable instructions, the modules comprising instructions for performing the steps of: 
 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; and    updating said at least one delete state if necessitated by said node operation.    
   
   
       33 . The computer-readable medium of  claim 32 , where said storing at least one delete state comprises: 
 storing a delete state associated with each of said nodes;    and where said delete state comprises a binary function in which one possible value of said binary function indicates that said associated node has not been deleted.    
   
   
       34 . The computer-readable medium of  claim 32 , where said storing at least one delete state comprises storing a counter value, where said counter value remaining constant over time indicates that none of said associated nodes have been deleted.  
   
   
       35 . The computer-readable medium of  claim 32 , where said storing at least one delete state comprises: 
 for each index node of level one, storing one delete state in said index node associated with all of said leaf nodes that are children of said index node.    
   
   
       36 . (canceled)  
   
   
       37 . (canceled)  
   
   
       38 . (canceled)  
   
   
       39 . (canceled)  
   
   
       40 . (canceled)  
   
   
       41 . The computer-readable medium of  claim 32 , where said node operation is an update node operation for a given target node, and where said step of performing a node operation on a target node from among said nodes comprises: 
 traversing said B link -tree data structure to find said target node;    attempting an update of said target node;    if said update fails due to said target node being full, performing a split node operation on said target node; and    if split node operation has been performed, retrying said update of said target node.    
   
   
       42 . The computer-readable medium of  claim 41 , where said step of performing a node operation on a target node from among said nodes further comprises: 
 determining if said target node is under-utilized; and    if said target node is under-utilized, enqueueing a delete node operation for said target node.    
   
   
       43 . The computer-readable medium of  claim 32 , where said node operation is an split node operation for a given target node, and where said step of performing a node operation on a target node from among said nodes comprises: 
 copying a side pointer of said target node and a portion of key data of said target node to a new index node;    setting said side pointer of said target node to point to said new index node; and    adding a post operation for said target node to a work queue.    
   
   
       44 . (canceled)  
   
   
       45 . (canceled)  
   
   
       46 . (canceled)