In [SPAA2007], define a streaming B-tree (or index) as one that supports updates in amortized @math IOs, and present a structure achieving amortized @math IOs and queries in @math IOs. We extend their result to the partially-persistent case. For a version @math , let @math be the number of keys accessible at @math and @math be the total number of updates. We give a data structure using space @math , supporting updates to a leaf version @math with @math amortized IOs and answering range queries returning @math elements with @math IOs on average (where the average is over all queries covering disjoint key ranges at a given version). This is the first persistent streaming' index we are aware of, i.e. that supports updates in @math IOs and supports efficient range queries.
Becker @cite_10 presented the multiversion B-tree (MVBT), which solves the space blowup problem. It achieves the same query and update bounds with @math space, and is partially-persistent. 115861 developed two fully-persistent B-tree variants based on variants of the techniques from @cite_6 , but for both variants, either there is a large space blowup, or range queries may be far from optimal. Recently, @cite_3 presented a fully-persistent B-tree that uses linear space, and achieves roughly the same update query bounds (within a small factor) as the MVBT and the CoW B-tree. These results are summarized in Table .
@cite_3 @cite_10 @cite_6
2055385473 2142947709
In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others. Abstract This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and efficient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O (1) space bounds for insertion and deletion.