Fully persistent B-trees

Abstract We present efficient fully persistent B-trees in the I/O model with block size B that support range searches on t reported elements at any accessed version of size n in O ( log B ⁡ n + t / B ) I/Os and updates at any accessed version in O ( log B ⁡ n + log 2 ⁡ B ) amortized I/Os, using O ( m / B ) disk blocks after m updates. This improves both the query and update I/O-efficiency of the previous fully persistent B-trees of Lanka and Mays (ACM SIGMOD ICMD 1991). To achieve the result, we introduce an implementation for ephemeral B-trees that supports searches and updates in O ( log B ⁡ n ) I/Os, using O ( n / B ) blocks, where moreover every update makes a worst-case constant number of modifications to the structure. We make these B-trees fully persistent using an I/O-efficient method for full persistence, inspired by the node-splitting method of Driscoll et al. (JCSS 1989). Interesting in its own right, the method is generic enough to be applied to any external memory pointer-based data structure with maximum in-degree d i n and out-degree O ( B ) , where every node occupies a constant number of blocks on disk. For a user-specified parameter π = Ω ( d i n ) , we achieve O ( π B + log 2 ⁡ π ) I/O-overhead per access to a field of an ephemeral block and amortized O ( π B + log 2 ⁡ π + d i n π log 2 ⁡ B ) I/O-overhead and O ( 1 / B ) block space-overhead per modification to the ephemeral structure.