Questão Q1846123

Considere uma árvore B+ com as seguintes características.

I. A raiz é uma folha ou um nó que contém, no mínimo, dois filhos.

II. Cada nó diferente do nó raiz e das folhas possui no mínimo d filhos.

III. Cada nó tem no máximo 2d filhos. Cada nó possui entre d-1 e 2d-1 chaves, exceto o raiz que possui entre 1 e 2d-1 chaves.

IV. Somente os nós folhas contêm dados associados às chaves.

Assinale o número máximo de acessos necessários para localizar uma chave, com d=10, num universo de 10 milhões de chaves.

Alternativas

100

1.000

Comentários

Gabarito: b

A questão esta querendo saber qual o nivel da hierarquia será para o nó 10 milhoes.
Ex.:
| - Nível 1 = 1
| | - Nível 2 = 2
| | | | - Nível 3 = 4
....
- Nível 4 = 8
....

Vamos usar um paralelo de tabela binária, níveis da árvore B+ e valor desejado.

N 7 6 5 4 3 2 1
... 64 32 16 8 4 2 1
10 .0 0 0 . 0 0 0

Resultado: 10 está no nível 7.
D é igual ao número de filhos.
Se D = 10, então a cada nível a árvore terá um múltiplo de 10 filhos.
Nível 1 = 10, nível 2 = 10 nodos com possibilidade de 10 filhos cada, ou seja 10x10 = 100.
Para ir direto ao ponto, utilizando dois níveis (2 acessos) com D = 10, eu posso ter 100 nodos (1 + 2 zeros).
Ou seja, com 10 milhões de nodos (7 zeros) eu vou precisar percorrer pelo menos 7 níveis.
Partindo do pressuposto que uma árvore binária o acesso a ser dado pelos nós seria 2^n. Poderíamos fazer para árvore B+ que possui 10 índices, o seguinte: 10^n. Portanto, para resolvermos a questão faríamos assim:

10^n = 10.000.000
10^n = 10^7
n = 7

SóProvas