Browse Prior Art Database

Locking Protocols for Concurrent Operations on B Trees

IP.com Disclosure Number: IPCOM000087790D
Original Publication Date: 1977-Mar-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Bayer, R: AUTHOR [+2]

Abstract

A mechanism which allows concurrent use of a B-tree structure is presented. A protocol for using this mechanism is also included. The protocol can be shown to be deadlock-free and is parameterized so that maximum concurrency can be achieved for a given mixture of users of the structure.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 3

Locking Protocols for Concurrent Operations on B Trees

A mechanism which allows concurrent use of a B-tree structure is presented. A protocol for using this mechanism is also included. The protocol can be shown to be deadlock-free and is parameterized so that maximum concurrency can be achieved for a given mixture of users of the structure.

A B-tree [1] is a dynamic data structure which allows users to maintain and retrieve elements from a sorted set when deletions and insertions are frequently made to the set. The structures have wide application as support of access paths to indexed files [2]. For simplicity, we will use the variant presented by Wedekind [3]. However, the ideas presented here are easily extended to any other type of B-tree. When these structures are used in a multiuser environment, they may cause a bottleneck in the operation of the system in which they exist since all users have to access them, and without a proper synchronization mechanism available, all the accesses to it have to be serialized. Although B- trees are well suited for access by a single user, no satisfactory mechanism for concurrent access has been previously reported, the best one being that presented in [4].

The mechanism proposed here has four different signals (RR, RU, A, X) that users may give to each other. These signals (which we will call locks) are to be placed in the nodes of the structure being visited. Depending on the type of each lock placed on a node by a user, access to the node in question may be prohibited or restricted for other users. This control over access to a node is enforced by restricting the types of locks that can be simultaneously placed in any given node. These restrictions, called incompatibilities, are shown below. Existing lock

RR RU A X

Lock RR yes yes yes no to RU yes yes no no be A yes no no no placed x no no no no
Compatibilities Among Locks

This table is to be interpreted as follows: If a user wishes to visit a node of the structure, he has to place a lock on it. If the lock to be placed is compatible (as shown by a yes entry in the table) with every existing lock on the node, access is permitted and the new lock is placed in the node. If the locks are incompatible, however, the incoming user is placed on a wait set for visiting this node. Once a user is placed on a wait set for a node, he cannot request that locks be placed on other nodes. (The way users are selected for removal from these sets is not important here. Any reasonable method can be used, e.g., a round-robin selection).

With the above synchronization mechanism, we now describe protocols to be used by users of these data structures. Two types of users are distinguished: those that will access the structure to retrieve information only and those that wish to modify it. We call the first type of users readers and the second type

1

Page 2 of 3

updaters. Modification to these structures (either by way of an insertion or a deletion) is a known proces...