Árvore B*
Trabalho Universitário: Árvore B*. Pesquise 862.000+ trabalhos acadêmicosPor: alice_b • 18/6/2013 • 279 Palavras (2 Páginas) • 842 Visualizações
A árvore B* é uma estrutura de dados na ciência da computação e uma variação da árvore B proposta em 1973 por Donald E. Knuth. Esta apresenta mecanismos de inserção, remoção e busca muito semelhantes aos realizados em árvores B, mas com a diferença em que a técnica de redistribuição de chaves também é empregada durante as operações de inserção. Dessa maneira a operação de split pode ser adiada até que duas páginas irmãs estejam completamente cheias e, a partir daí, o conteúdo dessas páginas irmãs é redistribuído entre três páginas (uma nova criada e as duas páginas irmãs anteriormente cheias).5. Uma página não folha com k páginas filhas possui k-1 chaves
Comparação com árvores B
As chaves numa árvore B* ficam armazenadas nas páginas internas, folha e raiz. A principal diferença é relacionada ao momento de inserção de chaves, na qual utiliza a redistribuição de chaves entre páginas irmãs até que estas estejam completamente cheias. Desse modo a operação de split é atrasada até que duas páginas irmãs estejam completamente cheias, conferindo maior aproveitamento de espaço em arquivo.
Vale lembrar que a página raiz de uma árvore B* deve ser tratada de forma especial, pois esta não possui uma página irmã e, portanto, deve sofrer uma divisão do tipo one-to-two ou deve-se aumentar sua capacidade de armazenamento de chaves.
• A operação de Inserção de um registro em uma árvore B* é essencialmente igual à inserção de um registro em uma árvore B.
• A única diferença é que, quando uma folha é dividida em duas, o algoritmo promove uma cópia da chave que pertence ao registro do meio para a página pai no nível anterior, retendo o registro do meio na página folha da direita.
...