TY - GEN
T1 - Deletion without rebalancing in multiway search trees
AU - Sen, Siddhartha
AU - Tarjan, Robert E.
N1 - Funding Information:
Research at Princeton University partially supported by NSF grants CCF-0830676 and CCF-0832797 and US-Israel Binational Science Foundation grant 2006204. The information contained herein does not necessarily reflect the opinion or policy of the federal government and no official endorsement should be inferred.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=75649121491&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=75649121491&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10631-6_84
DO - 10.1007/978-3-642-10631-6_84
M3 - Conference contribution
AN - SCOPUS:75649121491
SN - 3642106307
SN - 9783642106309
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 832
EP - 841
BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009
Y2 - 16 December 2009 through 18 December 2009
ER -