Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Árvores B+ Lívia N. Andrade Árvores B+ A árvore B+ é uma variação da estrutura básica da árvore B. Uma árvore B+ é uma árvore B mais uma lista duplamente encadeada que liga as páginas folhas; Em uma árvore B+, todos os registros são armazenados no último nível (páginas folha). Os níveis acima do último nível constituem um índice cuja organização é a organização de uma árvore B. 2 Árvores B+ A figura ilustra a separação lógica entre o índice e os registros que constituem o arquivo propriamente dito. Árvore B ... Acesso Sequencial Índice Só aparecem as chaves, sem nenhuma informação associada Registros 3 Árvores B+ A figura ilustra a separação lógica entre o índice e os registros que constituem o arquivo propriamente dito. Árvore B ... Acesso Sequencial Índice Registros As páginas folha são conectadas da esquerda para a direita, acesso mais eficiente via índice. 4 Árvores B+ - Características A pesquisa é semelhante à pesquisa em árvore B; A pesquisa inicia-se na raiz da árvore e continua até uma página folha; Como todos os registros residem nas folhas, a pesquisa não pára se a chave procurada for encontrada em uma página índice. O apontador da direita é seguido até que se encontre uma página folha. 5 Exemplo Os elementos 29, 60 e 75 aparecem no índice e em registros do arquivo. Os valores encontrados ao longo do caminho são irrelevantes desde que eles conduzam à página folha correta. 29 33 9 18 19 22 45 6 29 60 75 1 4 5 75 80 60 65 70 50 52 Índice 6 Árvores B+ - Características Como não há necessidade do uso de apontadores nas páginas folha, é possível utilizar esse espaço para armazenar uma quantidade maior de registros em cada página folha. Valor de m diferente para as páginas folha. Isto não cria nenhum problema para os algoritmos de inserção, pois as metades de uma página que está sendo particionada permanecem no mesmo nível da página original antes da partição (algo semelhante acontece na remoção de registros) 7 Estrutura de dados 8 Estrutura de dados 9 Operações em Árvore B+ Pesquisa Inserção Remoção 10 Pesquisa – código C Página interna A página em questão é interna ou externa? Página externa 11 Pesquisa – código C i for menor que a quantidade de elementos nesta página interna X for maior do que o elemento que ocupa a posição i-1 no vetor de elementos 12 Pesquisa – código C se X for menor que o elemento, chama recursivamente o Pesquisa para seu filho da esquerda 13 Pesquisa – código C Se a comparação ocorre com o último elemento da página e o valor procurado é maior, chama Pesquisa recursivamente para o filho da direita 14 Pesquisa – código C i for menor que a quantidade de elementos na página externa X for maior do que o elemento que ocupa a posição i-1 no vetor de elementos 15 Pesquisa – código C X for o elemento que está sendo pesquisado 16 Exemplo 1: Pesquisa árvore B+ 29 33 9 18 19 22 45 6 29 60 75 1 4 5 75 80 60 65 70 50 52 Utilizando o código em C, pesquise pela chave 52 na árvore B+ abaixo. 17 Ideia básica para a inserção Semelhante à inserção na árvore B: ocorre sempre em uma página folha. Diferença: quando uma folha é dividida em duas, o algoritmo promove uma cópia da chave que pertence ao registro do meio para a página pai no nível anterior, retendo o registro do meio na página folha da direita. 18 Exemplo 2: Inserção árvore B+ 25 10 20 21 Insira a chave 50 na árvore B+ abaixo. 25 30 40 50 25 10 20 21 25 30 40 19 Passos para a inserção Localizar a página folha dentro da qual a chave deve ser inserida; Localizar a posição de inserção dentro da página folha; Inserir a chave; Se, após a inserção, a página folha estiver completa, realizar a divisão da página: Localizar o registro central da página folha e copiá-lo para a página pai; Os registros menores são levados para a página da esquerda; Os registros maiores, incluindo o elemento central, ficam na página da direita. 20 Exemplo 3: Inserção árvore B+ 25 40 10 20 21 Insira a chave 60 na árvore B+ abaixo. 25 30 25 10 20 21 25 30 40 50 Página cheia Solução: dividir a página em duas páginas. O elemento central deve ficar tanto na página da direita quanto na página pai 40 50 60 21 Exercício de Inserção Inserir as seguintes chaves em um árvore B+ de ordem 2: 20, 10, 40, 50, 30, 55, 3, 11, 4, 28, 36, 33, 52, 17, 25, 13, 45, 9, 43, 8 e 48. 17 20 25 28 10 11 13 30 10 17 40 50 3 4 8 9 50 52 55 40 43 45 48 30 33 36 Árvore B+ resultante 22 Idéia básica da Exclusão Relativamente mais simples que em uma árvore B; O registro a ser retirado sempre reside em uma página folha, não havendo necessidade de localizar a chave antecessora; As páginas dos índices não serão modificadas desde que a folha fique com pelo menos a metade dos registros, mesmo que uma cópia da chave que pertence ao registro a ser retirado esteja no índice. Uma chave só é removida do índice quando nós das folhas são combinadas (merge) devido à violação da restrição de capacidade mínima. 23 Exemplo 4: Exclusão árvore B+ Remover chave 5. 29 33 9 18 19 22 45 6 29 60 75 1 4 5 75 80 60 65 70 50 52 29 33 9 18 19 22 45 6 29 60 75 1 4 75 80 60 65 70 50 52 Página continuou com pelo menos metade dos registros 24 Exemplo 5: Exclusão árvore B+ Remover as chaves 19 22 60. 29 33 9 18 19 22 45 6 29 60 75 1 4 75 80 60 65 70 50 52 29 33 9 18 45 6 29 60 75 1 4 75 80 65 70 50 52 Páginas continuaram com metade dos registros 25 Exemplo 6: Exclusão árvore B+ Remover a chave 9. 29 33 9 18 45 6 29 60 75 1 4 75 80 65 70 50 52 29 33 18 45 6 29 60 75 1 4 75 80 65 70 50 52 Página ficou com menos da metade dos registros 26 Exemplo 6: Exclusão árvore B+ Solução: Juntar as duas páginas folha em uma página folha. Se o registro que esta na página pai (registro que separa as páginas) não estiver na página folha da direita, ele é simplesmente eliminado. 29 33 18 45 6 29 60 75 1 4 75 80 65 70 50 52 Página ficou com menos da metade dos registros 27 Exemplo 6: Exclusão árvore B+ 29 33 18 45 6 29 60 75 1 4 75 80 65 70 50 52 Página ficou com menos da metade dos registros 29 33 29 1 4 18 Possibilidade I Se a junção fosse feita com o irmão da esquerda, o registro que esta na página pai (6) não está na página folha da direita, então ele é simplesmente eliminado. 28 Exemplo 6: Exclusão árvore B+ 29 33 18 45 6 29 60 75 1 4 75 80 65 70 50 52 Página ficou com menos da metade dos registros 18 29 33 6 1 4 Possibilidade II Se a junção fosse feita com o irmão da direita, o registro que esta na página pai (29) está na página folha da direita, o registro é eliminado da pagina pai, mas permanece na página folha. 29 Exemplo 6: Exclusão árvore B+ Página ficou com menos da metade dos registros 18 29 33 45 6 60 75 1 4 75 80 65 70 50 52 Solução: Juntar as duas páginas internas em uma página interna. Neste caso, a junção ocorre com a raiz, o que faz a árvore diminuir sua altura em 1. 30 Exemplo 6: Exclusão árvore B+ 18 29 33 6 45 60 75 1 4 75 80 65 70 50 52 Estrutura do Índice foi modificada Página ficou com menos da metade dos registros 18 29 33 45 6 60 75 1 4 75 80 65 70 50 52 31 Remover a chave 80. Exemplo 7: Exclusão árvore B+ 18 29 33 6 45 60 75 1 4 75 80 65 70 50 52 18 29 33 6 45 60 75 1 4 75 65 70 50 52 Página ficou com menos da metade dos registros 32 Exemplo 7: Exclusão árvore B+ 18 29 33 6 45 60 1 4 65 70 75 50 52 As duas páginas viraram uma página folha 33 Exemplo 8: Exclusão árvore B+ Remover a chave 52. 18 29 33 6 45 60 1 4 65 70 75 50 52 18 29 33 6 45 60 1 4 65 70 75 50 Página ficou com menos da metade de m registros... 34 Exemplo 8: Exclusão árvore B+ Remover a chave 52. Solução: Juntar as duas páginas em uma única página folha 18 29 33 6 45 60 1 4 65 70 75 50 18 29 33 6 45 1 4 50 65 70 75 35 Exemplo 9: Exclusão árvore B+ Remover as chaves 18 e 33. Página ficou com menos da metade de m registros... E a página vizinha não pode ser agrupada em uma única página 18 29 33 6 45 1 4 50 65 70 75 29 6 45 1 4 50 65 70 75 36 Exemplo 9: Exclusão árvore B+ Remover as chaves 18 e 33. A página vizinha empresta um registro 29 6 45 1 4 50 65 70 75 29 50 6 65 1 4 65 70 75 37 Exercício de Exclusão Excluir as seguintes chaves na árvore B + de ordem 2: 20, 10, 40, 50, 30, 55, 3, 13, 4, 36, 8. 17 20 25 28 10 11 13 30 10 17 40 50 3 4 8 9 50 52 55 40 43 45 48 30 33 36 38 Exercício de Exclusão Excluir as seguintes chaves na árvore B + de ordem 2: 20, 10, 40, 50, 30, 55, 3, 13, 4, 36, 8. 17 25 28 17 30 45 9 11 45 48 52 33 43 Árvore B+ após as exclusões 39 Acesso Concorrente em Árvore B+ Acesso simultâneo a banco de dados por mais de um usuário; Concorrência aumenta a utilização e melhora o tempo de resposta do Sistema; O uso de árvores B + nesses sistemas deve permitir o processamento simultâneo de várias solicitações diferentes; Necessidade de criar mecanismos chamados protocolos para garantir a integridade tanto dos dados quanto da estrutura; 40 Acesso Concorrente em Árvore B+ Considere a seguinte situação: Dois processos acessando simultaneamente o banco de dados. Um dos processos está percorrendo uma página para localizar o intervalo no qual a chave da pesquisa se encaixa e seguir o apontador para a subárvore correspondente. O outro está inserindo um novo registro que provoca divisões nas páginas do mesmo caminho da árvore. Pode acontecer de o processo que está percorrendo a página obtenha um apontador para uma subárvore errada ou inexistente. 41 Acesso Concorrente em Árvore B+ Página segura: não há possibilidade de modificações na estrutura da árvore como conseqüência de inserção ou remoção. inserção -> página segura se o número de chaves é menor que 2m; remoção -> página segura se o número de chaves é maior que m. Os algoritmos para acesso concorrente fazem uso dessa propriedade para aumentar o nível de concorrência em árvores B+. 42 Acesso Concorrente em Árvore B+ - Protocolos de Travamentos Bayer e Schkolnick (1977) apresentaram três diferentes alternativas de protocolos para travamentos 1, que asseguram a integridade dos caminhos de acesso aos dados da árvore B+ e, ao mesmo tempo, permitem acesso concorrente. 1 mecanismo que assegura a modificação de apenas uma página de cada vez na árvore. 43 Acesso Concorrente em Árvore B+ - Protocolos de Travamentos Quando uma página é lida, a operação de recuperação a trava, assim, outros processos, não podem interferir com a página. A pesquisa continua em direção ao nível seguinte e a trava é liberada para que outros processos possam ler a página. Processo leitor -> executa uma operação de recuperação Processo modificador -> executa uma operação de inserção ou retirada. 44 Acesso Concorrente em Árvore B+ - Protocolos de Travamentos A operação de modificação requer protocolos mais sofisticados, pois níveis acima podem ser modificados. Em umas das alternativas propostas por Bayer e Schkolnick (1977), o processo modificador coloca um travamento exclusivo em cada página acessada, liberando a página apenas quando ela for considerada segura. 45 Acesso Concorrente em Árvore B+ - Protocolos de Travamentos Dois tipos de travamento: Travamento para leitura -> permite um ou mais leitores acessarem os dados, mas não permite inserção ou retirada. Travamento exclusivo -> permite qualquer tipo de operação na página e nenhum outro processo pode operar na página. Mais detalhes sobre Acesso Concorrente em Árvore B+, leia (no final do capítulo 6) livro texto da disciplina. 46 Referências Utilizadas Livro: ZIVIANI, Nivio, Projeto de algoritmos com implementação em Pascal e C, 3a. edição, Editora Thomson, 2011 Notas de aula da disciplina, disponível no Moodle. 47
