An asymptotically optimal multiversion B-tree

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.

Authors and Affiliations

1. Institut für Theoretische Informatik, ETH Zentrum, CH-8092 Zürich, Switzerland¶ Tel. ++41-1-63-27400, Fax ++41-1-63-21172, email: widmayer@inf.ethz.ch , , , , , , CH

   Peter Widmayer

2. isys software gmbh, Ensisheimer Str. 2a, D–79110 Freiburg, Germany , , , , , , DE

   Bruno Becker, Stephan Gschwind & Thomas Ohler

3. Philipps-Universität Marburg, Fachbereich Mathematik, Fachgebiet Informatik, Hans-Meerwein-Strasse, D–35032 Marburg, Germany , , , , , , DE

   Bernhard Seeger

Reprints and permissions