Questão 2802727

Considere árvores B não vazias, com grau mínimo t ≥ 2. Para árvores B+, adote a convenção usual de sistemas de indexação: todas as chaves de dados permanecem nas folhas, enquanto os nodos (nós) internos armazenam apenas chaves separadoras; todas as folhas estão na mesma profundidade. Nesse contexto, analise as assertivas a seguir:

I. Em uma árvore B de grau mínimo t, todo nodo não raiz armazena entre t−1 e 2t−1 chaves; a raiz armazena entre 1 e 2t−1 chaves.

II. A altura de uma árvore B aumenta somente quando a raiz é dividida e diminui somente quando, após uma fusão, uma raiz interna fica sem chaves e é substituída por seu único filho.

III. Na inserção em uma árvore B+, a divisão de uma folha cheia remove da folha a chave separadora promovida ao pai, exatamente como ocorre na divisão de um nodo em uma árvore B convencional.

IV. A altura h de uma árvore B de grau mínimo t, com n chaves, satisfaz h ≤ log_t((n+1)/2). Para t=500 e n=10⁹, conclui-se que h ≤ 3; ou seja, o caminho da raiz até uma folha contém no máximo 4 nodos. Assumindo um nodo por página de disco e a raiz residente em memória principal, uma busca exige, no máximo, 3 acessos a disco.

Quais estão corretas?