B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half

DOI10.1016/0022-0000(93)90020-WzbMATH Open0780.68016OpenAlexW2069205797MaRDI QIDQ686641FDOQ686641

Dennis Shasha, Theodore Johnson

Publication date: 10 October 1993

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(93)90020-w

Recommendations

• Deletion without rebalancing in multiway search trees
• Deletion without rebalancing in multiway search trees
• Space saving generalization of \(B\)-trees with \(2/3\) utilization
• Modeling B-tree insertion activity
• Some average performance measures for the B-tree

zbMATH Keywords

deletionsinsertions\(B\)-treesspace utilization

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• On random 2-3 trees
• The theory of fringe analysis and its application to 23 trees and b-trees
• Organization and maintenance of large ordered indexes
• Concurrency of operations on B-trees
• Modeling B-tree insertion activity
• Expected behaviour of \(B^+\)-trees under random insertions
• Unsafe operations in B-trees
• Space utilization and access path length in B-trees
• Storage utilization in B*-trees with a generalized overflow technique

Cited In (2)

• Deleting keys of B-trees in parallel
• Deletion without rebalancing in multiway search trees

This page was built for publication: \(B\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half

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