2026-07-20T14:51:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24194 2025-11-12T13:34:27Z ddc:004 open_access

Lazy B-Trees Rysgaard, Casper Moldrup Wild, Sebastian B-tree lazy search trees lazy updates external memory deferred data structures database cracking Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient priority queues and binary search trees - automatically, depending on actual use; no adjustments are necessary to the data structure to realize the cost savings. In this paper, we design lazy B-trees, a variant of lazy search trees suitable for external memory that generalizes the speedup of B-trees over binary search trees wrt. input/output operations to the same smooth interpolation regime. A key technical difficulty to overcome is the lack of a (fully satisfactory) external variant of biased search trees, on which lazy search trees crucially rely. We give a construction for a subset of performance guarantees sufficient to realize external-memory lazy search trees, which we deem of independent interest. As one special case, lazy B-trees can be used as an external-memory priority queue, in which case they are competitive with some tailor-made heaps; indeed, they offer faster decrease-key and insert operations than known data structures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Casper Moldrup Rysgaard and Sebastian Wild 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.87 urn:nbn:de:0030-drops-241949 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.87 eng https://creativecommons.org/licenses/by/4.0/legalcode