Article

Online B-tree merging

Authors:

Betty Salzberg,

Chendong ZouAuthors Info & Claims

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data

Pages 335 - 346

https://doi.org/10.1145/1066157.1066196

Published: 14 June 2005 Publication History

Abstract

Many scenarios involve merging of two B-tree indexes, both covering the same key range. Increasing demand for continuous availability and high performance requires that such merging be done online, with minimal interference to normal user transactions. In this paper we present an online B-tree merging method, in which the merging of leaf pages in two B-trees are piggybacked lazily with normal user transactions, thus making the merging I/O efficient and allowing user transactions to access only one index instead of both. The concurrency control mechanism is designed to interfere as little as possible with ongoing user transactions. Merging is made forward recoverable by following a conventional logging protocol, with a few extensions. Should a system failure occur, both indexes being merged can be recovered to a consistent state and no merging work is lost. Experiments and analysis show the I/O savings and the performance, and compare variations on the basic algorithm.

References

[1]

K. J. Achyutuni, E. Omiecinski, and S. B. Navathe. Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases. In Proc ACM SIGMOD Conference, pages 125--136, 1996.

Digital Library

[2]

R. Bayer and M. Schkolnick. Concurrency of Operations on B-Trees. Acta Inf., 9:1--21, 1977.

Digital Library

[3]

D. Comer. The Ubiquitous B-Tree. ACM Computing Surveys, 11(2), 1979.

Digital Library

[4]

A. Gartner, A. Kemper, D. Kossmann, and B. Zeller. Efficient Bulk Deletes in Relational Databases. In Proc IEEE ICDE Conference, pages 183--192, 2001.

Digital Library

[5]

G. Graefe. Sorting And Indexing With Partitioned B-Trees. In Biennial Conference on Innovative Data System Research, 2003.

[6]

J. Gray and A. Reuter. Transaction Processing: Techniques and Concepts. Morgan Kaufmann, 1993.

Digital Library

[7]

H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, and R. Kanneganti. Incremental Organization for Data Recording and Warehousing. In Proc VLDB Conference, pages 16--25, 1997.

Digital Library

[8]

T. Johnson and D. Shasha. A Framework for the Performance Analysis of Concurrent B-tree Algorithms. In Proc Symposium on Principles of Database Systems, pages 273--287, 1990.

Digital Library

[9]

M.-L. Lee, M. Kitsuregawa, B. C. Ooi, K.-L. Tan, and A. Mondal. Towards Self-Tuning Data Placement in Parallel Database System. In Proc ACM SIGMOD Conference, pages 225--236, 2000.

Digital Library

[10]

P. L. Lehman and S. B. Yao. Efficient Locking for Concurrent Operations on B-Trees. ACM Transactions on Database Systems, 6(4):650--670, 1981.

Digital Library

[11]

D. Lomet. Simple, Robust and Highly Concurrent B-trees with Node Deletion. In Proc IEEE ICDE Conference, pages 18--28, 2004.

Digital Library

[12]

D. Lomet and B. Salzberg. Access Method Concurrency with Recovery. In Proc ACM SIGMOD Conference, pages 351--360, 1992.

Digital Library

[13]

D. Lomet and B. Salzberg. Concurrency and Recovery for Index Trees. VLDB Journal, 6:224--240, 1997.

Digital Library

[14]

C. Mohan. ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. In Proc VLDB Conference, pages 392--405, 1990.

Digital Library

[15]

C. Mohan and F. Levine. ARIES/IM: an Efficient and High Concurrency Index Management Method Using Write-ahead Logging. In Proc ACM SIGMOD Conference, pages 371--380, 1992.

Digital Library

[16]

C. Mohan and I. Narang. Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. In Proc ACM SIGMOD Conference, pages 361--370, 1992.

Digital Library

[17]

P. Muth, P. E. O'Neil, A. Pick, and G. Weikum. Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method. In Proc VLDB Conference, pages 452--463, 1998.

Digital Library

[18]

N. Ponnekanti and H. Kodavalla. Online Index Rebuild. In Proc ACM SIGMOD Conference, pages 529--538, 2000.

Digital Library

[19]

H. Schmetman. CSIM19: A Powerful Tool for Building System Models. In Proc Winter Simulation Conference, 2001.

Digital Library

[20]

V. Srinivasan and M. J. Carey. Performance of B+ Tree Concurrency Algorithms. VLDB Journal, 2(4):361--406, 1993.

Digital Library

[21]

C. Zou and B. Salzberg. On-line Reorganization of Sparsely-populated B+ trees. In Proc ACM SIGMOD Conference, pages 115--124, 1996.

Digital Library

[22]

C. Zou and B. Salzberg. Safely and Effi ciently Updating References During On-line Reorganization. In Proc VLDB Conference, pages 512--522, 1998.

Digital Library

Cited By

