Mostrar código-fonte de Estruturas de Dados Intermediário/B-Tree

[[Imagem:B-tree-definition.png|thumb|300px|right|Exemplo de Árvore B]]

'''Árvore B''' ou B-Tree são estruturas de dados  muito utilizadas em banco de dados e sistema de arquivos.

Para inserir ou remover variáveis de um nó, o nó não poderá ultrapassar sua ordem e nem ser menor que sua ordem dividida por dois. Árvores B não precisam ser rebalanceadas como são freqüentemente as árvores de busca binária com Árvore AVL. Árvores B têm vantagens substanciais em relação a outros tipos de implementações quanto ao tempo de acesso e pesquisa aos nós.

O criador das árvores B, Rudolf Bayer, não definiu claramente de onde veio o ''B'' das árvores B. Ao que parece, o ''B'' vem de ''balanceamento'' onde todos os nós da árvore estão em um mesmo nível. Também é possível que o ''B'' tenha vindo de seu sobrenome ''Bayer'', ou ainda do nome da empresa onde trabalhava Boeing, no ''Boeing Scientific Research Labs''.

== Estrutura do nó ==

Nós em árvores B, também denominado páginas, geralmente são representados por um conjunto de elementos apontando para seus filhos. Alguns autores consideram a ordem de uma árvore B como sendo a quantidade de registros que a página pode suportar. Outros consideram a ordem como a quantidade de campos apontadores. Todo nó da árvore tem um mínimo de registros definido pela sua ordem, que é a metade da ordem, arredondando-se para baixo, caso a árvore seja de ordem ímpar, exceto a raiz da árvore, que pode ter um mínimo de um registro. Por exemplo, os nós de uma árvore de ordem 5, podem ter, no mínimo <math>5/2</math> registros, ou seja, dois registros. A quantidade de filhos que um nó pode ter é sempre a quantidade de registros do nó mais 1 (V+1). Por exemplo, se um nó tem 4 registros, este nó terá obrigatoriamente 5 apontamentos para os nós filhos.

== Algoritmos ==
=== Inserção ===

# Primeiro, pesquise a posição onde este nó será incluído. Então, insira o valor dentro do nó.
# Se nenhum nó ficou errado, acima ou abaixo da ordem div 2, o processo é terminado.
# Se algum nó ficar acima da ordem, dividimos o nó, o valor central do nó dividido sobe para a posição do pai, continuando assim recursivamente por toda a árvore. Se o nó estourar na raiz, então é criado um novo nó raiz (podendo ter um único elemento).

=== Exclusão === 

# Primeiro, busque um valor a ser excluído. Então, remova-o de dentro de um nó.
# Se nenhum nó teve problema, o processo é terminado.
# Se algum nó estiver errado, então há duas possibilidades:
## Se o nó ao lado do nó errado pode transferir um ou mais de seus nós filho ao nó atual, então o nó atual voltará ao normal. Após ter atualizado os valores da separação do pai e dos dois filhos, o processo é terminado.
##Se o nó ao lado do nó errado não tem um filho extra porque está no limite mais baixo, então ambos os nós serão fundidos em um único nó. Continuando até que o nó atual esteja normal.

==Ligações externas==
* [http://www.cse.ohio-state.edu/~bondhugu/acads/234-tree/index.shtml Animação de uma simples árvore B].
* [http://slady.net/java/bt/ Applet de uma B-Tree]

[[Categoria:Estrutura de Dados II|{{PAGENAME}}]]