Fully Persistent B+-trees.

Sitaram Lanka, Eric Mays: Fully Persistent B+-trees. SIGMOD Conference 1991: 426-435

@inproceedings{DBLP:conf/sigmod/LankaM91,
  author    = {Sitaram Lanka and
               Eric Mays},
  editor    = {James Clifford and
               Roger King},
  title     = {Fully Persistent B+-trees},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {426-435},
  ee        = {http://doi.acm.org/10.1145/115790.115861, db/conf/sigmod/LankaM91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991

, SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1040 KB]

References

[1]: Hong-Tai Chou, Won Kim: A Unifying Framework for Version Control in a CAD Environment. VLDB 1986: 336-344
[2]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[3]: James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38(1): 86-124(1989)
[4]: Gerald Held, Michael Stonebraker: B-trees Re-examined. Commun. ACM 21(2): 139-143(1978)
[5]: Randy H. Katz, Tobin J. Lehman: Database Support for Versions and Alternatives of Large Design Files. IEEE Trans. Software Eng. 10(2): 191-200(1984)
[6]: Eric Mays, Sitaram Lanka, Robert Dionne, Robert A. Weida: A Persistent Store for Large Shared Knowledge Bases. IEEE Trans. Knowl. Data Eng. 3(1): 33-41(1991)
[7]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents