Patent ID: 7370055

Claim:
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.