dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Amma85]
...
[Come79]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fish86]
...
[Horw85]
...
[Kjel84]
Peter Kjellberg, Torben U. Zahle: Cascade Hashing. VLDB 1984: 481-492 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Knut73]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lars80]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lehm86a]
...
[Lehm86b]
Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lela85]
...
[Lint84]
Mark A. Linton: Implementing Relational Views of Programs. Software Development Environments (SDE) 1984: 132-140 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Litw80]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mull84]
James K. Mullin: Unified Dynamic Hashing. VLDB 1984: 473-480 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shap86]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Snod84]
Richard T. Snodgrass: Monitoring in a Software Development Environment: A Relational Approach. Software Development Environments (SDE) 1984: 124-131 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Warr81]
David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Will84]
Dan E. Willard: New Trie Data Structures Which Support Very Fast Search Operations. J. Comput. Syst. Sci. 28(3): 379-394(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Jun Rao, Kenneth A. Ross: Making B+-Trees Cache Conscious in Main Memory. SIGMOD Conference 2000: 475-486
  2. Peter A. Boncz, Martin L. Kersten: MIL Primitives for Querying a Fragmented World. VLDB J. 8(2): 101-119(1999)
  3. Jun Rao, Kenneth A. Ross: Cache Conscious Indexing for Decision-Support in Main Memory. VLDB 1999: 78-89
  4. Peter A. Boncz, Stefan Manegold, Martin L. Kersten: Database Architecture Optimized for the New Bottleneck: Memory Access. VLDB 1999: 54-65
  5. Times-Ten Team: In-Memory Data Management for Consumer Transactions The Times-Ten Approach. SIGMOD Conference 1999: 528-529
  6. Jang Ho Park, Yong Sik Kwon, Ki Hong Kim, Sangho Lee, Byoung Dae Park, Sang Kyun Cha: Xmas: An Extensible Main-Memory Storage System for High-Performance Applications. SIGMOD Conference 1998: 578-580
  7. Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis W. Leinbaugh, Abraham Silberschatz, S. Sudarshan: Logical and Physical Versioning in Main Memory Databases. VLDB 1997: 86-95
  8. Peter A. Boncz, Wilko Quak, Martin L. Kersten: Monet And Its Geographic Extensions: A Novel Approach to High Performance GIS Processing. EDBT 1996: 147-166
  9. Byung Suk Lee, Gio Wiederhold: Efficiently Instantiating View-Objects From Remote Relational Databases. VLDB J. 3(3): 289-323(1994)
  10. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  11. Tobin J. Lehman, Eugene J. Shekita, Luis-Felipe Cabrera: An Evaluation of Starburst's Memory Resident Storage Component. IEEE Trans. Knowl. Data Eng. 4(6): 555-566(1992)
  12. Hector Garcia-Molina, Kenneth Salem: Main Memory Database Systems: An Overview. IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992)
  13. Vibby Gottemukkala, Tobin J. Lehman: Locking and Latching in a Memory-Resident Database System. VLDB 1992: 533-544
  14. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
  15. Philippe Pucheral, Jean-Marc Thévenin: Pipelined Query Processing in the DBGraph Storage Model. EDBT 1992: 516-533
  16. Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990)
  17. Philippe Pucheral, Jean-Marc Thévenin, Patrick Valduriez: Efficient Main Memory Data Management Using the DBGraph Storage Model. VLDB 1990: 683-695
  18. Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146
  19. Tobin J. Lehman, Michael J. Carey: A Recovery Algorithm for A High-Performance Memory-Resident Database System. SIGMOD Conference 1987: 104-117
  20. Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250
  21. Dina Bitton: The Effect of Large Main memory on Database Systems. SIGMOD Conference 1986: 337-339

Last update Fri Sep 14 17:38:08 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page