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

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.

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

**Online version**

soda12.pdf (737 Kb)

**DOI**

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

**BIBT _{E}X 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 = "10.1137/1.9781611973099.51", isbn = "978-1-611972-11-5", issn = "1557-9468", pages = "602-614", title = "Fully Persistent B-trees", year = "2012" }