Concurrent operations on B^ *-trees with overtaking

DOI10.1016/0022-0000(86)90021-8MaRDI QIDQ579974zbMATH OpenOpenAlexFDO

Authors Yehoshua Sagiv

Publication date 1986

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(86)90021-8

zbMATH Keywords

\(B^ *\)-treescompressionconcurrent operationsdata structuredatabasesdeletionsinsertionssearches

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

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.

Recommendations

• A rigorous analysis of concurrent operations on B-trees
• scientific article; zbMATH DE number 2033285
• String Processing and Information Retrieval
• Restructuring the concurrent B\(^{+}\)-tree with non-blocked search operations
• scientific article; zbMATH DE number 2241920

Cites work

• A New Method for Concurrency in B-Trees
• B-trees in a system with multiple users
• Concurrency of operations on B-trees
• Concurrent manipulation of binary search trees
• Concurrent search and insertion in 2-3 trees
• Efficient locking for concurrent operations on B-trees
• scientific article; zbMATH DE number 3890770 (Why is no real title available?)
• Organization and maintenance of large ordered indexes

Cited in

(18)

• Concurrency and trie hashing
• Unsafe operations in B-trees
• \(B\)-trees with lazy parent split
• Amortization results for chromatic search trees, with an application to priority queues
• Operation-specific locking in balanced structures
• Restructuring the concurrent B\(^{+}\)-tree with non-blocked search operations
• ASA-graphs for efficient data representation and processing
• On the correctness of a lock-free compression-based elastic mechanism for a hash trie design
• Relaxed avl trees, main-memory databases and concurrency
• scientific article; zbMATH DE number 2033285 (Why is no real title available?)
• Variants of (a,b)-trees with relaxed balance
• String Processing and Information Retrieval
• scientific article; zbMATH DE number 2241920 (Why is no real title available?)
• A process-calculus analysis of concurrent operations on B-trees
• A rigorous analysis of concurrent operations on B-trees
• Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines
• Global parallel index for multi-processors database systems
• Distributing a \(B^+\)-tree in a loosely coupled environment

This page was built for publication: Concurrent operations on \(B^ *\)-trees with overtaking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579974)