Um Novo Algoritmo de Concorrência para Acesso e Compactação de Árvores-B
Resumo
Esse trabalho apresenta inicialmente uma breve (mas completa) resenha sobre as várias soluções do problema de controle de concorrência de processos percorrendo árvores-B. Em seguida é proposta uma nova solução que se caracteriza por empregar índices de tamanho variável, utilizar apenas um único tipo de bloqueio nas operações usuais de acesso à árvore, e empregar desdobramentos prévios, e concatenações e redistribuições adiadas. E apresentado um novo algoritmo de compactação e sua execução concorrente, utilizando um novo tipo de bloqueio.
Referências
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972. Primeiro artigo a abordar a estrutura de árvore-B, definindo-a, propondo e analisando os algoritmos de busca, inserção e remoção para um valor de índice e mostrando alguns resultados experimentais.
R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Informatica, 9(1):1-21, 1977. Sugere 4 soluções para o problema de concorrência nas árvores-B*", as quais fazem uso de 3 tipos de bloqueios.
R. Bayer and K. Unterauer. Prefix B-tree. ACM Transactions on Database Systems, 2(1):12-26, March 1977. Apresenta o conceito de árvore-B com pré-fixação simples e não simples, juntamente com os algoritmos para estas estruturas.
W. Boswell and A.L. Tharp. Advances in Computing and Information, volume 468 of Lecture Notes in Computer Science, chapter Alternatives to The B+-Tree, pages 266-274. Springer, May 1990. Exemplifica 2 estruturas de arquivos para aplicações que requerem acesso sequencial e direto: Bounded Disorder e Adaptive Hashing. Faz uma análise comparativa entre estas estruturas e a árvore-B+.
D. Comer. The Ubiquitous B-tree. Computing Surveys, 11(2):121-137, 1979. Este artigo é uma resenha (survey) abordando de forma sucinta muitos dos tópicos relacionados com o tema árvore-B.
T.H. Cormen, C.E. Leiserson, and R.L. Reivest. Introduction to Algorithms. The MIT Press and McGraw Hill Book Company, New York, 1990. Consultados em aspectos gerais sobre tipos de árvores de busca.
E.W. Dijkstra. The structure of the multi-programming system. Communications of the ACM, 11(5):341-346, May 1968. Introduz a noção de semáforos para manipular os problemas de concorrência.
C.S. Ellis. Concurrent search and insertion in 2-3-trees. Acta Informatica, 14(1):63-86, 1980. Apresenta 2 algoritmos que permitem um alto grau de concorréncia nas árvores-2-3 sem ocasionar deadlock (Bloqueio-2-3 e Pipeline-2-3).
L.J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th Annual Symposium Foundation of Computer Science, pages 8-21, 1978. Aborda uma técnica de coloração para binarizar árvores e torná-las sempre balanceadas. Propõe também um novo algoritmo de atualização para árvores-B, o qual executa prédesdobramentos nos nós durante a fase de busca.
M.A. Keller and G. Wiederhold. Concurrent use of B-trees with variable-length entries. Sigmod Records, 17(2):89-90, June 1988. Propõe uma solução para o problema de concorrência em árvores-B com valores de tamanho variável.
D.E. Knuth. The Art Computer Programming: Sorting and Searching, volume 3. Addison-Wesley Publishing Company, Reading, Massachusetts, 1973. Aborda as árvores-B e introduz a B*, bem como os desdobramentos de 2 para 3.
H.F. Korth and A. Silberchatz. Database System Concepts. Mc. Graw Hill Inc., New York, 1986. Consultado em aspectos de organização, implementação, projeto e seleção de arquivos utilizados em banco de dados, em particular para os arquivos indexados.
Y.S. Kwong and D. Wood. In Proc. MFCS, volume 88 of Lecture Notes in Computer Science, chapter Approaches to Concurrency in B-Trees, pages 402-413. Springer, 1980. Expõe os problemas de concorrência com árvores-B e analizam algumas soluções existentes.
Y.S. Kwong and D. Wood. In Proc. 4th International Symposium Programming, volume 83 of Lecture Notes in Computer Science, chapter Concurrent Operations in Large Ordered Indexes, pages 208-221. Springer, 1980. Apresenta soluções para o problema de concorrência nas árvores-B* e propõem uma nova estrutura denominada de árvore-T (uma árvore de árvores).
Y.S Kwong and D. Wood. A new method of concurrency in B-trees. IEEE Transactions on Software Engineering, SE-8(3):211-222, May 1982. Propõe uma solução para o problema de concorrência em árvores-B*", fazem uma comparação das várias soluções existentes e tratam o caso de concorrência dentro de um nó.
L. Lamport. Concurrent reading and writing. Communications of the ACM, 20(11):806811, November 1977. Exibe vários algoritmos para o problema de concorrência. Todos estes algoritmos permitem o compartilhamento dos dados, pois fazem uso da técnica de ler os dados em um sentido e escrevê-los em outro.
P.L. Lehman and S.B. Yao. Efficient locking for concurrent operations on B-tree. ACM Transactions on Database Systems, 6(4):650-670, December 1981. Propõe uma solugo de concorréncia para as árvores-B* fazendo uma ligeira modificação na estrutura e garantindo o bloqueio de um único nó em cada instante de um processo em execução.
E.R. Miller and L. Snyder. Multiple access to B-trees. In Proc. Conference Information Sciences and Systems, pages 400-407, John Hopkins University - Baltimore, March 1978. Trata do problema de concorrência em árvores-B sugerindo uma solução na qual os nós bloqueados estão a uma distância pequena daquele que sofrerá modificação.
E.R. Miller, N. Pippenger, A.L. Rosemberg, and L. Snyder. Optimal 2-3 trees. Siam Journal of Computing, 8(1):42-59, February 1979. Propõe um algoritmo de tempo linear para construir árvores-2-3 de espaço ótimo, isto é, baixas, a partir de um conjunto de itens e da determinação de um perfil para este conjunto. O algoritmo é facilmente adaptável para as árvores-B.
Y. Mond and Y. Raz. Concurrency control in B+-trees databases using preparatory operations. In Proc. of the 11th International Conference on Very Large Database, pages 331-334, Stockholm, 1985. Propõe um controle de concorrência para as árvores-B*" evitando um número elevado de nós bloqueados por cada processo em execução, através do uso de operações preparatórias que garantem a segurança dos nós para inserções e remoções.
S. Nagayama. Tabelas de Decisão e Implementação de Gerador I-M-E. Dissertação de Mestrado, Instituto de Matemática e Estatística - USP, São Paulo, 1990. Contém extensa resenha sobre tabelas de decisão, bem como a implementação do gerador de aplicações I-M-E.
J.R. Parr. An access method for concurrently sharing a B-tree index. Technical Report 36, University of Western Ontario, Departament of Computer Science, April 1977. Artigo não localizado (citado em [23]).
Y. Sagiv. Concurrent operations on B*-trees with overtacking. Journal of Computer and Systems Science, 33:275-296, 1986. Aperfeiçoou a solução proposta por Lehman e Yao [17] utilizando uma técnica de redistribuição denominada de compressão que pode ser utilizada concorrentemente com outras operações.
B. Samadi. B-trees in a system with multiple users. Inf. Processing Letters, 5(4):107-112, October 1976. Sugere uma solução para o problema de concorrência nas árvores-B fazendo uso da técnica padrão de semáforos.
R.M.F. Souza and O.S.F. Carvalho. Controle de concorrência em árvores-b. IVSimpósio Brasileiro de Arquitetura de Computadores - Processamento de Alto Desempenho (IV SBAC PAD), pages 397-412, 1992. Apresentam algoritmos de busca e inserção para o problema de concorrência nas árvoresB com elementos de tamanho variável. Estes algoritmos permitem o uso da técnica de overflow.
R.E. Wagner. Indexing design considerations. IBM System Journal, (4):351-367, 1973. Define os tipos de índices, as operações de inserção, remoção e atualização em arquivos de índices e propõe técnicas de compressão de caracteres para os valores dos índices e de enderaçamento relativo.
A. Zisman. A árvore-B e Uma Proposta de Implementação. Dissertação de Mestrado, Instituto de Matemática e Estatística - USP, São Paulo, 1993. Contém extensa resenha sobre árvores-B e uma proposta de implementação, com um novo algoritmo de concorrência e de compactação.
R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Informatica, 9(1):1-21, 1977. Sugere 4 soluções para o problema de concorrência nas árvores-B*", as quais fazem uso de 3 tipos de bloqueios.
R. Bayer and K. Unterauer. Prefix B-tree. ACM Transactions on Database Systems, 2(1):12-26, March 1977. Apresenta o conceito de árvore-B com pré-fixação simples e não simples, juntamente com os algoritmos para estas estruturas.
W. Boswell and A.L. Tharp. Advances in Computing and Information, volume 468 of Lecture Notes in Computer Science, chapter Alternatives to The B+-Tree, pages 266-274. Springer, May 1990. Exemplifica 2 estruturas de arquivos para aplicações que requerem acesso sequencial e direto: Bounded Disorder e Adaptive Hashing. Faz uma análise comparativa entre estas estruturas e a árvore-B+.
D. Comer. The Ubiquitous B-tree. Computing Surveys, 11(2):121-137, 1979. Este artigo é uma resenha (survey) abordando de forma sucinta muitos dos tópicos relacionados com o tema árvore-B.
T.H. Cormen, C.E. Leiserson, and R.L. Reivest. Introduction to Algorithms. The MIT Press and McGraw Hill Book Company, New York, 1990. Consultados em aspectos gerais sobre tipos de árvores de busca.
E.W. Dijkstra. The structure of the multi-programming system. Communications of the ACM, 11(5):341-346, May 1968. Introduz a noção de semáforos para manipular os problemas de concorrência.
C.S. Ellis. Concurrent search and insertion in 2-3-trees. Acta Informatica, 14(1):63-86, 1980. Apresenta 2 algoritmos que permitem um alto grau de concorréncia nas árvores-2-3 sem ocasionar deadlock (Bloqueio-2-3 e Pipeline-2-3).
L.J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th Annual Symposium Foundation of Computer Science, pages 8-21, 1978. Aborda uma técnica de coloração para binarizar árvores e torná-las sempre balanceadas. Propõe também um novo algoritmo de atualização para árvores-B, o qual executa prédesdobramentos nos nós durante a fase de busca.
M.A. Keller and G. Wiederhold. Concurrent use of B-trees with variable-length entries. Sigmod Records, 17(2):89-90, June 1988. Propõe uma solução para o problema de concorrência em árvores-B com valores de tamanho variável.
D.E. Knuth. The Art Computer Programming: Sorting and Searching, volume 3. Addison-Wesley Publishing Company, Reading, Massachusetts, 1973. Aborda as árvores-B e introduz a B*, bem como os desdobramentos de 2 para 3.
H.F. Korth and A. Silberchatz. Database System Concepts. Mc. Graw Hill Inc., New York, 1986. Consultado em aspectos de organização, implementação, projeto e seleção de arquivos utilizados em banco de dados, em particular para os arquivos indexados.
Y.S. Kwong and D. Wood. In Proc. MFCS, volume 88 of Lecture Notes in Computer Science, chapter Approaches to Concurrency in B-Trees, pages 402-413. Springer, 1980. Expõe os problemas de concorrência com árvores-B e analizam algumas soluções existentes.
Y.S. Kwong and D. Wood. In Proc. 4th International Symposium Programming, volume 83 of Lecture Notes in Computer Science, chapter Concurrent Operations in Large Ordered Indexes, pages 208-221. Springer, 1980. Apresenta soluções para o problema de concorrência nas árvores-B* e propõem uma nova estrutura denominada de árvore-T (uma árvore de árvores).
Y.S Kwong and D. Wood. A new method of concurrency in B-trees. IEEE Transactions on Software Engineering, SE-8(3):211-222, May 1982. Propõe uma solução para o problema de concorrência em árvores-B*", fazem uma comparação das várias soluções existentes e tratam o caso de concorrência dentro de um nó.
L. Lamport. Concurrent reading and writing. Communications of the ACM, 20(11):806811, November 1977. Exibe vários algoritmos para o problema de concorrência. Todos estes algoritmos permitem o compartilhamento dos dados, pois fazem uso da técnica de ler os dados em um sentido e escrevê-los em outro.
P.L. Lehman and S.B. Yao. Efficient locking for concurrent operations on B-tree. ACM Transactions on Database Systems, 6(4):650-670, December 1981. Propõe uma solugo de concorréncia para as árvores-B* fazendo uma ligeira modificação na estrutura e garantindo o bloqueio de um único nó em cada instante de um processo em execução.
E.R. Miller and L. Snyder. Multiple access to B-trees. In Proc. Conference Information Sciences and Systems, pages 400-407, John Hopkins University - Baltimore, March 1978. Trata do problema de concorrência em árvores-B sugerindo uma solução na qual os nós bloqueados estão a uma distância pequena daquele que sofrerá modificação.
E.R. Miller, N. Pippenger, A.L. Rosemberg, and L. Snyder. Optimal 2-3 trees. Siam Journal of Computing, 8(1):42-59, February 1979. Propõe um algoritmo de tempo linear para construir árvores-2-3 de espaço ótimo, isto é, baixas, a partir de um conjunto de itens e da determinação de um perfil para este conjunto. O algoritmo é facilmente adaptável para as árvores-B.
Y. Mond and Y. Raz. Concurrency control in B+-trees databases using preparatory operations. In Proc. of the 11th International Conference on Very Large Database, pages 331-334, Stockholm, 1985. Propõe um controle de concorrência para as árvores-B*" evitando um número elevado de nós bloqueados por cada processo em execução, através do uso de operações preparatórias que garantem a segurança dos nós para inserções e remoções.
S. Nagayama. Tabelas de Decisão e Implementação de Gerador I-M-E. Dissertação de Mestrado, Instituto de Matemática e Estatística - USP, São Paulo, 1990. Contém extensa resenha sobre tabelas de decisão, bem como a implementação do gerador de aplicações I-M-E.
J.R. Parr. An access method for concurrently sharing a B-tree index. Technical Report 36, University of Western Ontario, Departament of Computer Science, April 1977. Artigo não localizado (citado em [23]).
Y. Sagiv. Concurrent operations on B*-trees with overtacking. Journal of Computer and Systems Science, 33:275-296, 1986. Aperfeiçoou a solução proposta por Lehman e Yao [17] utilizando uma técnica de redistribuição denominada de compressão que pode ser utilizada concorrentemente com outras operações.
B. Samadi. B-trees in a system with multiple users. Inf. Processing Letters, 5(4):107-112, October 1976. Sugere uma solução para o problema de concorrência nas árvores-B fazendo uso da técnica padrão de semáforos.
R.M.F. Souza and O.S.F. Carvalho. Controle de concorrência em árvores-b. IVSimpósio Brasileiro de Arquitetura de Computadores - Processamento de Alto Desempenho (IV SBAC PAD), pages 397-412, 1992. Apresentam algoritmos de busca e inserção para o problema de concorrência nas árvoresB com elementos de tamanho variável. Estes algoritmos permitem o uso da técnica de overflow.
R.E. Wagner. Indexing design considerations. IBM System Journal, (4):351-367, 1973. Define os tipos de índices, as operações de inserção, remoção e atualização em arquivos de índices e propõe técnicas de compressão de caracteres para os valores dos índices e de enderaçamento relativo.
A. Zisman. A árvore-B e Uma Proposta de Implementação. Dissertação de Mestrado, Instituto de Matemática e Estatística - USP, São Paulo, 1993. Contém extensa resenha sobre árvores-B e uma proposta de implementação, com um novo algoritmo de concorrência e de compactação.
Publicado
07/09/1993
Como Citar
ZISMAN, A.; SETZER, V. W..
Um Novo Algoritmo de Concorrência para Acesso e Compactação de Árvores-B. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1993
.
p. 614-630.
DOI: https://doi.org/10.5753/sbac-pad.1993.23064.
