SóProvas


ID
1055641
Banca
CESPE / CEBRASPE
Órgão
STF
Ano
2013
Provas
Disciplina
Banco de Dados
Assuntos

Julgue os itens a seguir acerca de bancos de dados.

O uso de árvores B+ aumenta a eficiência da pesquisa de dados por meio de índices, porém dificulta a busca de dados sequenciais.

Alternativas
Comentários
  • Busca

    A operação de busca sobre uma árvore B+ pode ser realizada de duas maneiras: iniciando a busca (linear ou binária) pelo apontador para o sequence set ou pelo apontador para a raíz da árvore. O método mais eficiente é pelo apontador para a raíz na qual é semelhante ao realizado numa árvore B. Dessa forma quando buscamos uma chave k, percorremos a árvore de cima para baixo carregando as páginas internas e selecionando a página apontada pelo ponteiro correspondente ao intervalo no qual pertence k e caso uma cópia de k esteja numa página interna devemos carregar a página à direita de k. Encontrado uma página folha o algoritmo deve buscar k nesta e responder se ela se encontra ou não.


  • Sendo mais objetivo: uma das principais vantagens da utilização de uma árvore B+ em relação a uma árvore B é o aumento da eficiência nas buscas sequenciais em relação a esta. Portanto, questão ERRADA.

    Vejamos os motivos dos ganhos de eficiência nas buscas sequenciais em árvores B+:

    "árvore B+ aparentemente foi proposta por Knuth e grande parte da literatura sobre essa estrutura é encontrada em forma de artigos ao invés de livros. Com ela foi possível organizar um arquivo de maneira que o processamento sequencial (característica até então pouco eficiente para árvores B) e aleatório de chaves fossem eficientes

    A idéia inicial desta variação da árvore B é manter todas as chaves de busca em seus nós folha de maneira que o acesso sequencial ordenado das chaves de busca seja um processo mais eficiente do que em árvores B. Obviamente tal acesso sequencial também é possivel nestas, mas, para isso seria necessário algum algoritmo semelhante ao percurso em ordem realizado numaárvore binária.

    Para manter o acesso sequencial, cada nó folha contém apontadores para quais nós são seus predecessores ou sucessores na sequência de chaves e como nas árvores B, as chaves estão ordenadas tanto em suas páginas internas quanto em páginas folha. Dessa forma, quando realizamos uma busca por uma chave k e para encontrarmos a chave k+1, ou seja sua sucessora na ordem, basta verificar a chave ao lado de k caso k+1 esteja na mesma página de k ou carregar a próxima página contida na lista de páginas para verificar qual chave sucede k. Tal procedimento emárvores B seria mais custoso, pois, deveríamos buscar por k+1 iniciando pela raiz da árvore caso k+1 não estivesse na mesma página de k. Em comparação com asárvores B, este tipo de acesso sequencial às chaves é um dos principais benefícios proporcionados pelas árvores B+.

    Além desta característica, também devemos analisar suas semelhanças com as árvores B. A organização das páginas internas ou no inglês index set é semelhante a de uma árvore B, este, por sua vez, armazena cópias de chaves para referênciar as buscas, mas não contém as chaves em si. Já no sequence set estão as páginas folha que contém as chaves inseridas na árvore e funciona como uma lista encadeada permitindo o acesso sequencial ordenado às chaves independente do index set." - fonte : http://pt.wikipedia.org/wiki/Árvore_B+.

    Espero ter ajudo!

  • mas comparando com ler a tabela inteira não é pior o uso de árvores B no percurso sequencial? vai ficar fazendo passeio na árvore e lendo blocos ao invés de ler todos blocos de uma vez? alguém pode ajudar nessa dúvida?

  • As árvores B+ se diferenciam das árvores B convencionais na medida em que possuem os dados somente nas folhas. Essas folhas, por sua vez, possuem referências para a próxima folha, o que permite um melhor desempenho nas consultas que envolvem intervalos (sequências) de dados. Assim, a alternativa está incorreta, pois o que acontece é exatamente o contrário.

    Gabarito: E