More Web Proxy on the site http://driver.im/

Article

Free access

On-line reorganization of sparsely-populated B+-trees

Authors:

Betty SalzbergAuthors Info & Claims

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

Pages 115 - 124

https://doi.org/10.1145/233269.233325

Published: 01 June 1996 Publication History

Abstract

In this paper, we present an efficient method to do online reorganization of sparsely-populated B⁺-trees. It reorganizes the leaves first, compacting in short operations groups of leaves with the same parent. After compacting, optionally, the new leaves may swap locations or be moved into empty pages so that they are in key order on the disk. After the leaves are reorganized, the method shrinks the tree by making a copy of the upper part of the tree while leaving the leaves in place. A new concurrency method is introduced so that only a minimum number of pages are locked during reorganization. During leaf reorganization, Forward Recovery is used to save all work already done while maintaining consistency after system crashes. A heuristic algorithm is developed to reduce the number of swaps needed during leaf reorganization, so that better concurrency and easier recovery can be achieved. A detailed description of switching from the old B⁺-tree to the new B⁺-tree is described for the first time.

References

[1]

R. Bayer and M Schkolnick. C, oncurrency of operations on B-trees. Aeta Informatica, 9(1):1- 21, 1977.

Digital Library

[2]

Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufinann Publishers, Inc, t993.

Digital Library

[3]

