Deletion without rebalancing in multiway search trees

DOI10.1145/2540068zbMath1321.68237OpenAlexW2055701211MaRDI QIDQ2943570

Siddhartha Sen, Robert Endre Tarjan

Publication date: 3 September 2015

Published in: ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2540068

zbMATH Keywords

amortized complexityI/O modelB-treesexponential potential functiondatabase access methods

Mathematics Subject Classification ID

Searching and sorting (68P10) Database theory (68P15) Data structures (68P05)

Uses Software

• Oracle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(B\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half
• Unsafe operations in B-trees
• A new data structure for representing sorted lists
• B-trees in a system with multiple users
• Organization and maintenance of large ordered indexes
• Symmetric binary B-trees: Data structure and maintenance algorithms
• Rank-Balanced Trees
• Deletion without Rebalancing in Multiway Search Trees
• Amortized Computational Complexity
• Binary Search Trees of Bounded Balance

This page was built for publication: Deletion without rebalancing in multiway search trees