2026-07-22T10:25:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24278 2025-11-12T13:39:45Z ddc:004 open_access

B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load Safavi, Roodabeh Seybold, Martin P. Unique Representation Randomization Top-Down Analysis Block Search Tree Write-Efficiency Storage-Efficiency Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called "strongly history independent" structures in the literature. We introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2]. Thus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roodabeh Safavi and Martin P. Seybold 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.47 urn:nbn:de:0030-drops-242786 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.47 eng https://creativecommons.org/licenses/by/4.0/legalcode