Buffered Partially-Persistent External-Memory Search Trees

Gerth Stølting Brodal, Casper Moldrup Rysgaard, Rolf Svenning

We present an optimal partially-persistent external-memory search tree with amortized I/O bounds matching those achieved by the non-persistent $B^{\epsilon }$-tree by Brodal and…