Questão de Administração de Banco de Dados · FGV MPAL 2018 (nº 41)

A busca em uma Árvore B sempre começa na raiz e desce até encontrar a chave ou chegar a um nó folha. O número máximo de nós visitados corresponde à altura da árvore mais um (contando a raiz). Para maximizar a altura de uma árvore com um certo número de chaves, os nós devem estar o mínimo possível preenchidos.

• (A) Incorreta: Uma altura de 2 (3 nós visitados) seria para uma árvore com um número muito menor de chaves, ou uma árvore muito mais cheia. Com 30.000 chaves e $d=8$, o mínimo de chaves para altura 2 é 161.
• (B) Correta: Para encontrar o número máximo de nós visitados, precisamos determinar a altura máxima ($h$) que uma Árvore B com 30.000 chaves pode ter. A altura máxima ocorre quando os nós estão minimamente preenchidos.
  1. Propriedades da Árvore B de ordem d:
     • Cada nó (exceto a raiz) tem no mínimo d chaves e d+1 filhos.
     • A raiz tem no mínimo 1 chave e 2 filhos (se não for folha).
     • Dado $d=8$, cada nó (não raiz) tem no mínimo 8 chaves e 9 filhos.
  2. Fórmula para o número mínimo de chaves ($N_{min}$) em uma árvore de altura $h$:
     $N_{min}(h) = 1 + 2 \times ((d+1)^h - 1)$
     Onde $h$ é a altura da árvore (número de arestas da raiz até a folha mais distante).
  3. Substituindo $d=8$:
     N_{min}(h) = 1 + 2 \times ((8+1)^h - 1) = 1 + 2 \times (9^h - 1)\
  4. Encontrando o maior $h$ para 30.000 chaves:
     Queremos o maior $h$ tal que $N_{min}(h) \le 30000$:
     $1 + 2 \times (9^h - 1) \le 30000$
     $2 \times (9^h - 1) \le 29999$
     $9^h - 1 \le 14999.5$
     9^h \le 15000.5\
  5. Testando potências de 9:
     • $9^1 = 9$
     • $9^2 = 81$
     • $9^3 = 729$
     • $9^4 = 6561$
     • $9^5 = 59049$
       O maior valor de $h$ que satisfaz $9^h \le 15000.5$ é $h=4$.
  6. Número de nós visitados:
     O número de nós visitados é $h+1$. Portanto, $4+1=5$ nós.
• (C) Incorreta: Uma altura de 6 (7 nós visitados) exigiria um número mínimo de chaves de $N_{min}(6) = 1 + 2 \times (9^6 - 1) = 1 + 2 \times (531441 - 1) = 1 + 1062880 = 1062881$, o que é muito maior que 30.000.
• (D) Incorreta: Este valor não corresponde à lógica de altura de uma Árvore B. Pode ser um distrator relacionado ao número máximo de chaves em um nó ($2d-1 = 15) ou filhos (\2d+1 = 17$).
• (E) Incorreta: (Distrator mais tentador) Este valor (15.000) é a metade do número total de chaves (30.000 / 2). A armadilha aqui é pensar que a busca em uma Árvore B é linear ou que o número de nós visitados seria uma fração direta do total de chaves, o que é incorreto. A busca em Árvores B, como em outras árvores balanceadas, tem complexidade logarítmica, ou seja, o número de nós visitados cresce muito mais lentamente que o número de chaves.