External Memory Fully Persistent Search Trees

We present the first fully-persistent external-memory search tree achieving amortized I/O bounds matching those of the classic (ephemeral) B-tree by Bayer and McCreight. The insertion and deletion of a value in any version requires amortized O log 𝐵 𝑁 𝑣 I/Os and a range reporting query in any version requires worst-case O log 𝐵 𝑁 𝑣 + 𝐾/𝐵 I/Os, where 𝐾 is the number of values reported, 𝑁 𝑣 is the number of values in the version 𝑣 of the tree queried or updated, and 𝐵 is the external-memory block size. The data structure requires space linear in the total number of updates. Compared to the previous best bounds for fully persistent B-trees [Brodal, Sioutas, Tsakalidis, and Tsichlas, SODA 2012], this paper eliminates from the update bound an additive term of O log 2 𝐵 I/Os. This result matches the previous best bounds for the restricted case of partial persistent B-trees [Arge, Danner and Teh, JEA 2003]. Central to our approach is to consider the problem as a dynamic set of two-dimensional rectangles that can be merged and split.