Transactions on the multiversion B⁺-tree Export

@inproceedings{citeulike:5076557, abstract = {The multiversion B + -tree (MVBT) by Becker et al. assumes a single-data-item update model in which each new version created for a data item is given a timestamp that is unique across the entire MVBT. In this paper, we extend the MVBT model with multi-action transactions such that all (final) data-item versions created by a transaction are given the same timestamp. We show that the MVBT algorithms can be modified to work in a setting in which multiple readonly transactions and a single updating transaction operate concurrently in snapshot isolation on the MVBT, without compromising the asymptotically optimal time complexity of key inserts, key deletes, and key-range scans on any version. The structural consistency and balance of the MVBT is guaranteed by short-duration latching of pages, redo-only logging of structure modifications (version splits, key splits and page merges), and redo-undo logging of key insertions and deletions. The redo pass of our ARIES-based restart-recovery algorithm always produces a structurally consistent and balanced MVBT on which any undo action by a backward-rolling updating transaction can be performed logically if a physical undo is not possible. The standard steal-and-no-force buffering policy is assumed.}, address = {New York, NY, USA}, author = {Haapasalo, Tuukka and Jaluta, Ibrahim and Seeger, Bernhard and Sippu, Seppo and Soininen, Eljas S.}, booktitle = {EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology}, citeulike-article-id = {5076557}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1516482}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1516360.1516482}, doi = {10.1145/1516360.1516482}, isbn = {978-1-60558-422-5}, keywords = {2009, b-tree, btree, edbt, tx, versioning}, location = {Saint Petersburg, Russia}, pages = {1064--1075}, posted-at = {2009-07-06 16:58:10}, priority = {2}, publisher = {ACM}, title = {Transactions on the multiversion B⁺-tree}, url = {http://dx.doi.org/10.1145/1516360.1516482}, year = {2009} }

TY - CONF ID - citeulike:5076557 L3 - citeulike-article-id:5076557 N2 - The multiversion B + -tree (MVBT) by Becker et al. assumes a single-data-item update model in which each new version created for a data item is given a timestamp that is unique across the entire MVBT. In this paper, we extend the MVBT model with multi-action transactions such that all (final) data-item versions created by a transaction are given the same timestamp. We show that the MVBT algorithms can be modified to work in a setting in which multiple readonly transactions and a single updating transaction operate concurrently in snapshot isolation on the MVBT, without compromising the asymptotically optimal time complexity of key inserts, key deletes, and key-range scans on any version. The structural consistency and balance of the MVBT is guaranteed by short-duration latching of pages, redo-only logging of structure modifications (version splits, key splits and page merges), and redo-undo logging of key insertions and deletions. The redo pass of our ARIES-based restart-recovery algorithm always produces a structurally consistent and balanced MVBT on which any undo action by a backward-rolling updating transaction can be performed logically if a physical undo is not possible. The standard steal-and-no-force buffering policy is assumed. CY - Saint Petersburg, Russia SN - 978-1-60558-422-5 AD - New York, NY, USA EP - 1075 TI - Transactions on the multiversion B⁺-tree PB - ACM T2 - EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology SP - 1064 KW - 2009 KW - b-tree KW - btree KW - edbt KW - tx KW - versioning AU - Haapasalo, Tuukka AU - Jaluta, Ibrahim AU - Seeger, Bernhard AU - Sippu, Seppo AU - Soininen, Eljas PY - 2009/// UR - http://dx.doi.org/10.1145/1516360.1516482 ER -