Fully persistent B+-trees

In this paper, we investigate efficiently maintaining multiple versions of B+-trees. We propose two main schemes: the fat field method and the pure version block method. The former method is suitable for range queries or whenever lookup on a released version is an important issue. The latter method is more space efficient, and is suitable when the total number of keys from all the versions are small. © 1991, ACM. All rights reserved.