Questão nº 41
Questão de Tecnologia da Informação · FGV TCE-SP 2023 (nº 41)
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; (alternativa correta)
- CIII;
- DI e II;
- EII e III.
Resposta comentada
Gabarito Alternativa B
O conceito-chave é que B-trees são estruturas ordenadas, perfeitas para buscas por intervalo, enquanto tabelas Hash são estruturas não ordenadas, otimizadas apenas para busca por igualdade exata da chave. A pegadinha está em achar que a complexidade da Hash é O(N/2), quando na verdade é O(1) em média.
- (A) Incorreta: A complexidade média de busca em uma tabela Hash é O(1) (constante), não O(N/2). A complexidade O(log N) para B-trees está correta, mas a primeira parte invalida a afirmação.
- (B) Correta: B-trees armazenam as chaves em ordem, permitindo percorrer os nós folha sequencialmente, o que viabiliza buscas por intervalo (ex: "todos os clientes com nome entre 'A' e 'C'"). Essa é a principal razão de serem usadas em bancos relacionais.
- (C) Incorreta: Tabelas Hash não gerenciam múltiplas chaves para o mesmo objeto sem redundância; elas usam uma única chave para mapear um valor. Para múltiplas chaves, seria necessário criar índices secundários, o que geraria redundância ou estruturas adicionais.
- (D) Incorreta: A afirmação I é falsa (como explicado na letra A), então a combinação I e II não pode ser correta.
- (E) Incorreta: A afirmação III é falsa (como explicado na letra C), então a combinação II e III não pode ser correta.
Fonte: FGV TCE-SP 2023 Agente da Fiscalização - TI (Caderno Tipo 1). Reproduzida para fins de estudo.