A Study of Index Structures for Main Memory Database Management Systems.

Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303

@inproceedings{DBLP:conf/vldb/LehmanC86,
  author    = {Tobin J. Lehman and
               Michael J. Carey},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {A Study of Index Structures for Main Memory Database Management
               Systems},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {294-303},
  ee        = {db/conf/vldb/LehmanC86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

One approach to achieving high performance in a database management system is to store the database in main memory rather than on disk. One can then design new data structures and algorithms oriented towards making efficient use of CPU cycles and memory space rather than minimizing disk accesses and using disk space efficiently. In this paper we present some results on index structures from an ongoing study of main memory database management systems. We propose a new index structure, the T Tree, and we compare it to existing index structures in a main memory database environment. Our results indicate that the T Tree provides good overall performance in main memory.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" 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/vldb7588 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

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents

References

[Aho74]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
[Amma85]: ...
[Come79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[DeWi84]: David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8
[Elha84]: Klaus Elhardt, Rudolf Bayer: A Database Cache for High Performance and Fast Restart in Database Systems. ACM Trans. Database Syst. 9(4): 503-525(1984)
[Fagi79]: Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979)
[Fish86]: ...
[Horw85]: ...
[Kjel84]: Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492
[Knut73]: Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
[Lars80]: Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232
[Lehm86a]: ...
[Lehm86b]: Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250
[Lela85]: ...
[Lint84]: Mark A. Linton: Implementing Relational Views of Programs. Software Development Environments (SDE) 1984: 132-140
[Litw80]: Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223
[Mull84]: James K. Mullin: Unified Dynamic Hashing. VLDB 1984: 473-480
[Shap86]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[Snod84]: Richard T. Snodgrass: Monitoring in a Software Development Environment: A Relational Approach. Software Development Environments (SDE) 1984: 124-131
[Warr81]: David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281
[Will84]: Dan E. Willard: New Trie Data Structures Which Support Very Fast Search Operations. J. Comput. Syst. Sci. 28(3): 379-394(1984)