Article

Free access

Concurrency control in database structures with relaxed balance

Authors:

E. Soisalon-Soininen,

D. WoodAuthors Info & Claims

PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 170 - 176

https://doi.org/10.1145/28659.28677

Published: 01 June 1987 Publication History

Abstract

We consider the separation of rebalancing from updates in several database structures, such as B-trees for external and AVL-trees for internal structures. We show how this separation can be implemented such that rebalancing is performed by local background processes. Our solution implies that even simple locking schemes (without additional links and copies of certain nodes) for concurrency control are efficient in the sense that at any time only a small constant number of nodes must be locked.

References

[1]

Bayer,R and E McCrelght, Orgamzatlon and maintenance of large ordered indexes Acts Inf I (1972), 173-189

[2]

Corner,D, The ublqmtous B-tree ACM Comput Surveys II (1979), 121-138

[3]

DIjkstra,E W, L Lamport, A J Martin, C S Scholten, and E F M Steffens, On-the-fly garbage collectlon An exerclse in cooperatlon Cornrn ACM 21 (1978), 966-975

Digital Library

[4]

Elhs,C S, Concurrent search and msertlon m AVL trees IEEE Trans on Computers C-29 (1980), 811- 817

Digital Library

[5]

Elhs,C S, Concurrent search and insertlon in 2-3 trees Acta Inf 14 (1980), 63-86

[6]

Goodrnan,N and D Sasha, Semantlcally based concurrency control for search structures Proc Fourth ACM SIGACT-SIGMOD Syrnp on Prmclples of Database Systems, 1985, pp 8-19

Digital Library

[7]

Gulbas,L J, and R Sedgew,ck, A d,chromat,c framework for balanced trees, Proc 19th IEEE Syrup on Foundatlons of Computer Sclence, 1978, pp 8-21

[8]

Kessels,J L W, On-the-fly optimization of data structures Comm ACM 26 (1983), 895-901

Digital Library

[9]

Knuth,D E, The Art of Computer Programming, Vol 3 Sorting and Searching Addison-Wesley, Reading, Mass, 1973

Digital Library

[10]

Kung,H T and P L Lehman, A concurrent database mampulatlon problem binary search trees A CM Trans Database Syst 5 (1980), 339-353

Digital Library

[11]

Kwong,Y S and D Wood, A new method for concurrency m B-trees IEEE Trans Soft Eug SE-8 (1982) 211-2 2

Digital Library

[12]

Lehman,P L and S B Yao, Effic,ent locking for concurrent operations on B-trees A CM Trans Database Syst 5 (1981), 650-670

Digital Library

[13]

Lehman,T J and M J Carey, Query processing m ma, n memory database management systems Proc A CM SIGMOD Conf, 1986, pp 239-250

Digital Library

[14]

Manber,U and R E Ladner, Concurrency control m a dynam,c search structure A CM Trans Database Syst 9 (1984), 439-455

Digital Library

[15]

Saglv,Y, Concurrent operahons on B-trees with overtaking Journal of Computer and System Sciences 33 (1986)

[16]

Samadl,B, B-trees in a system with multiple users Inform Process Left 5 (1976), 107-112

Cited By

Crain TGramoli VRaynal M(2018)A speculation‐friendly binary search treeConcurrency and Computation: Practice and Experience10.1002/cpe.488331:4Online publication date: 31-Jul-2018
https://doi.org/10.1002/cpe.4883
Sen STarjan RKim D(2016)Deletion Without Rebalancing in Binary Search TreesACM Transactions on Algorithms10.1145/290314212:4(1-31)Online publication date: 2-Sep-2016
https://dl.acm.org/doi/10.1145/2903142
Laccetti GLapegna MMele V(2016)A Loosely Coordinated Model for Heap-Based Priority Queues in Multicore EnvironmentsInternational Journal of Parallel Programming10.1007/s10766-015-0398-x44:4(901-921)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10766-015-0398-x
Show More Cited By

Index Terms

Concurrency control in database structures with relaxed balance

Recommendations

Optimistic concurrency control algorithms for distributed database systems
Relaxed Concurrency Control in Software Transactional Memory

Some of today's TM systems implement the two-phase-locking (2PL) algorithm which aborts transactions every time a conflict occurs. 2PL is a simple algorithm that provides fast transactional operations. However, it limits concurrency in benchmarks with ...
Concurrency control and recovery for multiversion database structures
PIKM '08: Proceedings of the 2nd PhD workshop on Information and knowledge management

In modern database applications access to historical versions of the dataset is becoming increasingly important. Several multiversion structures with corresponding concurrency-control and recovery algorithms exist, but none of these have optimal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

June 1987

363 pages

ISBN:0897912233

DOI:10.1145/28659

Editor:
Moshe Y. Vardi

Copyright © 1987 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 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODS '87

Sponsor:

PODS '87: Principles of database systems

March 23 - 25, 1987

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
460
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)4

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Crain TGramoli VRaynal M(2018)A speculation‐friendly binary search treeConcurrency and Computation: Practice and Experience10.1002/cpe.488331:4Online publication date: 31-Jul-2018
https://doi.org/10.1002/cpe.4883
Sen STarjan RKim D(2016)Deletion Without Rebalancing in Binary Search TreesACM Transactions on Algorithms10.1145/290314212:4(1-31)Online publication date: 2-Sep-2016
https://dl.acm.org/doi/10.1145/2903142
Laccetti GLapegna MMele V(2016)A Loosely Coordinated Model for Heap-Based Priority Queues in Multicore EnvironmentsInternational Journal of Parallel Programming10.1007/s10766-015-0398-x44:4(901-921)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10766-015-0398-x
Ohene-Kwofie DOtoo ENimako G(2013)Concurrent operations of O2-tree on shared memory multicore architecturesProceedings of the Twenty-Fourth Australasian Database Conference - Volume 13710.5555/2525416.2525420(33-42)Online publication date: 29-Jan-2013
https://dl.acm.org/doi/10.5555/2525416.2525420
Crain TGramoli VRaynal M(2013)No Hot Spot Non-blocking Skip ListProceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems10.1109/ICDCS.2013.42(196-205)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1109/ICDCS.2013.42
Crain TGramoli VRaynal M(2012)A speculation-friendly binary search treeACM SIGPLAN Notices10.1145/2370036.214583747:8(161-170)Online publication date: 25-Feb-2012
https://dl.acm.org/doi/10.1145/2370036.2145837
Crain TGramoli VRaynal MRamanujam JSadayappan P(2012)A speculation-friendly binary search treeProceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming10.1145/2145816.2145837(161-170)Online publication date: 25-Feb-2012
https://dl.acm.org/doi/10.1145/2145816.2145837
Messeguer X(2011)Skip trees, an alternative data structure to skip lists in a concurrent approachRAIRO - Theoretical Informatics and Applications10.1051/ita/199731030251131:3(251-269)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1997310302511
Bronson NCasper JChafi HOlukotun K(2010)A practical concurrent binary search treeACM SIGPLAN Notices10.1145/1837853.169348845:5(257-268)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693488
Bronson NCasper JChafi HOlukotun KGovindarajan RPadua DHall M(2010)A practical concurrent binary search treeProceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/1693453.1693488(257-268)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1693453.1693488
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