Batch updates and concurrency control in B-trees

Thumbnail Image

Files

isbn9512258951.pdf (935.91 KB)

URL

Journal Title

Journal ISSN

Volume Title

Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2002-04-15

Department

Department of Computer Science and Engineering
Tietotekniikan osasto

Major/Subject

Mcode

Degree programme

Language

en

Pages

116

Series

Teknillinen korkeakoulu, tietotekniikan osasto, tietojenkäsittelyopin laboratorio. A, 38

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.

Description

Keywords

B-tree, concurrency control, batch update, differential index

Other note

Citation

Permanent link to this item

https://urn.fi/urn:nbn:fi:tkk-001385

Collections

[diss] Perustieteiden korkeakoulu / SCI