Questão 1826989

• Banca: FGV
• Órgão: TJ-PI
• Ano: 2015
• Provas: FGV - 2015 - TJ-PI - Analista Judiciário - Analista de Sistemas / Banco de Dados
• Disciplina: Banco de Dados
• Assuntos: Índices

Considere as seguintes propriedades de uma implementação de índice para bancos de dados.

I. Cada página contém no máximo d páginas filhas

II. Cada página, exceto a raiz e as folhas, tem pelo menos d÷2 páginas filhas.

III. Todas as páginas folha possuem a mesma profundidade emrelação à raiz.Nesse tipo de árvore, uma busca que envolva um domínio de N=1.000.000.000 de chaves requer, no máximo, um número de acessos da ordem de:

• A. lg(N)
• B. lg(N² )
• C. N
• D. N^d
• E. lg(N^d )

Gabarito: A

Comentários

• Não seria LOGd (N)?

•  A complexidade pode ser: ▸

  O(1) → o item a ser pesquisado encontra-se na raiz da árvore

  O(h) → caso tenha-se que percorrer toda a altura da árvore para se encontrar a chave :

    O(log n) → árvore binária completa (Gabarito)

     O(n) → árvore degenerada