Batch updates and concurrency control in B-trees

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Degree programme
Teknillinen korkeakoulu, tietotekniikan osasto, tietojenkäsittelyopin laboratorio. A, 38
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.
B-tree, concurrency control, batch update, differential index
Other note
Permanent link to this item