2025/03/11 by Brodal, Gerth Stølting, Rysgaard, Casper Moldrup, Svenning, Rolf
#Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.08211
We present an optimal partially-persistent external-memory search tree with amortized I/O bounds matching those achieved by the non-persistent Bε-tree by Brodal and Fagerberg [SODA 2003]. In a partially-persistent data structure each update creates a new version of the data structure, where all past versions can be queried, but only the current version can be updated. All operations should be efficient with respect to the size Nv of the accessed version v. For any parameter 0<ε<1, our data structure supports insertions and deletions in amortized O (\frac1ε B1-εlogB Nv) I/Os, where B is the external-memory block size. It also supports successor and range reporting queries in amortized O ((1)/(ε)logB Nv+K/B) I/Os, where K is the number of values reported. The space usage of the data structure is linear in the total number of updates. We make the standard and minimal assumption that the internal memory has size M ≥ 2B. The previous state-of-the-art external-memory partially-persistent search tree by Arge, Danner and Teh [JEA 2003] supports all operations in worst-case O (logB Nv+K/B) I/Os, matching the bounds achieved by the classical B-tree by Bayer and McCreight [Acta Informatica 1972]. Our data structure successfully combines buffering updates with partial persistence. The I/O bounds can also be achieved in the worst-case sense, by slightly modifying our data structure and under the requirement that the memory size M = Ω (B1-εlog2(maxv Nv)). The worst-case result slightly improves the memory requirement over the previous ephemeral external-memory dictionary by Das, Iacono, and Nekrich (ISAAC 2022), who achieved matching worst-case I/O bounds but required M=Ω (BlogB N).