{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:32Z","timestamp":1763468192722,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0830676 and CCF-0832797"],"award-info":[{"award-number":["CCF-0830676 and CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2006204"],"award-info":[{"award-number":["2006204"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            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\n            <jats:italic>O<\/jats:italic>\n            (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.\n          <\/jats:p>","DOI":"10.1145\/2540068","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Deletion without rebalancing in multiway search trees"],"prefix":"10.1145","volume":"39","author":[{"given":"Siddhartha","family":"Sen","sequence":"first","affiliation":[{"name":"Microsoft Research, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University and Microsoft Research, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1,6]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"3","author":"Adelson-Velskii G. M.","year":"1962","unstructured":"G. M. Adelson-Velskii and E. M. Landis . 1962 . An algorithm for the organization of information . Sov. Math. Dokl. 3 , 1259 -- 1262 . G. M. Adelson-Velskii and E. M. Landis. 1962. An algorithm for the organization of information. Sov. Math. Dokl. 3, 1259--1262.","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645929.672716"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734714.1734731"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_8_1","volume-title":"Transaction Processing: Concepts and Techniques. Morgan Kaufmann","author":"Gray J.","year":"1993","unstructured":"J. Gray and A. Reuter (Eds.). 1993 . Transaction Processing: Concepts and Techniques. Morgan Kaufmann , San Mateo, CA . 851--876. J. Gray and A. Reuter (Eds.). 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, San Mateo, CA. 851--876."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_31"},{"key":"e_1_2_1_11_1","article-title":"Rank-balanced trees. ACM","author":"Haeupler Bernhard","year":"2014","unstructured":"Bernhard Haeupler , Siddhartha Sen , and Robert E. Tarjan . 2014 . Rank-balanced trees. ACM Trans. Algorithms. To appear. Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. 2014. Rank-balanced trees. ACM Trans. Algorithms. To appear.","journal-title":"Trans. Algorithms. To appear."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the GI-Conference on Theoretical Computer Science. Lecture Notes in Computer Science","volume":"104","author":"Huddleston S.","unstructured":"S. Huddleston and K. Mehlhorn . 1981. Robust balancing in B-trees . In Proceedings of the GI-Conference on Theoretical Computer Science. Lecture Notes in Computer Science , vol. 104 , Springer-Verlag, Berlin, 234--244. S. Huddleston and K. Mehlhorn. 1981. Robust balancing in B-trees. In Proceedings of the GI-Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol. 104, Springer-Verlag, Berlin, 234--244."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/202660.202666"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73745"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90020-W"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90101-0"},{"volume-title":"Managing simultaneous operations in large ordered indexes. Tech. rep. Technische Universit\u00e4t M\u00fcnchen","author":"Metzger J.","key":"e_1_2_1_18_1","unstructured":"J. Metzger . 1975. Managing simultaneous operations in large ordered indexes. Tech. rep. Technische Universit\u00e4t M\u00fcnchen , Institut f\u00fcr Informatik, TUM-Math . J. Metzger. 1975. Managing simultaneous operations in large ordered indexes. Tech. rep. Technische Universit\u00e4t M\u00fcnchen, Institut f\u00fcr Informatik, TUM-Math."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/141484.130338"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1982160100511"},{"volume-title":"Berkeley DB. In Proceedings of the USENIX Annual Technical Conference (ATC), FREENIX Track. 183--191","author":"Olson Michael A.","key":"e_1_2_1_22_1","unstructured":"Michael A. Olson , Keith Bostic , and Margo I. Seltzer . 1999 . Berkeley DB. In Proceedings of the USENIX Annual Technical Conference (ATC), FREENIX Track. 183--191 . Michael A. Olson, Keith Bostic, and Margo I. Seltzer. 1999. Berkeley DB. In Proceedings of the USENIX Annual Technical Conference (ATC), FREENIX Track. 183--191."},{"key":"e_1_2_1_23_1","volume-title":"Seltzer","author":"Olson Michael A.","year":"2000","unstructured":"Michael A. Olson , Keith Bostic , and Margo I . Seltzer . 2000 . Berkeley DB. http:\/\/www.oracle.com\/us\/products\/database\/berkeley-db\/overview\/index.html. Michael A. Olson, Keith Bostic, and Margo I. Seltzer. 2000. Berkeley DB. http:\/\/www.oracle.com\/us\/products\/database\/berkeley-db\/overview\/index.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90005-3"},{"key":"e_1_2_1_25_1","unstructured":"Robert Sedgewick. 2008. Left-leaning red-black trees. http:\/\/www.cs.princeton.edu\/&sim;rs\/talks\/LLRB\/LLRB.pdf.  Robert Sedgewick. 2008. Left-leaning red-black trees. http:\/\/www.cs.princeton.edu\/&sim;rs\/talks\/LLRB\/LLRB.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_84"},{"key":"e_1_2_1_27_1","volume-title":"Tarjan","author":"Sen Siddhartha","year":"2010","unstructured":"Siddhartha Sen and Robert E . Tarjan . 2010 . Deletion without rebalancing in balanced binary trees. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1490--1499. Siddhartha Sen and Robert E. Tarjan. 2010. Deletion without rebalancing in balanced binary trees. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1490--1499."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289145"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2540068","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2540068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:33Z","timestamp":1750234233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2540068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2540068"],"URL":"https:\/\/doi.org\/10.1145\/2540068","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}