Fully Persistent B-trees

Gerth Stølting Brodal, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas

In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 602-614, 2012.

Abstract

We present I/O-efficient fully persistent B-Trees that support range searches at any version in O(logB n +t/B) I/Os and updates at any version in O(logB n + log2B) 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(logB m) for the range query complexity and O(logB n) for the update complexity. To achieve the result, we first present a new B-Tree implementation that supports searches and updates in O(logB 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 din 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(din log2B) amortized I/Os, and the space overhead is O(din/B) amortized blocks. Access to a field of an ephemeral block is supported in O(log2 din) worst case I/Os.

Copyright notice

Copyright © 2012 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda12.pdf (737 Kb)

DOI

siam.omnibooksonline.com/2012SODA/data/papers/498.pdf

Slides

soda12.pdf (507 Kb), soda12.pptx (311 Kb)

BIBTEX entry

@inproceedings{soda12,
  author = "Gerth St{\o}lting Brodal and Spyros Sioutas and Konstantinos Tsakalidis and Kostas Tsichlas",
  booktitle = "Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "siam.omnibooksonline.com/2012SODA/data/papers/498.pdf",
  isbn = "978-1-611972-11-5",
  issn = "1557-9468",
  pages = "602-614",
  title = "Fully Persistent B-trees",
  year = "2012"
}