Concurrency control for B-trees with node deletion

• US 20050171960A1
• Filed: 01/30/2004
• Published: 08/04/2005
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lomet, David B.
• Granted Patent: US 7,383,276 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

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 if necessitated by 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. The method of claim 1, where said node operation is a delete 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:

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 correct 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 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.

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. The method of claim 5, where said deleting said target node comprises updating said associated delete state.

8. The method of claim 5, where said step of traversing said B^link-tree data structure to find a correct parent node corresponding to the parent for said target node and a left sibling for said target node comprises checking said associated delete state and if said delete state indicates that a stored parent node for said target node may have been deleted, traversing said B^link-tree data structure to find said parent node for said target node.

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. The method of claim 11, where said post operation comprises:

determining in a first determination whether a stored parent node for said new target node may have been deleted using said delete state associated said stored parent node;

if said first determination determines that said stored parent node for said target node has not been deleted, determining in a second determination whether said new target node may have been deleted using said delete state associated with said new target node; and

if said first determination determines that said stored parent node for said target node has not been deleted and said second determination determines that said new target node has not been deleted, adding new index term to said stored parent node.

13. The method of claim 12 where if said delete state indicates that a node may have been deleted, said post operation is abandoned.

14. The method of claim 12 further comprising:

if an index term has not been posted because delete state indicated that the target node or its parent may have been deleted, performing a subsequent side traversal from a left sibling of the new target node; and

where if, said subsequent side traversal indicates that the index term has not been posted;

a post index term is enqueued for said new target node.

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 if necessitated by 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. The system of claim 16, where said node operation is a delete node operation for a given target node, and where said node operation logic comprises:

determination logic for 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;

traversal logic for traversing said B^link-tree data structure to find a correct parent node corresponding to the parent for said target node and a left sibling for said target node;

parent node latching logic for latching said parent node;

index term deletion logic for deleting an index term for target node from said parent node;

left sibling latching logic for latching said left sibling node;

side traversal logic for performing a side traversal of said left sibling;

target node latching logic for latching said target node, if found by said side traversal;

parent node unlatching logic for unlatching said parent node;

target node under-utilization logic if said target node is latched, 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;

consolidation logic for, 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;

left sibling unlatching logic for unlatching said left sibling node; and

target node deletion logic deleting said target node.

21. The system of claim 20, where said node operation logic comprises:

parent node utilization logic for determining if said parent node is under-utilized; and

delete enqueueing logic for if said parent node is under-utilized, enqueueing a delete node operation for said parent node.

22. The system of claim 20, where said target node deletion logic triggers an update by said delete state logic for updating said delete states.

23. The system of claim 20, where said traversal logic comprises delete state checking logic for checking said associated delete state and if said delete state indicates that a stored parent node for said target node may have been deleted, traversing said B^link-tree data structure to find said parent node for said target node.

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. The system of claim 26, where said post operation enqueuing logic comprises:

first determination logic for determining in a first determination whether a stored parent node for said new target node may have been deleted using said delete state associated with said stored parent node;

second determination logic for, if said first determination determines that said stored parent node for said target node has not been deleted, determining in a second determination whether said new target node may have been deleted using said delete state associated with said new target node; and

new index term addition logic for, if said first determination determines that said stored parent node for said target node has not been deleted and said second determination determines that said stored new target node has not been deleted, adding new index term to said stored parent node.

28. The system of claim 27 where if said delete state indicates that a node may have been deleted, said post operation is abandoned.

29. The system of claim 27 further comprising:

side traversal logic for, if an index term has not been posted because delete state indicated that the target node or its parent may have been deleted, performing a subsequent side traversal from a left sibling of the new target node; and

post index term enqueuing logic for, if, said subsequent side traversal indicates that the index term has not been posted;

a post index term is enqueued for said new target node.

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. The computer-readable medium of claim 32, where said node operation is a delete 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:

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 correct 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 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;

if said target node is found, 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

deleting said target node.

37. The computer-readable medium of claim 36, where said step of performing a node operation on a target node from among said nodes further comprises:

prior to performing a side traversal on said left sibling, obtaining an exclusive latch for said parent node and for said left sibling;

38. The computer-readable medium of claim 36, 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.

39. The computer-readable medium of claim 36, where said deleting said target node comprises updating said associated delete state.

40. The computer-readable medium of claim 36, where said step of traversing said B^link-tree data structure to find a correct parent node corresponding to the parent for said target node and a left sibling for said target node comprises checking said associated delete state and if said delete state indicates that a stored parent node for said target node may have been deleted, traversing said B^link-tree data structure to find said parent node for said target node.

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. The computer-readable medium of claim 43, where said post operation comprises:

determining in a first determination whether a stored parent node for said new index node may have been deleted using said delete state associated with said stored parent node;

if said first determination determines that said stored parent node for said target node has not been deleted, determining in a second determination whether said new index node may have been deleted using said delete state associated with said new index node; and

if said first determination determines that said stored parent node for said target node has not been deleted and said second determination determines that said stored new index node has not been deleted, adding new index node data to said stored parent node.

45. The computer-readable medium of claim 44 where if said delete state indicates that a node may have been deleted, said post operation is abandoned.

46. The computer-readable medium of claim 44 further comprising:

if an index term has not been posted because delete state indicated that the target node or its parent may have been deleted, performing a subsequent side traversal from a left sibling of the new target node; and

where if, said subsequent side traversal indicates that the index term has not been posted;

a post index term is enqueued for said new target node.