Questão FC369524
No contexto de uma Árvore B, estrutura comumente utilizada na indexação de tabelas relacionais, considere as seguintes propriedades numa árvore B de grau g. 1. Todas as folhas estã
Sistema de Gerenciamento de Banco de Dados (SGBD)
FGV · 2024
No contexto de uma Árvore B, estrutura comumente utilizada na indexação de tabelas relacionais, considere as seguintes propriedades numa árvore B de grau g.
1. Todas as folhas estão no mesmo nível de profundidade na árvore.
2. Todos os nós podem conter, no máximo, 2g - 1 chaves.
3. Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, 3 chaves.
4. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n2).
5. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n).
Estão corretas apenas as afirmativas
- 1 e 2.
- 1, 2 e 3.
- 1, 2, 3 e 4.
- 1, 3, 4 e 5.
- 2, 4 e 5.
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
Todas as folhas estão no mesmo nível: essa é uma propriedade fundamental de uma Árvore B. Significa que a árvore é balanceada em termos de altura, o que garante caminhos de busca de comprimento semelhante para todas as chaves e, consequentemente, eficiência nas operações de busca, inserção e exclusão.
Máximo de chaves por nó: \(2g-1\): numa B-tree com grau (ou grau mínimo) \(g\) cada nó pode armazenar até \(2g-1\) chaves. Esse limite deriva da definição que associa a capacidade máxima de chaves ao dobro do grau menos um, garantindo espaço suficiente para operações de divisão (split) quando um nó fica cheio.
Adicionalmente, observa‑se que há um limite inferior de chaves por nó (geralmente \(g-1\)), com exceção da raiz, o que mantém a estrutura equilibrada e facilita rebalanceamentos controlados.
Conteúdo do catálogo FC Concursos · Atualizado em