Learning Centre

Batch updates and concurrency control in B-trees

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Pollari-Malmi, Kerttu
dc.date.accessioned 2012-02-10T09:16:51Z
dc.date.available 2012-02-10T09:16:51Z
dc.date.issued 2002-04-15
dc.identifier.isbn 951-22-5895-1
dc.identifier.issn 1239-6885
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/2168
dc.description.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. en
dc.format.extent 116
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Helsinki University of Technology en
dc.publisher Teknillinen korkeakoulu fi
dc.relation.ispartofseries Teknillinen korkeakoulu, tietotekniikan osasto, tietojenkäsittelyopin laboratorio. A en
dc.relation.ispartofseries 38 en
dc.subject.other Computer science en
dc.title Batch updates and concurrency control in B-trees en
dc.type G4 Monografiaväitöskirja fi
dc.description.version reviewed en
dc.contributor.department Department of Computer Science and Engineering en
dc.contributor.department Tietotekniikan osasto fi
dc.subject.keyword B-tree en
dc.subject.keyword concurrency control en
dc.subject.keyword batch update en
dc.subject.keyword differential index en
dc.identifier.urn urn:nbn:fi:tkk-001385
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (monografia) fi
dc.type.ontasot Doctoral dissertation (monograph) en
dc.contributor.lab Laboratory of Information Processing Science en
dc.contributor.lab Tietojenkäsittelytekniikan laitos fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse