Questão de Tecnologia da Informação - Programação · FGV DPE-RS 2023 (nº 63)

Árvores B+ são estruturas de dados que organizam informações para buscas rápidas em bancos de dados. Elas funcionam como um índice: todos os dados completos ficam nas "folhas" (o nível mais baixo), e os "nós internos" (níveis superiores) guardam apenas chaves para direcionar a busca até a folha correta. Quando uma folha fica cheia, ela se divide, e o valor do meio é "promovido" para o nó interno acima, mas uma cópia dele permanece na folha à direita, por isso dizemos que ele é "replicado".

Vamos simular a construção da árvore B+ de ordem 5 (máximo de 4 chaves por nó):

1. Inclusão de 10, 20, 30, 40:

   • Folha: [10, 20, 30, 40] (cheia)

2. Inclusão de 50:

   • A folha [10, 20, 30, 40, 50] está cheia. Divide.
   • Chave mediana: 30.
   • 30 é promovido para o nó interno (que se torna a raiz). Uma cópia de 30 permanece na folha à direita.
   • Raiz (interna): [30]
   • Folhas: [10, 20] <-> [30, 40, 50]
   • Chaves replicadas em nós internos até agora: {30}

3. Inclusão de 60:

   • Vai para a folha [30, 40, 50].
   • Folhas: [10, 20] <-> [30, 40, 50, 60]

4. Inclusão de 70:

   • A folha [30, 40, 50, 60, 70] está cheia. Divide.
   • Chave mediana: 50.
   • 50 é promovido para o nó interno (raiz [30]). Uma cópia de 50 permanece na folha à direita.
   • Raiz (interna): [30, 50] (não está cheia, pois ordem 5 permite até 4 chaves)
   • Folhas: [10, 20] <-> [30, 40] <-> [50, 60, 70]
   • Chaves replicadas em nós internos até agora: {30, 50}

5. Inclusão de 15:

   • Vai para a folha [10, 20].
   • Folhas: [10, 15, 20] <-> [30, 40] <-> [50, 60, 70]

6. Inclusão de 25:

   • Vai para a folha [10, 15, 20].
   • Folhas: [10, 15, 20, 25] <-> [30, 40] <-> [50, 60, 70]

7. Inclusão de 35:

   • Vai para a folha [30, 40].
   • Folhas: [10, 15, 20, 25] <-> [30, 35, 40] <-> [50, 60, 70]

8. Inclusão de 45:

   • Vai para a folha [30, 35, 40].
   • Folhas: [10, 15, 20, 25] <-> [30, 35, 40, 45] <-> [50, 60, 70]

9. Inclusão de 55:

   • Vai para a folha [50, 60, 70].
   • Folhas: [10, 15, 20, 25] <-> [30, 35, 40, 45] <-> [50, 55, 60, 70]

10. Inclusão de 65:

    • A folha [50, 55, 60, 65, 70] está cheia. Divide.
    • Chave mediana: 60.
    • 60 é promovido para o nó interno (raiz [30, 50]). Uma cópia de 60 permanece na folha à direita.
    • Raiz (interna): [30, 50, 60] (não está cheia, pois ordem 5 permite até 4 chaves)
    • Folhas: [10, 15, 20, 25] <-> [30, 35, 40, 45] <-> [50, 55] <-> [60, 65, 70]
    • Chaves replicadas em nós internos até agora: {30, 50, 60}

Ao final da sequência, os nós internos contêm as chaves [30, 50, 60].
As folhas contêm as chaves: [10, 15, 20, 25], [30, 35, 40, 45], [50, 55], [60, 65, 70].
Os valores que estão presentes tanto nas folhas quanto nos nós internos são 30, 50 e 60.

(A) Correta: Os valores 30, 50 e 60 foram promovidos de folhas para nós internos e, por serem de splits de folhas, uma cópia deles permanece na folha à direita, tornando-os replicados.
(B) Incorreta: Embora 30 esteja correto, os valores 10, 20 e 40 nunca foram promovidos para nós internos; eles permanecem apenas nas folhas. A armadilha aqui é confundir as chaves iniciais que compunham uma folha com as chaves que são efetivamente promovidas.
(C) Incorreta: Os valores 25, 40 e 55 nunca foram promovidos para nós internos; eles permanecem apenas nas folhas.
(D) Incorreta: Nenhum dos valores 10, 25, 40, 55 e 70 foi promovido para nós internos; eles permanecem apenas nas folhas.
(E) Incorreta: Nenhum dos valores 10, 40 e 70 foi promovido para nós internos; eles permanecem apenas nas folhas.