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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
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
[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]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:31 2009