Theil CŠtajner SStuckenschmidt H(2020)Explaining Financial Uncertainty through Specialized Word EmbeddingsACM/IMS Transactions on Data Science10.1145/33430391:1(1-19)Online publication date: 12-Mar-2020
https://dl.acm.org/doi/10.1145/3343039
Chen YLien YHuang P(2020)Hashed B-tree: Adaptive Performance Enhancement of B-tree on Byte-addressable Nonvolatile Memories2020 IEEE Green Technologies Conference(GreenTech)10.1109/GreenTech46478.2020.9289805(53-58)Online publication date: 1-Apr-2020
https://doi.org/10.1109/GreenTech46478.2020.9289805
Wevers LHuisman Mvan Keulen MDesai BToyama MBernardino J(2016)Lazy Evaluation for Concurrent OLTP and Bulk TransactionsProceedings of the 20th International Database Engineering & Applications Symposium10.1145/2938503.2938555(115-124)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2938503.2938555
Show More Cited By

Online B-tree merging
1. Information systems
  1. Data management systems
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Modern floorplanning based on B^*-tree and fast simulated annealing

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern very large scale integration (VLSI) floorplanning typically needs to pack blocks within a fixed die (outline), and additionally considers the packing ...
T-Tree or B-Tree: Main Memory Database Index Structure Revisited
ADC '00: Proceedings of the Australasian Database Conference

While the B-tree (or the B+-tree) is the most popular index structure in disk-based relational database systems, the T-tree has been widely accepted as a promising index structure for main memory databases where the entire database (or most of them) ...
Obstacle-avoiding rectilinear Steiner tree construction
ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design

In today's VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of data

June 2005

990 pages

ISBN:1595930604

DOI:10.1145/1066157

Conference Chair:
Fatma Ozcan
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS05

Sponsor:

SIGMOD/PODS05: International Conference on Management of Data and Symposium on Principles Database and Systems

June 14 - 16, 2005

Maryland, Baltimore

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
979
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Theil CŠtajner SStuckenschmidt H(2020)Explaining Financial Uncertainty through Specialized Word EmbeddingsACM/IMS Transactions on Data Science10.1145/33430391:1(1-19)Online publication date: 12-Mar-2020
https://dl.acm.org/doi/10.1145/3343039
Chen YLien YHuang P(2020)Hashed B-tree: Adaptive Performance Enhancement of B-tree on Byte-addressable Nonvolatile Memories2020 IEEE Green Technologies Conference(GreenTech)10.1109/GreenTech46478.2020.9289805(53-58)Online publication date: 1-Apr-2020
https://doi.org/10.1109/GreenTech46478.2020.9289805
Wevers LHuisman Mvan Keulen MDesai BToyama MBernardino J(2016)Lazy Evaluation for Concurrent OLTP and Bulk TransactionsProceedings of the 20th International Database Engineering & Applications Symposium10.1145/2938503.2938555(115-124)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2938503.2938555
Sippu SSoisalon-Soininen ESippu SSoisalon-Soininen E(2014)Transaction Rollback and Restart RecoveryTransaction Processing10.1007/978-3-319-12292-2_4(65-99)Online publication date: 17-Nov-2014
https://doi.org/10.1007/978-3-319-12292-2_4
Wei WYu TXue RBertino ESandhu RBauer LPark J(2013)iBigTableProceedings of the third ACM conference on Data and application security and privacy10.1145/2435349.2435399(341-352)Online publication date: 18-Feb-2013
https://dl.acm.org/doi/10.1145/2435349.2435399
Wang JZhang YGao YXing C(2013)pLSMProceedings of the 2013 IEEE 37th Annual Computer Software and Applications Conference10.1109/COMPSAC.2013.40(240-245)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1109/COMPSAC.2013.40
Nuray-Turan RKalashnikov DMehrotra S(2012)Exploiting Web querying for Web people searchACM Transactions on Database Systems10.1145/2109196.210920337:1(1-41)Online publication date: 6-Mar-2012
https://dl.acm.org/doi/10.1145/2109196.2109203
Ré CSuciu D(2012)Understanding cardinality estimation using entropy maximizationACM Transactions on Database Systems10.1145/2109196.210920237:1(1-31)Online publication date: 6-Mar-2012
https://dl.acm.org/doi/10.1145/2109196.2109202
Yang DRundensteiner EWard M(2012)Shared execution strategy for neighbor-based pattern mining requests over streaming windowsACM Transactions on Database Systems10.1145/2109196.210920137:1(1-44)Online publication date: 6-Mar-2012
https://dl.acm.org/doi/10.1145/2109196.2109201
Liu ZChen Y(2012)Differentiating search results on structured dataACM Transactions on Database Systems10.1145/2109196.210920037:1(1-30)Online publication date: 6-Mar-2012
https://dl.acm.org/doi/10.1145/2109196.2109200
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents