Deletion without rebalancing in multiway search trees

DOI10.1145/2540068MaRDI QIDQ2943570zbMATH OpenOpenAlexFDO

Authors Siddhartha Sen, Robert E. 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

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

Recommendations

• Deletion without rebalancing in multiway search trees
• Deletion without rebalancing in binary search trees
• Deletion without rebalancing in balanced binary trees
• scientific article; zbMATH DE number 3928331
• B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half

Cites work

• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 3716818 (Why is no real title available?)
• A new data structure for representing sorted lists
• Amortized Computational Complexity
• B-trees in a system with multiple users
• Binary Search Trees of Bounded Balance
• Deletion without rebalancing in balanced binary trees
• Deletion without rebalancing in multiway search trees
• Organization and maintenance of large ordered indexes
• Rank-Balanced Trees
• Symmetric binary B-trees: Data structure and maintenance algorithms
• Unsafe operations in B-trees
• B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half

Cited in

(11)

• B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half
• Deletion without rebalancing in balanced binary trees
• Deletion without rebalancing in non-blocking binary search trees
• Deletion without rebalancing in binary search trees
• Insertions and deletions in B-trees
• Deletion: The curse of the red-black tree
• Deletion without rebalancing in multiway search trees
• Randomness Preserving Deletions on Special Binary Search Trees
• Optimal Key Tree Structure for Deleting Two or More Leaves
• Maintenance of the pre-large trees for record deletion
• Unbalanced multiway trees improved by partial expansions

Describes a project that uses

Uses Software

• Oracle

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

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