Controle de Concorrência em Árvores-B
Resumo
Existem na literatura vários algoritmos para o acesso concorrente a árvores-B. Estes algoritmos foram classificados em algoritmos conservadores e algoritmos agressivos. Este artigo descreve novos algoritmos para o acesso concorrente a árvores-B que podem ser classificados como híbridos, pois adotam a postura agressiva durante o caminhamento na árvore e a postura conservadora durante a reestruturação da árvore.
Referências
ANSI/MDC X11.1, "Programming Languages - MUMPS", 1990.
Bayer R., & Unterauer, K., "Prefix B-Trees", ACM Trans. on Database Systems, vol. 2, no. 1, Mar 1977.
Bayer R., Heller, H. & Reiser, A., "Parallelism and Recovery in Database Systems", ACM Trans. on Database Systems, vol. 5, no. 2, Jun 1980.
Bernstein, P., Hadzilacos, V. & Goodman, N., "Concurrency Control and Recovery in Database Systems", Addison Wesley, 1987.
Comer, D., "The Ubiquitous B-Tree", ACM Computing Surveys, vol. 11, no. 2, Jun 1979.
Eswaram, K. et al., "The Notions of Consistency and Predicate Locks in a Database System", CACM, vol. 19, no. 11, Nov 1976.
Gray, J., "Notes on Data Base Operating Systems", IBM Research Report, Fev 1978.
Kedem, Z. & Silberschatz, A., "Locking Protocols: From Exclusive to Shared Locks", Journal of the ACM, vol. 30, no. 4, Out 1983.
Kung, H. & Lehman, P., "Concurrent Manipulation of Binary Search Trees", ACM Trans. on Database Systems, vol. 5, no. 5, Set 1980.
Kwong, Y., & Wood, D., "A New Method for Concurrency in B-Trees", IEEE Trans. on Software Engineering, vol. SE-8, no. 3, Mar 1982.
Lehman, P. & Yao, S., "Efficient Locking for Concurrent Operations on B-Trees", ACM Trans. on Database Systems, vol. 6, no. 4, Dez 1981.
Manber, U. & Ladner, R., "Concurrency Control In a Dynamic Search Structure", ACM Trans. on Database Systems, vol. 9, no. 3, Set 1984.
McCreight, E., "Pagination of B*-Trees with Variable-Length Records", CACM, vol. 20, no. 9, Set 1977.
Mohan, C., "ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes", IBM Research Report, Set 1989.
Papadimitriou, C., "The Theory of Database Concurrency Control", Computer Science Press, 1986.
Wagner, R., "Indexing Design Considerations", IBM Systems Journal no. 4, 1978.
Wirth, N., "Algorithms + Data Structures = Programs", Prentice-Hall, 1976.
Bayer R., & Unterauer, K., "Prefix B-Trees", ACM Trans. on Database Systems, vol. 2, no. 1, Mar 1977.
Bayer R., Heller, H. & Reiser, A., "Parallelism and Recovery in Database Systems", ACM Trans. on Database Systems, vol. 5, no. 2, Jun 1980.
Bernstein, P., Hadzilacos, V. & Goodman, N., "Concurrency Control and Recovery in Database Systems", Addison Wesley, 1987.
Comer, D., "The Ubiquitous B-Tree", ACM Computing Surveys, vol. 11, no. 2, Jun 1979.
Eswaram, K. et al., "The Notions of Consistency and Predicate Locks in a Database System", CACM, vol. 19, no. 11, Nov 1976.
Gray, J., "Notes on Data Base Operating Systems", IBM Research Report, Fev 1978.
Kedem, Z. & Silberschatz, A., "Locking Protocols: From Exclusive to Shared Locks", Journal of the ACM, vol. 30, no. 4, Out 1983.
Kung, H. & Lehman, P., "Concurrent Manipulation of Binary Search Trees", ACM Trans. on Database Systems, vol. 5, no. 5, Set 1980.
Kwong, Y., & Wood, D., "A New Method for Concurrency in B-Trees", IEEE Trans. on Software Engineering, vol. SE-8, no. 3, Mar 1982.
Lehman, P. & Yao, S., "Efficient Locking for Concurrent Operations on B-Trees", ACM Trans. on Database Systems, vol. 6, no. 4, Dez 1981.
Manber, U. & Ladner, R., "Concurrency Control In a Dynamic Search Structure", ACM Trans. on Database Systems, vol. 9, no. 3, Set 1984.
McCreight, E., "Pagination of B*-Trees with Variable-Length Records", CACM, vol. 20, no. 9, Set 1977.
Mohan, C., "ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes", IBM Research Report, Set 1989.
Papadimitriou, C., "The Theory of Database Concurrency Control", Computer Science Press, 1986.
Wagner, R., "Indexing Design Considerations", IBM Systems Journal no. 4, 1978.
Wirth, N., "Algorithms + Data Structures = Programs", Prentice-Hall, 1976.
Publicado
26/10/1992
Como Citar
SOUZA, Roberto M. F.; CARVALHO, Osvaldo S. F..
Controle de Concorrência em Árvores-B. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 4. , 1992, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1992
.
p. 397-412.
DOI: https://doi.org/10.5753/sbac-pad.1992.22724.
