Efficiently performing deletion of a range of keys in a B+ tree

Details Efficiently performing deletion of a range of keys in a B+ tree Efficiently performing deletion of a range of keys in a B+ tree

2003-06-04

2008-05-06

Pham, Hung Q (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C700S100000, C700S102000

Reexamination Certificate

active

07370055

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

REFERENCES:
patent: 5813000 (1998-09-01), Furlani
patent: 6009425 (1999-12-01), Mohan
patent: 6330653 (2001-12-01), Murray et al.
patent: 6427147 (2002-07-01), Marquis
Ramakrishnan, Raghu and Gehrke, Johannes, Database Management Systems, Aug. 2002, McGraw-Hill, 3rd ed., pp. 344-352.
Paul E. Black, “Balanced Tree”, in Dictionary of Algorithms and Data Structures [Online], Paul E. Black., U.S. National Institute of Standards and Technology. Jan. 24, 2005 <http://www.nist.gov/dads/HTML/balancedtree.html>, 1 page.
Nicodeme, Pierre, “Compact Balanced Tries”, 1992, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Archtecture- Information Processing 92, vol. 1.
Elmasri et al., “Fundamentals of Database Systems”, copyright 2000, Buschlen/Mowatt Fine Arts Ltd., Third Edition, pp. 175-183.
Silberschatz et al., Database System Concepts, Third Edition, 1997, pp. 346-358.

Affiliated with

Also associated with

Rating

Efficiently performing deletion of a range of keys in a B+ tree does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficiently performing deletion of a range of keys in a B+ tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiently performing deletion of a range of keys in a B+ tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3983953