System and method for restructuring a B-Tree

摘要

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.