Concurrent operations on B∗-trees with overtaking

AbstractAlgorithms for concurrent operations (i.e., searches, insertions, and deletions) on B∗-trees are presented. These algorithms improve those given by Lehman and Yao (ACM Trans. Database Systems 6, No. 4 (1981), 650–670), since an insertion process has to lock only one node at any time (as opposed to locking simultaneously two or three nodes in ibid. Another improvement is the ability to compress the tree when some nodes become too sparse as a result of some deletions. Compressing the tree is done by a process that periodically scans the whole tree while running concurrently with the other operations. Alternatively, it is possible to initiate a compression process after each deletion that leaves a node less than half full. These compression processes may run concurrently with the other operations, and they scan only the nodes that have to be compressed. Each compression process has to lock simultaneously three nodes