Concurrent operations on \(B^ *\)-trees with overtaking
type: Item
instance of: scholarly article
title: Concurrent operations on \(B^ *\)-trees with overtaking
zbMATH Open document ID: 0625.68084
DOI: 10.1016/0022-0000(86)90021-8
author: Yehoshua Sagiv
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: Algorithms for concurrent operations (i.e., searches, insertions, and deletions) on \(B^*\)-trees are presented. These algorithms improve those given by \textit{P. L. Lehman} and \textit{S. B. Yao} [ACM Trans. Database Syst. 6, 650-670 (1981; Zbl 0465.68061)] since an insertion process has to lock only one node at any time (as opposed to locking simultaneously two or three nodes in ibid. Another improvement is the ability to compress the tree when some nodes become too sparse as a result of some deletions. Compressing the tree is done by a process that periodically scans the whole tree while running concurrently with the other operations. Alternatively, it is possible to initiate a compression process after each deletion that leaves a node less than half full. These compression processes may run concurrently with the other operations, and they scan only the nodes that have to be compressed. Each compression process has to lock simultaneously three nodes.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 4016242
zbMATH Keywords: data structure
zbMATH Keywords: databases
zbMATH Keywords: concurrent operations
zbMATH Keywords: searches
zbMATH Keywords: insertions
zbMATH Keywords: deletions
zbMATH Keywords: \(B^ *\)-trees
zbMATH Keywords: compression
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90021-8
OpenAlex ID: W2039071499
cites work: Organization and maintenance of large ordered indexes
cites work: Concurrency of operations on B-trees
cites work: Concurrent search and insertion in 2-3 trees
cites work: Concurrent manipulation of binary search trees
cites work: A New Method for Concurrency in B-Trees
cites work: Efficient locking for concurrent operations on B-trees
cites work: B-trees in a system with multiple users
cites work: Q3347338
description: scientific article; zbMATH DE number 4016242