Árvore B*
Uma á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).
Tal técnica é conhecida como divisão two-to-three split, ou no português divisão de dois para três, que proporciona propriedades diferentes das árvores B na qual utiliza a divisão usual conhecida como one-to-two split. A grande melhoria direta proporcionada por essa abordagem é o melhor aproveitamento de espaço do arquivo, pois, no pior caso, cada página apresenta no mínimo 2/3 do número máximo de chaves que esta pode armazenar, enquanto na divisão usual cada página apresenta, no pior caso, metade do número máximo de chaves.
Definição
Segundo a definição de Knuth [1] uma árvore B* de ordem m apresenta as seguintes propriedades:
- Cada página apresenta no máximo m páginas filhas
- Uma página folha contém pelo menos ⌊(2m-1)/3⌋ chaves e no máximo m-1
- Todas as páginas folha estão no mesmo nível
- Toda página, exceto a raiz e as folhas possuem no máximo (2m-1)/3 descendentes
- Uma página não folha com k páginas filhas possui k-1 chaves
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Bstartree-overflow.svg/375px-Bstartree-overflow.svg.png)
Comparação com árvores B
Assim como as á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.
Ver também
- Árvore B
- Árvore B+
- Árvore AVL
- Árvore binária
Referências
- ↑ Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 372 A referência emprega parâmetros obsoletos
|coautor=
(ajuda)
Bibliografia
- Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. 590 páginas. ISBN 0-201-55713-4 A referência emprega parâmetros obsoletos
|coautor=
(ajuda)
- Langsam, Yedidyah; J. Augenstein, Moshe; M. Tenenbaum, Aaron (1996). Data Structures Using C and C++ (em inglês) 2 ed. [S.l.]: Prentice Hall. 672 páginas. ISBN 0-13-036997-7
- Knuth, Donald (1998). The Art of Computer Programming. Sorting and Searching (em inglês). 3 2 ed. [S.l.]: Addison-Wesley. ISBN 0-201-89685-0
Ligações externas
Dicionário de Algoritmos e Estrutura de dados