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

DOI10.1016/0022-0000(93)90020-WzbMath0780.68016OpenAlexW2069205797MaRDI QIDQ686641

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

zbMATH Keywords

deletionsinsertions\(B\)-treesspace utilization

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (1)

Deletion without rebalancing in multiway search trees

Cites Work

• 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
• Concurrency of operations on B-trees
• On random 2-3 trees
• Organization and maintenance of large ordered indexes
• The theory of fringe analysis and its application to 23 trees and b-trees

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