Questão de Banco de Dados — Banco de Dados Relacionais — FGV 2023
Banco de Dados›Banco de Dados Relacionais
Código
fg071509
Banca
FGV
Órgão
TCE-SP
Ano
2023
Nível
Superior
Cargo
Agente da Fiscalização - TI
Tabelas Hash (e assemelhadas) são utilizadas frequentemente em implementações de bancos NoSQL do tipo “Key-value”, enquanto B-trees são preferencialmente utilizadas em bancos de dados relacionais.Nesse contexto, analise as afirmativas a seguir.I. Algoritmos de busca a partir de chaves em tabelas Hash têm complexidade O(N/2), enquanto em B-trees têm complexidade O(log N).II. B-trees suportam buscas por intervalo de chaves.III. Tabelas Hash admitem e gerenciam múltiplas chaves para o mesmo objeto indexado sem redundância.Está correto somente o que se afirma em:
AI;
BII;
CIII;
DI e II;
EII e III.
Revelar gabarito e comentário▾
GabaritoB — II;
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Estruturas de indexação: tabelas hash versus B-trees
Gabarito: letra B. Apenas a afirmativa II está correta: B-trees suportam buscas por intervalo de chaves, graças à ordenação das chaves na árvore. As demais afirmativas contêm erros conceituais: a complexidade de busca em tabelas hash é O(1) no caso médio (não O(N/2)), e tabelas hash não gerenciam múltiplas chaves para o mesmo objeto sem redundância — colisões exigem tratamento (ex.: encadeamento ou endereçamento aberto), o que pode introduzir redundância.
A questão cobra a distinção entre as estruturas de indexação típicas de bancos NoSQL (hash) e relacionais (B-tree).
Afirmativa I — ❌ Incorreta
Afirma que a complexidade de busca em tabelas hash é O(N/2). Isso não é uma notação padrão; na média, a busca em tabelas hash é O(1), embora no pior caso possa ser O(N) devido a colisões. Já em B-trees, a complexidade é O(log N). Portanto, a comparação está errada.
Afirmativa II — ✅ Correta ⟵ GABARITO
B-trees mantêm as chaves ordenadas e balanceadas, o que permite percorrer a árvore em ordem e realizar buscas por intervalo (ex.: todas as chaves entre valor1 e valor2) com eficiência O(log N + k), onde k é o número de resultados.
Afirmativa III — ❌ Incorreta
Tabelas hash mapeiam cada chave para um único valor. Se duas chaves diferentes forem inseridas, cada uma gera uma entrada distinta. Para associar múltiplas chaves ao mesmo objeto, seria necessário usar listas encadeadas ou outras estruturas que introduzem redundância ou complexidade. A afirmativa sugere que isso é feito "sem redundância", o que não é verdade.
Conclusão: Somente a afirmativa II está correta, portanto o gabarito é a letra B.
NÃO CAIA NESSA!
A banca tenta confundir a complexidade das tabelas hash (espera-se que o candidato saiba que é O(1) médio, não O(N/2)) e a gestão de colisões. Em tabelas hash, múltiplas chaves para o mesmo objeto exigem tratamento de colisão, o que pode gerar redundância (ex.: encadeamento).
PEGA ESSA DICA!
Decore as complexidades típicas: hash → O(1) médio, O(N) pior caso; B-tree → O(log N) sempre. Para buscas por intervalo, B-tree é a escolha natural.