Fully persistent B-trees

We present I/O-efficient fully persistent B-Trees that support range searches at any version in O (log B n + t/B ) I/Os and updates at any version in O (log B n + log 2 B ) amortized I/Os, using space O ( m/B ) disk blocks. By n we denote the number of elements in the accessed version, by m the total number of updates, by t the size of the query's output, and by B the disk block size. The result improves the previous fully persistent B-Trees of Lanka and Mays by a factor of O (log B m ) for the range query complexity and O (log B n ) for the update complexity. To achieve the result, we first present a new B-Tree implementation that supports searches and updates in O (log B n ) I/Os, using O ( n/B ) blocks of space. Moreover, every update makes in the worst case a constant number of modifications to the data structure. We make these B-Trees fully persistent using an I/O-efficient method for full persistence that is inspired by the node-splitting method of Driscoll et al. The method we present is interesting in its own right and can be applied to any external memory pointer based data structure with maximum in-degree d in bounded by a constant and out-degree bounded by O ( B ), where every node occupies a constant number of blocks on disk. The I/O-overhead per modification to the ephemeral structure is O ( d in log 2 B ) amortized I/Os, and the space overhead is O ( d in /B ) amortized blocks. Access to a field of an ephemeral block is supported in O (log 2 d in ) worst case I/Os.

Authors

• Gerth Stølting Brodal
• Konstantinos Tsakalidis
• Spyros Sioutas
• Kostas Tsichlas

Keywords

No keywords are indexed for this paper.