Batch updates and concurrency control in B-trees

Abstract

When a large number of new keys are to be inserted (or deleted) into a B-tree at about the same time, it is often profitable to sort the keys in the main memory before performing updates to the B-tree on disk. Thus, updates falling into the same leaf of the B-tree can be performed simultaneously and disk accesses are saved. In this thesis, new batch-update algorithms for B-trees are presented and analyzed.

First, an efficient batch-insertion algorithm for a situation where no concurrency control is needed is presented and analyzed. The algorithm is asymptotically optimal in the number of structure modification operations needed to rebalance the tree after the batch insertion.

Next, new batch-update algorithms for different types of B-trees such that the batch update can be performed concurrently with other actions are presented. Experimental tests have been performed to compare the new algorithms with an earlier algorithm. According to simulation results, the new algorithms allow much more concurrency than the previous algorithm.

Finally, a differential indexing system is presented. In the system a database index is divided into two parts: the main index located on disk and the differential index in the main memory. Periodically, writes of committed transactions are transferred from the differential index to the main index as a batch-update operation.