Efficiently performing deletion of a range of keys in a B+ tree
View Patent ↗A method for efficiently performing range deletions in a B+ tree. The method operates to delete all keys within a range in a plurality of iterations. Each iteration may comprise: 1) deleting all of the keys in one or more leaf-nodes that lie within the range of keys; and 2) adjusting entries in the node and its neighbors to perform any required rebalancing of the tree after the deletion. Each iteration of the deletion may comprise a Walk phase identifies nodes in the range of keys to be deleted; a Prepare phase which determines operations (delete and/or node adjust operations) to be performed at one or more levels in the B+ tree based on the identified nodes; and a Delete phase which performs the operations to delete keys in the range of keys in the B+ tree.
1. A computer-readable memory medium comprising program instructions for deleting a range of keys in a B+ tree, wherein the program instructions are executable to implement:
storing the B+ tree on a memory medium of a computer system;
receiving information regarding the range of keys to be deleted in the B+ tree; and
deleting the range of keys from the B+ tree from the memory medium;
wherein after said deleting, the B+ tree utilizes less memory space on the memory medium;
wherein said deleting comprises:
walking at least a portion of the B+ tree, wherein said walking comprises identifying nodes in the range of keys to be deleted and storing information in a delete data structure regarding the identified nodes in the range of keys to be deleted;
determining operations to be performed at one or more levels in the B+ tree based on the identified nodes, wherein the operations comprise one or more delete operations, wherein determining the operations comprises utilizing the information regarding the identified nodes from the delete data structure and storing the determined operations in the delete data structure;
performing the operations to delete one or more keys in the range of keys, wherein said performing the operations comprises traversing the delete data structure to perform the operations stored in the delete data structure; and
repeating said walking, said determining, and said performing one or more times to delete the range of keys.
2. The computer-readable memory medium of claim 1 ,
wherein said deleting is performed in a plurality of iterations, wherein, for each of at least a subset of the plurality of iterations, said deleting comprises:
deleting all of the keys in one or more leaf-nodes that lie within the range of keys; and
adjusting one or more nodes as required after said deleting.
3. The computer-readable memory medium of claim 2 ,
wherein said adjusting comprises adjusting entries from one or more nodes and neighboring nodes at two or more levels to rebalance the B+ tree after the deleting.
4. The computer-readable memory medium of claim 2 ,
wherein said adjusting comprises performing one or more of deleting, shifting and/or rotating entries from one or more nodes and neighboring nodes at two or more levels to rebalance the B+ tree after the deleting.
5. The computer-readable memory medium of claim 1 ,
wherein said deleting comprises deleting the range of keys in a plurality of iterations;
wherein the plurality of iterations is substantially less than the total number of keys in the range of keys.
6. The computer-readable memory medium of claim 1 ,
wherein the information regarding the range of keys to be deleted comprises a starting key and an ending key.
7. The computer-readable memory medium of claim 6 ,
wherein at least one of the starting key and the ending key is an entry in the B+ tree.
8. The computer-readable memory medium of claim 1 ,
wherein the range of keys spans multiple nodes.
9. The computer-readable memory medium of claim 1 ,
wherein the B+ tree comprises a root node and a plurality of leaf nodes;
wherein said walking comprises walking the at least a portion of the B+ tree starting from the root node;
wherein said determining operations comprises walking the delete data structure starting from a leaf node;
wherein said performing the operations comprises walking the delete data structure starting from a leaf node.
10. The computer-readable memory medium of claim 1 ,
wherein the information regarding the range of keys to be deleted comprises a starting key and an ending key;
wherein said walking comprises using the starting key as a search key in said walking.
11. The computer-readable memory medium of claim 1 ,
wherein said walking comprises, at each level, locking a search node, a left node of the search node, if present, and a right node of the search node, if present.
12. The computer-readable memory medium of claim 1 ,
wherein the operations further comprise one or more node adjustment operations.
13. The computer-readable memory medium of claim 1 ,
wherein said determining operations comprises determining at least one operation to be performed on each level that is affected by the deletion.
14. The computer-readable memory medium of claim 1 ,
wherein said operations comprise two or more of:
a simple delete;
a node delete;
a shift and delete;
an adjust parent-node after a shift and delete at the lower level;
a merge and delete;
an adjust parent-node after a merge and delete at the lower level; and
a root collapse.
15. A method for deleting a range of keys in a B+ tree, the method comprising:
storing the B+ tree on a memory medium of a computer system;
receiving information regarding the range of keys to be deleted in the B+ tree; and
deleting the range of keys from the B+ tree from the memory medium;
wherein after said deleting, the B+ tree utilizes less memory space on the memory medium;
wherein said deleting comprises:
walking at least a portion of the B+ tree, wherein said walking comprises identifying nodes in the range of keys to be deleted and storing information in a delete data structure regarding the identified nodes in the range of keys to be deleted;
determining operations to be performed at one or more levels in the B+ tree based on the identified nodes, wherein the operations comprise one or more delete operations, wherein determining the operations comprises utilizing the information regarding the identified nodes from the delete data structure and storing the determined operations in the delete data structure;
performing the operations to delete one or more keys in the range of keys, wherein said performing the operations comprises traversing the delete data structure to perform the operations stored in the delete data structure; and
repeating said walking said determining and said performing one or more times to delete the range of keys.
16. The method of claim 15 ,
wherein said deleting is performed in a plurality of iterations, wherein, for each of at least a subset of the plurality of iterations, said deleting comprises:
deleting all of the keys in one or more leaf-nodes that lie within the range of keys; and
adjusting one or more nodes as required after said deleting.
17. The method of claim 16 ,
wherein said adjusting comprises adjusting entries from one or more nodes and neighboring nodes at two or more levels to rebalance the B+ tree after the deleting.
18. The method of claim 15 ,
wherein said deleting comprises deleting the range of keys in a plurality of iterations;
wherein the plurality of iterations is substantially less than the total number of keys in the range of keys.
19. A system for deleting a range of keys in a B+ tree, the system comprising:
a memory medium which stores:
the B+ tree;
delete program instructions executable to delete the range of keys in the B+ tree;
an input device for receiving information regarding the range of keys to be deleted in the B+ tree; and
a processor coupled to the memory medium and the input device, wherein the processor is operable to execute the delete program instructions to delete the range of keys from the B+ tree from the memory medium;
wherein after said deleting, the B+ tree utilizes less memory space on the memory medium;
wherein said deleting comprises:
walking at least a portion of the B+ tree, wherein said walking comprises identifying nodes in the range of keys to be deleted and storing information in a delete data structure regarding the identified nodes in the range of keys to be deleted;
determining operations to be performed at one or more levels in the B+ tree based on the identified nodes, wherein the operations comprise one or more delete operations, wherein determining the operations comprises utilizing the information regarding the identified nodes from the delete data structure and storing the determined operations in the delete data structure;
performing the operations to delete one or more keys in the range of keys, wherein said performing the operations comprises traversing the delete data structure to perform the operations stored in the delete data structure; and
repeating said walking, said determining and said performing one or more times to delete the range of keys.
20. The system of claim 19 ,
wherein said deleting the range of keys is performed in a plurality of iterations, wherein, for each of at least a subset of the plurality of iterations, the processor is operable to execute the delete program instructions to:
delete all of the keys in one or more leaf-nodes that lie within the range of keys; and
adjust one or more nodes as required after said deleting.
21. A computer-readable memory medium comprising program instructions for deleting a range of keys in a B-tree, wherein the program instructions are executable to implement:
storing the B-tree on a memory medium of a computer system;
receiving information regarding the range of keys to be deleted in the B-tree; and
deleting the range of keys from the B-tree from the memory medium;
wherein after said deleting, the B-tree utilizes less memory space on the memory medium;
wherein said deleting comprises:
walking at least a portion of the B-tree, wherein said walking comprises identifying nodes in the range of keys to be deleted and storing information in a delete data structure regarding the identified nodes in the range of keys to be deleted;
determining operations to be performed at one or more levels in the B-tree based on the identified nodes, wherein the operations comprise one or more delete operations, wherein determining the operations comprises utilizing the information regarding the identified nodes from the delete data structure and storing the determined operations in the delete data structure;
performing the operations to delete one or more keys in the range of keys, wherein said performing the operations comprises traversing the delete data structure to perform the operations stored in the delete data structure; and
repeating said walking, said determining, and said performing one or more times to delete the range of keys.
22. The computer-readable memory medium of claim 21 ,
wherein said deleting is performed in a plurality of iterations, wherein, for each of at least a subset of the plurality of iterations, said deleting comprises:
deleting all of the keys in one or more nodes that lie within the range of keys; and
adjusting one or more nodes as required after said deleting.
23. The computer-readable memory medium of claim 22 ,
wherein said adjusting comprises adjusting entries from one or more nodes and neighboring nodes at two or more levels to rebalance the B-tree after the deleting.