Skip to main content

Deletion without rebalancing in multiway search trees

Author(s): Sen, Siddhartha; Tarjan, Robert E

To refer to this page use:
Abstract: Some database systems that use a form of B-tree for the underlying data structure do not do rebalancing on deletion. This means that a bad sequence of deletions can create a very unbalanced tree. Yet such databases perform well in practice. Avoidance of rebalancing on deletion has been justified empirically and by average-case analysis, but to our knowledge, no worst-case analysis has been done. We do such an analysis. We show that the tree height remains logarithmic in the number of insertions, independent of the number of deletions. Furthermore, the amortized time for an insertion or deletion, excluding the search time, is O(1), and nodes are modified by insertions and deletions with a frequency that is exponentially small in their height. The latter results do not hold for standard B-trees. By adding periodic rebuilding of the tree, we obtain a data structure that is theoretically superior to standard B-trees in many ways. Our results suggest that rebalancing on deletion not only is unnecessary but may be harmful.
Publication Date: Jan-2014
Citation: Sen, Siddhartha, and Robert E. Tarjan. "Deletion without rebalancing in multiway search trees." ACM Transactions on Database Systems 39, no. 1 (2014): pp. 8:1-8:14. doi:10.1145/2540068
DOI: 10.1145/2540068
ISSN: 0362-5915
EISSN: 1557-4644
Pages: 8:1 - 8:14
Type of Material: Journal Article
Journal/Proceeding Title: ACM Transactions on Database Systems
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.