Theodore Johnson and Dennis ShasheL. B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half. Journal of ('ompute'r and System Sciences, 47(1 ):45-76, 199,3.

Digital Library

[4]

D. Lomet and B. Salzberg. Access method concurrency with recovery.In Proceedzng~ of A CM/SIGMOD Annual Conference on Manage'- ment of Data, p~ges 351-360, 1992.

Digital Library

[5]

David Lomet and Mark Tuttle. Redo recovery after system crashes. In Internatzonal (:onference on Very Large Data Bases, pages 457-468, 1995.

[6]

C,. Mohan and Inderpal Narang. Algorithms for creating indexes for very large tables without quiescing updates. {n Proceedings of A('M/5;I(;MOD Annual Conference on Management of Data, {)ages 361-370, 1992.

Digital Library

[7]

C. Mohan. ARIES/KVL: A Key-Value Locking Method for Concurrency (;ontrol of Multiaction Transactions Operating on B-Tree Indexes. {n hzternat~onal Conference on Very Large Data Base~, pages 392-405, Brisbane, Australia, August 199t).

Digital Library

[8]

E. Omiecinski, L. Lee, and P. Scheuermann. C, oncurrent file reorganization for record clustering: A performance study. In Internatzonal C, onference On Data Engzneemng, pages 265-272, 1992

[9]

E. Omiecinski. (1oncurrent storage strllcture conversion: From B+Tree to liIlear hash file. In International Conference On Data Engzneemng, pages 589-596, 1988.

Digital Library

[10]

Betty Salzberg. Fzle Structures: An Analytzc Approach. Prentice Hall, 1988.

Digital Library

[11]

V. Sriniwsan and Michael J. (:arey. Performance of on-line index construction algorithms.In International ('onference on Extending Database' Technology, pages 293-309, 1992.

Digital Library

[12]

B. Satzberg and A. Dimock. Principles of transaction-based on-line reorganization. In International Conference on Very Large Data Base~', pages 511-520, 1992.

Digital Library

[13]

Gary Smith. Online reorganization of keysequenced t~bles and files. Tandem System Review, 6(2):52-59, October 1990. Describe algorithm of Franco Putzolu.

[14]

H. Wedekind. On the select,on of access paths zn a data base system, chapter Database Management. North Holland Publishing Company, 1974.

[15]

(:hendong Zou and Betty SMzberg. On-Line Reorganization of Sparsely-Populated B+trees. Technical Report NU-CCS-95-18, Northeastern University, College of Computer Science, Boston, MA (USA), 1995.

Cited By

Farka FNanevski ABanerjee ADelbianco GFábregas I(2021)On algebraic abstractions for concurrent separation logicsProceedings of the ACM on Programming Languages10.1145/34342865:POPL(1-32)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434286
Margalit RLahav O(2021)Verifying observational robustness against a c11-style memory modelProceedings of the ACM on Programming Languages10.1145/34342855:POPL(1-33)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434285
Anton EAyesta UJonckheere MVerloop I(2021)Improving the Performance of Heterogeneous Data Centers through RedundancyProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283334:3(1-29)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3428333
Show More Cited By

Index Terms

On-line reorganization of sparsely-populated B+-trees

Recommendations

On-line reorganization of sparsely-populated B+-trees

In this paper, we present an efficient method to do online reorganization of sparsely-populated B⁺-trees. It reorganizes the leaves first, compacting in short operations groups of leaves with the same parent. After compacting, optionally, the new leaves ...
Linear Bidirectional On-Line Construction of Affix Trees

Affix trees are a generalization of suffix trees that are based on the inherent duality of suffix trees induced by the suffix links. An algorithm is presented that constructs affix trees on-line by expanding the underlying string in both directions and ...
b-Matchings in Trees

We develop linear-time algorithms to find maximum weighted and unweighted degree-constrained subgraphs (b-matchings) of a tree. We use a generalization of an algorithm for finding a maximum 2-matching in a tree.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

June 1996

560 pages

ISBN:0897917944

DOI:10.1145/233269

Editor:
Jennifer Widom
Stanford Univ., Stanford, CT

ACM SIGMOD Record Volume 25, Issue 2
June 1996
557 pages
ISSN:0163-5808
DOI:10.1145/235968
Chairman:
T. H. Merrett
McGill Univ.
,
Editors:
H. V. Jagadish,
Inderpal Singh Mumick
Issue’s Table of Contents

Copyright © 1996 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: 01 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS96

Sponsor:

SIGMOD/PODS96: Joint ACM SIGMOD International Conference on Management of Data and ACM Symposium on Principles of Database Systems

June 4 - 6, 1996

Quebec, Montreal, Canada

Acceptance Rates

SIGMOD '96 Paper Acceptance Rate 47 of 290 submissions, 16%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
566
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)9

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farka FNanevski ABanerjee ADelbianco GFábregas I(2021)On algebraic abstractions for concurrent separation logicsProceedings of the ACM on Programming Languages10.1145/34342865:POPL(1-32)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434286
Margalit RLahav O(2021)Verifying observational robustness against a c11-style memory modelProceedings of the ACM on Programming Languages10.1145/34342855:POPL(1-33)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434285
Anton EAyesta UJonckheere MVerloop I(2021)Improving the Performance of Heterogeneous Data Centers through RedundancyProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283334:3(1-29)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3428333
Raaijmakers YBorst S(2021)Achievable Stability in Redundancy SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283314:3(1-21)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3428331
Fleder MShah D(2020)I Know What You Bought At Chipotle for $9.81 by Solving A Linear Inverse ProblemProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283324:3(1-17)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1145/3428332
Ott FWehbi MHamann TBarth JEskofier BMutschler C(2020)The OnHW DatasetProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/34118424:3(1-20)Online publication date: 4-Sep-2020
https://dl.acm.org/doi/10.1145/3411842
Kuszmaul BFrigo MPaluska JSandler A(2020)Everyone Loves FileACM Transactions on Storage10.1145/337787716:1(1-29)Online publication date: 5-Mar-2020
https://dl.acm.org/doi/10.1145/3377877
Graefe G(2019)On Transactional Concurrency ControlSynthesis Lectures on Data Management10.2200/S00912ED2V01Y201904DTM05914:5(1-404)Online publication date: 11-Jun-2019
https://doi.org/10.2200/S00912ED2V01Y201904DTM059
Kato CHayamizu YGoda KKitsuregawa MDesai BToyama M(2015)An Experimental Study of Aging Influence on Query Cost EstimationProceedings of the 19th International Database Engineering & Applications Symposium10.1145/2790755.2790783(220-221)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1145/2790755.2790783
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
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents