Questão FC373174
Determinada estrutura de dados foi projetada para minimizar o número de acessos à memória secundária. Como o número de acessos à memória secundária depende diretamente da altura da
Algoritmos e Lógica de Programação
FCC · 2019
Determinada estrutura de dados foi projetada para minimizar o número de acessos à memória secundária. Como o número de acessos à memória secundária depende diretamente da altura da estrutura, esta foi concebida para ter uma altura inferior às estruturas hierarquizadas similares, para um dado número de registros. Para manter o número de registros armazenados e, ao mesmo tempo, diminuir a altura, uma solução é aumentar o grau de ramificação da estrutura (o número máximo de filhos que um nó pode ter). Assim, esta estrutura possui um grau de ramificação geralmente muito maior que 2. Além disso, a cada nó são associados mais de um registro de dados: se o grau de ramificação de um nó for g, este pode armazenar até g-1 registros.
Esta estrutura de dados é utilizada em banco de dados e sistema de arquivos, sendo denominada
- árvore digital ou trie.
- árvore B.
- lista linear duplamente encadeada circular.
- árvore rubro-negra.
- árvore binária de busca não balanceada.
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
A árvore B é uma árvore de pesquisa multi‑way auto‑balanceada projetada para operar eficientemente em dispositivos de memória secundária (disco). Cada nó pode ter alto grau de ramificação, permitindo armazenar até \(g-1\) chaves quando o grau é \(g\), o que reduz muito a altura da árvore.
Por reduzir a altura, diminui o número de acessos a disco necessários em operações de busca, inserção e remoção. As operações têm custo proporcional à altura, tipicamente \(O(\log_g N)\), com \(N\) registros.
Os tamanhos dos nós são geralmente escolhidos para coincidir com o tamanho de bloco do dispositivo, otimizando leituras/gravações em bloco e minimizando E/S.
Além disso, a árvore B mantém-se balanceada após inserções e exclusões por meio de divisões e fusões de nós, garantindo desempenho estável em bancos de dados e sistemas de arquivos.
Conteúdo do catálogo FC Concursos · Atualizado em