US 5,475,837 AGranted

Method and system for restructuring a B-Tree for managing data during a node splitting operation

AssigneeHewlett-Packard Company

InventorsRagaa Ishak, Yijhye J. Hwang

Life of this patent

Estimating the term…

Loading patent…

Abstract

A database management system and method which permit a B-Tree to be concurrently traversed for the purpose of reading while the B-Tree is actually in the process of restructuring. The present system and method support node splitting for expansion of the B-Tree. The present system and method also support node deletion. A set of update transactions are required to carry out the node-splitting/expansion process. A separate set of steps are required to carry out the node deletion process. The B-Tree can be accessed by readers while either node splitting or deletion occurs, because of the ordering of the process steps. The ordering of the node-splitting and node deletion processes modifies the B-Tree and permit concurrent data readout in an efficient manner. Hence, readers are not required to hold a tree latch or poll for potential in-progress restructuring.

Claims6

Dependent claims

A method for a B-Tree restructuring on a computer system for managing data during a node splitting operation, said system permitting concurrent reading of the B-Tree during the node splitting, wherein the splitting node has a parent node and includes a variable number of variable size keys where each key corresponds to one of a data record and a child node and where the keys include lower value keys and higher value keys, the method comprising the steps of:

(1) generating the following:
first and second child nodes if the splitting node is a parent node;
first and second leaf or child nodes if the splitting node is a leaf node, wherein each leaf node includes a previous link pointing to a previous node and a next link pointing a next node, said next link of said first leaf node points to said second leaf node and said previous link of said second leaf node points to said first leaf node;
(2) copying the lower value keys from the splitting node into said first leaf or child node, wherein the first leaf or child node becomes a LO node;
and copying the higher value keys from the splitting node into the second leaf or child node, wherein the second leaf or child node becomes a HI node;
(3) inserting a first key into the parent node, wherein said first key point to said first leaf or child node;
(4) updating a second key in the parent node, wherein said second key points to said second leaf or child node, wherein said updating of said second key only updates a link part of said second key;
steps (1) through (4) being performed in the order given, with the two steps recited within step (2) being performed in either order;
(5) if the splitting node is a leaf node:
updating node links from at least one of said previous node and said next node to point to said first and second leaf nodes, respectively;
and
(6) marking the splitting node as invalid;
step (6) being performed last.

10 more elements

A computer system for managing data and B-Tree restructuring during a node splitting operation, said system permitting concurrent reading of the B-Tree during the node splitting, wherein the splitting node has a parent node, and includes a variable number of variable size keys where each key corresponds to one of a data record and a child node and where the keys include lower values keys and higher value keys, the system comprising:

(a) means for generating the following;
first and second child nodes if the splitting node is a parent node;
first and second leaf or child nodes if the splitting node is a leaf node, wherein each leaf node includes a previous link pointing to previous node and a next link pointing to a next node, said next link of said first leaf node points to said second leaf node and said previous link of said second leaf node points to said first leaf node;
(b) means for copying the lower value keys from the spitting node into said first leaf or child node, wherein the first leaf or child node becomes a LO node;
and for copying the higher value keys from the splitting node into the second leaf or child node, wherein the second leaf or child node becomes a HI node and each leaf or child node thereby contains at least one link to at least one of a previous node and a next node;
(c) means for inserting a first key into the parent node, wherein said first key points to said first leaf or child node;
(d) means for updating a second key in the parent node, wherein said second key points to said second leaf or child node, wherein said means for updating said second key only updates a link part of said second keys
items (a) through (d) being operated in the order presented, with the two operations recited for item (b) being executed in either order;
(e) means for updating node links from at least one of said previous node and said next node to point to said first and second leaf nodes, respectively, when the splitting node is a leaf node;
and
(f) means for marking the splitting node as invalid;
item (f) being operated last.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/373,675Filed 17 Jan 1995 · continuation
Priority: 29 May 1991
Granted: 12 Dec 1995
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 12/023
User address space allocation, e.g. contiguous or non contiguous base addressing: free address space management
G06F 16/9027
Indexing; Data structures therefor; Storage structures: trees
Y10S 707/99942
Database schema or data structure: manipulating data structure, e.g. compression, compaction, compilation
G06F
Computing and data processing