Extendible Hashing for Concurrent Operations and Distributed Data.

@inproceedings{DBLP:conf/pods/Ellis83,
  author    = {Carla Schlatter Ellis},
  title     = {Extendible Hashing for Concurrent Operations and Distributed
               Data},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {106-116},
  ee        = {http://doi.acm.org/10.1145/588058.588072, db/conf/pods/Ellis83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The extendible hash file is a dynamic data structure that is an alternative to B-trees for use as a database index. While there have been many algorithms proposed to allow concurrent access to B-trees similar solutions for extendible hash files have not appeared. In this paper, we present solutions to allow for concurrency that are based on locking protocols and minor modifications in the data structure.

Another question that deserves consideration is whether these indexing structures can be adapted for use in a distributed database. Among the motivations for distributing data are increased availability and ease of growth, however, unless data structures in the access path are designed to support those goals, they may not be realized. We describe some first attempts at adapting extendible hash files for distributed data.

Copyright © 1983 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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[Bayer 77]

Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX

[Ellis 82]

...

[Ellis 80]

Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX

[Fagin 79]

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) BibTeX

[Gifford 79]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[Kwong 79]

Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX

[Lehman 81]

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX

[Miller 78]

...

[Rashid 80]

...

[Stonebraker 79]

Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) BibTeX

[Tomas 79]

Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX

Referenced by

1. C. Mohan: ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. ICDE 1993: 243-252
2. Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
3. Akhil Kumar, Michael Stonebraker: Semantics Based Transaction Management Techniques for Replicated Data. SIGMOD Conference 1988: 117-125
4. Vladimir Lanin, Dennis Shasha: Concurrent Set Manipulation without Locking. PODS 1988: 211-220
5. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335
6. Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)
7. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
   Contents
8. Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19
9. Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7