Lista de exercícios
Árvores B: leitura e interpretação
Onze exercícios com textos de apoio curtos, figuras prontas e respostas comentadas sobre árvores B, custo de acesso, escolhas de organização e árvores B+.
Resolva uma questão por vez e confira sua solução antes de avançar. Cada questão apresenta o apoio necessário. A lista não pressupõe conhecimento de SQL.
Resposta esperada é uma referência para autocorreção, sem entrega ou correção individual. Outras redações são válidas quando apresentam o raciocínio solicitado. O tempo estimado inclui leitura, tentativa e conferência.
Vocabulário para consulta
- Registro: informações de um item, como identificador e valor de uma medição. A chave é o valor usado para localizar o registro.
- Página: nó da árvore que reúne chaves ordenadas e ligações para seus filhos. A raiz é a página inicial. Uma folha não tem filhos.
- Subárvore: uma página e todas as páginas que descendem dela.
- Página pai: página que aponta diretamente para outra. Cada página, exceto a raiz, tem uma única página pai.
- Elemento pai menor: chave da página pai imediatamente à esquerda da ligação para uma subárvore, quando existir.
- Elemento pai maior: chave da página pai imediatamente à direita dessa ligação, quando existir.
Convenção didática: elementos pais sempre ficam na página pai direta. O primeiro filho não tem elemento pai menor. O último não tem elemento pai maior.
Limites herdados: restrições vindas das páginas acima, que também precisam ser respeitadas. Esses limites não são elementos pais. Na extremidade esquerda da árvore inteira não há limite inferior. Na extremidade direita não há limite superior.
Exercício 1: compreender o problema resolvido
Considere um histórico de medições maior que a RAM disponível. O equipamento precisa consultar medições pelo identificador.
A RAM mantém os dados em uso. O histórico fica no SSD, um exemplo de memória secundária, que conserva os arquivos.
A árvore B reúne chaves em páginas. No modelo desta lista, ler uma página traz suas várias chaves para a RAM. As ligações entre páginas organizam faixas de valores.
Como essa organização ajuda a consultar uma medição sem ler o histórico inteiro?
Solução
Explicação
As chaves de uma página ajudam a delimitar onde um registro pode estar. A consulta pode, assim, acessar somente as páginas pertinentes. O arquivo inteiro não precisa ficar na RAM ao mesmo tempo.
Objetivo de aprendizagem: explicar como a organização em páginas ajuda a consultar grandes conjuntos de dados em memória secundária.
Resposta esperada
A árvore B organiza as chaves por faixas de valores. Isso permite consultar as páginas pertinentes à medição procurada, sem ler todo o histórico nem manter o arquivo inteiro na RAM.
Exercício 2: distinguir elemento pai de limite herdado
Observe a página C na figura.
Nas árvores B desta lista, as chaves são únicas. Todas as chaves de uma subárvore devem ser maiores que o elemento pai menor e menores que o maior, quando existirem. Também devem respeitar os limites herdados das páginas acima.
A subárvore à esquerda de R foi omitida porque não participa desta questão.
Quais são os limites das chaves de C? Identifique o elemento pai e o limite herdado.
Solução
Explicação
B está à direita de 40, então suas chaves e as de todas as páginas abaixo dela devem ser maiores que 40. C está à esquerda de 60, então suas chaves também devem ser menores que 60.
O valor 60 está em B, a página pai de C. Já 40 vem de R, uma página acima de B.
Objetivo de aprendizagem: interpretar o intervalo de uma subárvore, distinguindo o elemento pai local de um limite herdado.
Resposta esperada
As chaves de C devem ser maiores que 40 e menores que 60.
- 60: elemento pai maior, dentro de
B, a página pai deC. - 40: limite inferior herdado de
R. Não é elemento pai deC.
C não tem elemento pai menor. Suas chaves 45 e 50 respeitam os dois limites.
Exercício 3: avaliar uma árvore pronta
Avalie esta árvore B de ordem m = 2. Todas as páginas estão representadas.
Use a tabela para conferir uma regra por vez:
| Regra | O que verificar |
|---|---|
| Ocupação | Raiz com uma a quatro chaves. Cada outra página com duas a quatro. |
| Filhos | Uma página interna tem um filho a mais que sua quantidade de chaves. Folhas não têm filhos. |
| Ordem interna | As chaves de cada página estão em ordem crescente. |
| Intervalos | Todas as chaves da subárvore respeitam os elementos pais e os limites herdados. |
| Nível das folhas | Todas as folhas estão no mesmo nível. A raiz ocupa o nível 1. |
A árvore é válida? Registre uma justificativa para cada regra da tabela.
Solução
Explicação
Uma árvore B precisa respeitar todas as regras ao mesmo tempo. Aqui, C está à direita de 60 em R, mas contém 55. Essa chave viola o intervalo, mesmo estando antes de 80 dentro da página.
Objetivo de aprendizagem: verificar ocupação, filhos, ordenação, intervalos e nível das folhas em uma árvore pronta.
Resposta esperada
A árvore não é válida. A única falha está na chave 55 de C.
| Regra | Justificativa |
|---|---|
| Ocupação | Todas as páginas têm duas chaves, dentro dos limites permitidos. |
| Filhos | R tem três filhos para duas chaves. As demais páginas são folhas e não têm filhos. |
| Ordem interna | Todas as páginas têm chaves em ordem crescente, inclusive 55 antes de 80 em C. |
| Intervalos | A tem 10 e 20, menores que 30. B tem 40 e 50, entre 30 e 60. Em C, 80 é maior que 60, mas 55 não é. |
| Nível das folhas | A, B e C estão no nível 2. |
Exercício 4: comparar chaves exige acessar o SSD?
Distinga as três atividades:
- Leitura de página: trazer uma página do SSD para a RAM.
- Comparação: verificar se uma chave é menor, igual ou maior que outra, usando os dados na RAM.
- Gravação de página: salvar no SSD o conteúdo alterado de uma página.
Situação. Uma página já está na RAM e permanece nela durante a consulta. O programa compara várias chaves dessa página, sem alterar os dados.
Cada comparação exige uma nova leitura ou gravação no SSD? Justifique.
Solução
Explicação
A página já foi trazida para a RAM. As comparações usam esse conteúdo, sem precisar trazer a página novamente. Como os dados não foram alterados, também não há conteúdo novo para gravar no SSD.
Objetivo de aprendizagem: distinguir comparações feitas na RAM de leituras e gravações de páginas no armazenamento.
Resposta esperada
Não. As comparações usam a página que já está na RAM. Elas não exigem novas leituras do SSD nem gravações, pois os dados permanecem inalterados.
Exercício 5: relacionar capacidade e altura
Observe duas árvores B que armazenam o mesmo conjunto de chaves.
Uma página com mais espaço para chaves, além de armazenar mais registros em uma única página, também pode ter mais filhos. Assim, podemos armazenar muito mais dados sem aumentar a altura da árvore. A altura é o número de níveis da árvore, começando pela raiz no nível 1. Cada aresta percorrida em direção às folhas representa o avanço de um nível.
A tabela apresenta duas organizações prontas. As consultas chegaram a uma folha, e as quantidades de páginas lidas já estão informadas.
| Característica | Árvore P | Árvore Q |
|---|---|---|
| Capacidade de chaves por página | Menor | Maior |
| Altura | 4 níveis | 3 níveis |
| Páginas lidas na consulta | 4 | 3 |
Como a maior capacidade das páginas de Q pode ajudar a reduzir os níveis e as leituras?
Solução
Explicação
Com mais chaves por página interna, é possível ter mais filhos e distribuir os dados entre mais subárvores. Isso pode permitir acomodar o mesmo conjunto de dados em menos níveis. Neste exemplo, Q tem um nível a menos e sua consulta lê uma página a menos.
A maior capacidade permite essa redução, mas não a garante em toda árvore. A altura também depende de quanto espaço das páginas está ocupado.
Objetivo de aprendizagem: relacionar capacidade das páginas, quantidade de filhos, altura e quantidade de páginas lidas.
Resposta esperada
A maior capacidade permite mais filhos por página interna. Com isso, o mesmo conjunto de chaves pode caber em menos níveis. No exemplo, Q tem três níveis e exige três leituras, enquanto P tem quatro níveis e exige quatro leituras.
Exercício 6: escolher para uma leitura completa
Compare duas possibilidades:
- Arquivo sequencial simples: os registros são lidos em sequência.
- Arquivo com índice: uma estrutura adicional indica onde estão determinadas faixas de chaves.
Um relatório precisa ler todos os registros de um arquivo. O arquivo não muda durante esse trabalho.
Qual opção atende a esse uso com a organização mais simples? Por quê?
Solução
Explicação
O índice ajuda a localizar partes do arquivo. Nesse relatório, todos os registros precisam ser lidos. Manter um índice apenas para essa tarefa acrescentaria uma estrutura sem dispensar a leitura completa.
Objetivo de aprendizagem: reconhecer quando o acesso sequencial atende ao uso sem precisar de um índice.
Resposta esperada
Arquivo sequencial simples. O relatório precisa ler todos os registros, portanto um índice não evitaria a leitura completa.
Exercício 7: escolher para consultas em dados estáveis
Considere um arquivo sequencial indexado: os dados ficam ordenados, e um índice indica a página de cada faixa de chaves.
Neste exemplo, o índice é estático: é preparado junto com o arquivo e permanece igual enquanto os dados não mudam. Ele cabe na RAM.
Um catálogo é substituído uma vez por mês. Durante o mês, recebe muitas consultas por identificador e nenhuma alteração.
Um índice estático ajuda nessas consultas? Justifique pelo uso do catálogo.
Solução
Explicação
Cada consulta procura apenas uma parte do catálogo. O índice permite identificar a página pertinente, sem percorrer todos os registros. Como o catálogo não muda durante o mês, o mesmo índice pode atender às consultas até a próxima substituição.
Objetivo de aprendizagem: justificar o uso de um arquivo indexado quando há consultas frequentes e dados estáveis.
Resposta esperada
Sim. O índice direciona cada consulta para a página pertinente. Como o catálogo permanece inalterado durante o mês, não é necessário atualizar o índice entre essas consultas.
Exercício 8: escolher para dados que mudam
Compare duas formas de organizar o índice de um cadastro:
- Índice estático deste exemplo: precisa ser reconstruído quando o conjunto de chaves muda.
- Árvore B: ajusta as páginas afetadas pelas alterações, mantendo suas propriedades. Esses ajustes podem exigir gravações.
O cadastro recebe consultas por identificador, inclusões e remoções durante todo o dia. Reconstruir o índice inteiro a cada mudança seria inadequado.
Qual alternativa atende melhor a esse cadastro? Por quê?
Solução
Explicação
A escolha precisa considerar as alterações, além das consultas. A árvore B permite manter a organização atualizada ajustando páginas, sem reconstruir todo o índice a cada mudança. Essa manutenção tem custo, mas atende à necessidade de atualização frequente.
Objetivo de aprendizagem: justificar a escolha de uma árvore B quando consultas e alterações são frequentes.
Resposta esperada
Árvore B. Ela atende às consultas e acompanha as inclusões e remoções sem reconstruir todo o índice a cada mudança. Ainda pode precisar ajustar e gravar páginas.
Exercício 9: distinguir registros de índices
Compare a entrada de chave 30 na raiz das duas árvores. Os desenhos representam os mesmos oito registros.
Na figura, registro indica os dados ou uma referência a eles. Índice indica uma chave usada somente para orientar a localização dos registros.
A chave 30 da raiz tem o mesmo papel nas duas árvores? Explique a diferença.
Solução
Explicação
Na B, uma entrada pode estar associada ao registro em uma página interna ou em uma folha. Na B+, as entradas associadas aos registros ficam somente nas folhas. As chaves internas são cópias para orientação.
Por isso, a repetição de 30 na raiz e em uma folha da B+ não representa dois registros. Somente a entrada na folha está associada ao registro.
Objetivo de aprendizagem: distinguir o papel das entradas internas em B e B+ pela sua associação aos registros.
Resposta esperada
Não. Na B, a entrada de chave 30 na raiz está associada ao registro. Na B+, ela apenas orienta a localização. A entrada associada ao registro está na folha, e o registro não está duplicado.
Exercício 10: entender as folhas ligadas da B+
Relacione estas duas características da B+:
- Todas as entradas associadas aos registros ficam nas folhas.
- As folhas estão ligadas entre si na ordem das chaves.
Uma consulta por intervalo pede registros entre dois limites, como medições de um período. Considere que o início desse intervalo já foi localizado.
Como as ligações entre folhas ajudam a continuar essa consulta?
Solução
Explicação
A ligação indica a próxima folha na ordem das chaves. Assim, a consulta pode continuar nas folhas seguintes até alcançar o fim do intervalo, sem recomeçar pela raiz para cada registro.
Como todas as entradas associadas aos registros estão nas folhas, essa continuação não deixa de fora registros exclusivos de páginas internas. A árvore B também permite consultas por intervalo. A B+ oferece essa organização em folhas ligadas.
Objetivo de aprendizagem: relacionar a localização dos registros e o encadeamento das folhas da B+ às consultas por intervalo.
Resposta esperada
As ligações permitem continuar pelas folhas seguintes em ordem, sem iniciar uma nova busca pela raiz para cada registro. Como todas as entradas associadas aos registros estão nas folhas, elas podem ser consultadas nessa sequência.
Exercício 11: sintetizar uma recomendação técnica
Recomende o uso de uma árvore B para este catálogo:
- O arquivo é maior que a RAM disponível.
- Há consultas por identificador, inclusões e remoções frequentes.
Escreva um parágrafo de três frases, seguindo este roteiro:
- Indique qual problema a árvore B ajuda a resolver no catálogo.
- Explique como a organização em páginas contribui para isso.
- Mencione um custo ou limite que permanece.
Solução
Explicação
A recomendação deve conectar a estrutura às necessidades do catálogo. O roteiro separa a finalidade, o funcionamento geral e uma limitação. A síntese reúne essas ideias já trabalhadas na lista.
Objetivo de aprendizagem: produzir uma síntese que conecte problema, funcionamento geral, aplicação e limitações das árvores B.
Resposta esperada
Uma árvore B é adequada ao catálogo porque ajuda a consultar e atualizar dados maiores que a RAM sem percorrer ou reorganizar todo o arquivo a cada operação. Ela reúne chaves ordenadas em páginas, organiza as ligações por intervalos e mantém suas propriedades durante as alterações. A solução ainda exige leituras do armazenamento e pode precisar ajustar e gravar páginas quando os dados mudam.