Prévia do material em texto

<p>Fundação Universidade Federal de Rondônia</p><p>Departamento Acadêmico de Ciência da Computação</p><p>Estrutura de Dados II</p><p>Exercícios - Árvores B e variações</p><p>Discentes: Carlos Henrique Cardoso dos Santos e Higor Nascimento</p><p>1. Criar uma árvore-B+ pela inserção das chaves A, B, C, D, E, F, G, H, I e J, nesta</p><p>ordem. ∙ Ordem da árvore: 3</p><p>∙ Blocos de 3 registros.</p><p>2. Dada uma árvore -B+ abaixo, remova L, M, K e A, nesta ordem.</p><p>∙ Número mínimo de registros por bloco=2</p><p>∙ Número máximo de registros por bloco=4</p><p>∙ Ordem da árvore=3</p><p>3. Quais os separadores dos blocos, considerando uma árvore-B+ pré-fixada?</p><p>4. Construa a árvore-B+ pré-fixada sobre os blocos do exercício 3.</p><p>5. Realize as seguintes operações sobre a árvore-B+ pré-fixada do exemplo</p><p>anterior a) inserção de CARTER</p><p>b) inserção de DRAG</p><p>c) remoção de BIXBY</p><p>d) remoção de COLE</p><p>6. Quais os problemas de se usar árvores binárias de busca e árvores AVL como estruturas</p><p>de índices para grandes volumes de dados?</p><p>R: Um dos maiores problemas é o elevado número de acessos ao disco ao utilizar essas</p><p>estruturas de dados para grandes volumes de dados. Assim, como exemplo as ABB’s podem</p><p>facilmente se tornar desbalanceadas, o que leva a operações de busca, inserção e remoção</p><p>com complexidade O(n) no pior caso. Além disso, as AVL 's necessitam de constantes</p><p>operações de balanceamento, o que pode ocasionar um overhead significativo em termos de</p><p>tempo.</p><p>7. Considere uma árvore-B de ordem 3. Considere que o primeiro elemento do segundo nó é a</p><p>chave promovida durante o particionamento do nó. Insira as seguintes chaves no índice: A, B,</p><p>C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, Z</p><p>Qual o efeito da inserção das chaves em ordem alfabética? A árvore degenerou?</p><p>8. Quais as vantagens do uso da técnica de redistribuição quando da inserção e remoção</p><p>de chaves em uma árvore-B?</p><p>R: A redistribuição oferece como principal vantagem uma melhor taxa de ocupação dos nós,</p><p>tornando mais eficiente o uso do espaço e possibilitando uma árvore de menor altura,</p><p>assim, diminuindo o número de acessos ao disco necessários durante as operações de</p><p>busca, inserção e remoção.</p><p>9. Suponha que você vai remover uma chave em uma árvore-B, a qual causa underflow na</p><p>página. Se pela página irmã do lado direito é necessária concatenação, e pela página irmã</p><p>do lado esquerdo é possível redistribuição, qual opção você escolheria? Por quê?</p><p>R: Nesse cenário, a melhor opção se dá pela redistribuição. Visto que aredistribuição não</p><p>modifica a estrutura da árvore e proporciona uma maior taxade ocupação das páginas/nós.</p><p>10. Qual a diferença entre uma árvore-B e uma árvore-B*? Quais as vantagens e</p><p>as desvantagens da árvore-B*?</p><p>R: A principal diferença se dá pela implementação do split durante a operaçãode</p><p>inserção. Nas árvores B* o split é dado por “two-to-three split”, já nasárvores B é</p><p>por “One-to-two split”</p><p>.● Árvores B*: Uma página folha contém no mínimo (2m-1)/3 e no máximo-1</p><p>chaves.</p><p>● Árvores B; Uma página folha contém no mínimo m/2 -1 e, no máximo,m-1</p><p>chaves.</p><p>A principal vantagem das árvores B* se dá pela melhor taxa de ocupação das</p><p>páginas proporcionadas pela redistribuição durante as operações, tornado uma</p><p>árvore com nível menor</p><p>12. O que é uma árvore-B+? Quando ela é necessária?</p><p>R: Uma árvore-B + é uma estrutura de dados do tipo árvore derivada das árvores-B, porém</p><p>com uma forma diferente de armazenamento de suas chaves, onde as chaves são</p><p>armazenadas nas folhas e as folhas são ligadas umas às outras através de ponteiros,</p><p>permitindo uma varredura sequencial eficiente. Usamos uma árvore-B+ quando buscamos</p><p>organizar um arquivo de modo que seja eficiente para processamento sequencial de busca.</p><p>13. O que são separadores? Qual a diferença entre separadores e chaves?</p><p>R: São prefixos armazenados em índices, cada um de tamanho mínimovariável, usados para</p><p>distinguir entre os diferentes blocos de dados que estãoarmazenados nas folhas. O que</p><p>diferencia uma chave de um separador é quea chave é o dado real, já o separador é somente</p><p>um prefixo que indica umcaminho a uma determinada página folha procurada.</p><p>14. Para aplicações reais, juntamente com cada chave da árvore-B é armazenada uma</p><p>referência para o registro do arquivo de dados que contém os dados que são associados à</p><p>chave (abordagem 1). Outra solução consiste em, juntamente com cada chave da árvore-B,</p><p>armazenar o registro completo de dados que contém os dados que são associados à chave</p><p>(abordagem 2).Compare essas duas abordagens em termos de vantagens e desvantagens.</p><p>R: Abordagem 1:Vantagens:- Melhor uso do espaço, visto que armazena apenas referências</p><p>para os registros, economizando espaço na árvore.- Menor Overhead de Armazenamento,</p><p>pois mantém os registros separados das chaves, reduzindo o espaço ocupado pela estrutura</p><p>da árvore em si.Desvantagens:- Requer um acesso adicional ao disco, primeiro para obter a</p><p>referência do registro na árvore-B e depois para acessar o próprio registro no arquivo de</p><p>dados, aumentando o tempo de execução.Abordagem 2:Vantagens:- Acesso direto ao disco, é</p><p>possível acessar o registro completo sem</p><p>necessidade de buscar em outro local.Desvantagens:- Maior consumo do espaço, pois cada</p><p>chave armazena o registro completo, resultando em maior uso de espaço na árvore</p><p>15. Em sala de aula, considerou-se que os campos da árvore-B quearmazenam as chaves de</p><p>busca são campos de tamanho fixo (abordagem 1).Entretanto, a árvore-B pode ser</p><p>implementada considerando campos detamanho variável para armazenar as chaves de</p><p>busca (abordagem 2).Compare essas duas abordagens em termos de vantagens e</p><p>desvantagens.</p><p>R:Abordagem 1:Vantagens:- Acesso direto e mais rápido, visto que campos de tamanho fixo</p><p>estrutura da árvore-B são dados em posições previsíveis, otimizando operações como busca e</p><p>inserção.Desvantagens:- Possibilidade de desperdício de espaço quando as chaves não</p><p>ocupam o tamanho fixo definido.Abordagem 2: Campos de Tamanho Variável Vantagens:- Uso</p><p>eficiente do espaço, pois cada chave ocupa apenas a quantidade de memória</p><p>necessária.Desvantagens:- Complexidade ao acessar, já que se torna necessário gerenciar</p><p>o'tamanho das chaves e ajustar os ponteiros e índices conforme as chaves variam</p><p>a. Desenhe a trie estendida e o diretório de endereços hash correspondente. b. Considerando</p><p>que os buckets A, B e C contém, respectivamente, 100, 50 e 03 registros, dê a configuração do</p><p>diretório, e a condição de cada bucket após a inserção de uma nova chave cujo valor da função</p><p>hash é 00.</p><p>c. Ainda na configuração inicial, considere agora que todas as chaves de B são eliminadas. O</p><p>que acontece com o diretório?</p><p>17. Considere um máximo de 3 elementos por bucket, e que a função hash gera 4 bits para</p><p>uma chave. Simule a inserção de chaves que geram os seguintes endereços: 0000, 1000, 1001,</p><p>1010, 1100, 0001, 0100, 1111, 1011</p><p>http://wiki.icmc.usp.br/images/7/72/Alg2_17.Hashing_Externo.pdf</p>