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:
- A)I;
Errada, porque a busca em tabela hash nao tem complexidade O(N/2); em media ela e O(1), e o item I fica incorreto.
- B)II;
Certa, porque B-trees permitem buscas por intervalo de chaves, exatamente por manterem os dados ordenados.
- C)III;
Errada, porque tabelas hash nao sao a estrutura adequada para gerenciar multiplas chaves do mesmo objeto sem redundancia de forma eficiente.
- D)I e II;
Errada, porque a afirmativa I esta incorreta, embora a II esteja correta.
- E)II e III.
Errada, porque a III esta incorreta, mesmo com a II estando correta.
Gabarito: B
Quando voce pensa em estrutura de indexacao, a ideia central e simples: hash e campea em busca por igualdade, enquanto B-tree brilha quando voce quer ordenar e navegar pelo intervalo. Em tabelas hash, a funcao de espalhamento leva a chave diretamente para um endereco, entao a busca costuma ser O(1) em media, e nao O(N/2). No pior caso, com muitas colisoes, pode degradar, mas a conta classica da banca nao e essa. Já a B-tree organiza os dados de forma ordenada e balanceada, o que permite buscar em O(log N) e tambem fazer consultas por faixa de valores sem sofrimento. Por isso a afirmativa II esta correta: B-trees suportam buscas por intervalo de chaves, algo muito util em bancos relacionais, como em consultas com BETWEEN, ordenacao e varreduras proximas. A estrutura foi feita justamente para manter chaves em ordem e reduzir acessos ao disco. A afirmativa I esta errada porque tabela hash nao tem busca O(N/2); a ideia de hash e evitar varredura linear. E a afirmativa III tambem esta errada: hash nao e a estrutura ideal para lidar com multiplas chaves do mesmo objeto de forma ordenada e sem redundancia, porque isso exigiria outro tipo de organizacao de indice. Em resumo, a banca quis testar a diferenca classica entre acesso direto por chave e acesso ordenado por faixa.