Deletion without rebalancing in multiway search trees

Siddhartha Sen, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Many database systems that use a B + tree as 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. We conclude that rebalancing on deletion can be considered harmful.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages832-841
Number of pages10
DOIs
StatePublished - Dec 1 2009
Event20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States
Duration: Dec 16 2009Dec 18 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Symposium on Algorithms and Computation, ISAAC 2009
CountryUnited States
CityHonolulu, HI
Period12/16/0912/18/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Deletion without rebalancing in multiway search trees'. Together they form a unique fingerprint.

  • Cite this

    Sen, S., & Tarjan, R. E. (2009). Deletion without rebalancing in multiway search trees. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings (pp. 832-841). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS). https://doi.org/10.1007/978-3-642-10631-6_84