On-line Reorganization of Sparsely-populated B+trees.

Chendong Zou, Betty Salzberg: On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conference 1996: 115-124

@inproceedings{DBLP:conf/sigmod/ZouS96,
  author    = {Chendong Zou and
               Betty Salzberg},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {On-line Reorganization of Sparsely-populated B+trees},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {115-124},
  ee        = {http://doi.acm.org/10.1145/233269.233325, db/conf/sigmod/ZouS96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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 decribed for the first time.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 BibTeX , SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1138 KB]

References

[BS77]: Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[GR93]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[JS93]: Theodore Johnson, Dennis Shasha: B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than Merge-at-Half. J. Comput. Syst. Sci. 47(1): 45-76(1993) BibTeX
[LS92]: David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360 BibTeX
[LT95]: David B. Lomet, Mark R. Tuttle: Redo Recovery after System Crashes. VLDB 1995: 457-468 BibTeX
[MN92]: C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370 BibTeX
[Moh90]: C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 BibTeX
[OLS92]: Edward Omiecinski, Liehuey Lee, Peter Scheuermann: Concurrent File Reorganization for Record Clustering: A Performance Study. ICDE 1992: 265-272 BibTeX
[Omi88]: Edward Omiecinski: Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File. ICDE 1988: 589-596 BibTeX
[Sal88]: Betty Salzberg: File Structures: An Analytic Approach. Prentice-Hall 1988, ISBN 0-13-314550-6
BibTeX
[SC92]: V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309 BibTeX
[SD92]: Betty Salzberg, Allyn Dimock: Principles of Transaction-Based On-Line Reorganization. VLDB 1992: 511-520 BibTeX
[Smi90]: ...
[Wed74]: ...
[ZS95]: ...

Referenced by

Nagavamsi Ponnekanti, Hanuma Kodavalla: Online Index Rebuild. SIGMOD Conference 2000: 529-538
Mong-Li Lee, Masaru Kitsuregawa, Beng Chin Ooi, Kian-Lee Tan, Anirban Mondal: Towards Self-Tuning Data Placement in Parallel Database Systems. SIGMOD Conference 2000: 225-236
Mohana Krishna Lakhamraju, Rajeev Rastogi, S. Seshadri, S. Sudarshan: On-line Reorganization in Object Databases. SIGMOD Conference 2000: 58-69
Vijayshankar Raman: Locality Preserving Dictionaries: Theory and Application to Clustering in Databases. PODS 1999: 337-345
Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim: A Restructuring Method for the Concurrent B⁺-Tree Based on Semantic Consistency. DASFAA 1999: 229-236
Chendong Zou, Betty Salzberg: Safely and Efficiently Updating References During On-line Reorganization. VLDB 1998: 512-522
David B. Lomet, Betty Salzberg: Concurrency and Recovery for Index Trees. VLDB J. 6(3): 224-240(1997)
Chendong Zou, Betty Salzberg: Towards Efficient Online Database Reorganization. IEEE Data Eng. Bull. 19(2): 33-40(1996)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]