Concurrency control for B-trees with node deletion
First Claim
1. A method for storing one or more data records in a Blink-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 Assignments
0 Petitions
Accused Products
Abstract
A data structure, added to a modified form of the Blink-tree data structure, tracks delete states for nodes. The index delete state (DX) indicates whether it is safe to directly access an index node without re-traversing the B-tree. The DX state is maintained globally, outside of the tree structure. The data delete state (DD) indicates whether it is safe to post an index term for a new leaf node. A DD 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.
-
Citations
46 Claims
-
1. A method for storing one or more data records in a Blink-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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A system for storing one or more data records in a Blink-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. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
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. - View Dependent Claims (31)
-
-
32. A computer-readable medium for storing one or more data records in a Blink-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. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46)
-
Specification