A New Method for Concurrency in B-Trees

1 May 1982

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering

Vol. SE-8 (3), 211-222
https://doi.org/10.1109/tse.1982.235251

Abstract

In this paper we study the problem of supporting concurrent operations in B-trees and their variants. A survey of previous work is given and two basic types of solutions to this problem are identified. A new solution with a greater degree of concurrency is proposed. As solutions are surveyed or presented we identify useful techniques which have wider applicability. In particular, we introduce the technique of side-branching in our new solution.

Keywords

This publication has 13 references indexed in Scilit:

On the absence of livelocks in parallel programs
Published by Springer Nature ,2005
Dense multiway trees
ACM Transactions on Database Systems, 1981
Concurrent manipulation of binary search trees
ACM Transactions on Database Systems, 1980
Concurrent search and insertion in 2?3 trees
Acta Informatica, 1980
On B-trees
Published by Association for Computing Machinery (ACM) ,1980
Concurrent operations in large ordered indexes
Lecture Notes in Computer Science, 1980
Ubiquitous B-Tree
ACM Computing Surveys, 1979
Concurrent reading and writing
Communications of the ACM, 1977
Prefix B -trees
ACM Transactions on Database Systems, 1977
Concurrency of operations on B-trees
Acta Informatica, 1977

Cited by 57 articles