Fully persistent B-trees

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Gerth Stølting Brodal
  • Spyros Sioutas, University of Patras
  • ,
  • Konstantinos Tsakalidis, University of Liverpool
  • ,
  • Kostas Tsichlas, University of Patras

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(logB⁡n+t/B) I/Os and updates at any accessed version in O(logB⁡n+log2⁡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(logB⁡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 din and out-degree O(B), where every node occupies a constant number of blocks on disk. For a user-specified parameter π=Ω(din), we achieve [Formula Presented] I/O-overhead per access to a field of an ephemeral block and amortized [Formula Presented] I/O-overhead and O(1/B) block space-overhead per modification to the ephemeral structure.

Original languageEnglish
JournalTheoretical Computer Science
Volume841
Pages (from-to)10-26
ISSN0304-3975
DOIs
Publication statusPublished - Nov 2020

    Research areas

  • Big data, External memory, Persistent data structures, Range searching, Versioned data bases

See relations at Aarhus University Citationformats

ID: 197084269