A Restructuring Method for the Concurrent B+-Tree Based on Semantic Consistency.
Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim:
A Restructuring Method for the Concurrent B+-Tree Based on Semantic Consistency.
DASFAA 1999: 229-236@inproceedings{DBLP:conf/dasfaa/LimLK99,
author = {Sungchae Lim and
Yoon-Joon Lee and
Myoung-Ho Kim},
editor = {Arbee L. P. Chen and
Frederick H. Lochovsky},
title = {A Restructuring Method for the Concurrent B$^{\mbox{+}}$-Tree Based on Semantic Consistency},
booktitle = {Database Systems for Advanced Applications, Proceedings of the
Sixth International Conference on Database Systems for Advanced
Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
publisher = {IEEE Computer Society},
year = {1999},
isbn = {0-7695-0084-6},
pages = {229-236},
ee = {db/conf/dasfaa/LimLK99.html},
crossref = {DBLP:conf/dasfaa/99},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
As the B-tree index could be a peformance bottleneck in database systems, concurrent B-tree algorithms have been intensively studied to
improve concurrency of B-tree accesses in the literature. In this paper we propose a new concurrent B+ -tree algorithm for high concurrency and
an eficient tree restructuring method. Because the proposed method of tree restructuring always preserves a semantic consistency of the B+
-tree, a key searcher need not require any lock for a range search as well as a single-key search. To maintain correctly the linkfields constructed
at the leaf level, we make each leaf node contain two key-range indicators, and develop a tree restructuring method using these key-range
indicators.
Copyright © 1999 by The Institute of
Electrical and Electronic Engineers, Inc. (IEEE).
Abstract used with permission.
CDROM Version: Load the CDROM "DiSC, Volume 2 Number 1" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Citation Page
References
- [1]
- Rudolf Bayer, Mario Schkolnick:
Concurrency of Operations on B-Trees.
Acta Inf. 9: 1-21(1977) BibTeX
- [2]
- Philip L. Lehman, S. Bing Yao:
Efficient Locking for Concurrent Operations on B-Trees.
ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
- [3]
- Yat-Sang Kwong, Derick Wood:
A New Method for Concurrency in B-Trees.
IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX
- [4]
- Yehoshua Sagiv:
Concurrent Operations on B*-Trees with Overtaking.
J. Comput. Syst. Sci. 33(2): 275-296(1986) BibTeX
- [5]
- Dennis Shasha, Nathan Goodman:
Concurrent Search Structure Algorithms.
ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
- [6]
- C. Mohan, Frank E. Levine:
ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging.
SIGMOD Conference 1992: 371-380 BibTeX
- [7]
- Ragaa Ishak:
Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring.
ICDE 1992: 184-191 BibTeX
- [8]
- Chendong Zou, Betty Salzberg:
On-line Reorganization of Sparsely-populated B+trees.
SIGMOD Conference 1996: 115-124 BibTeX
- [9]
- Jan Jannink:
Implementing Deletion in B+-Trees.
SIGMOD Record 24(1): 33-38(1995) BibTeX
- [10]
- Jim Gray, Andreas Reuter:
Transaction Processing: Concepts and Techniques.
Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
- [11]
- V. Srinivasan, Michael J. Carey:
Performance of B+ Tree Concurrency Algorithms.
VLDB J. 2(4): 361-406(1993) BibTeX
- [12]
- David B. Lomet, Betty Salzberg:
Access Method Concurrency with Recovery.
SIGMOD Conference 1992: 351-360 BibTeX
- [13]
- Jayant R. Haritsa, S. Seshadri:
Real-Time Index Concurrency Control.
SIGMOD Record 25(1): 13-17(1996) BibTeX
- [14]
- 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
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
DASFAA 1999 Proceedings: Copyright © by IEEE,
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:05:38 2009
