# Algoritmos/Estruturas de dados/Árvore B
## Visão Geral

A árvore B, Inventada por Rudolf Bayer e Edward Meyers McCreight em 1971, é uma estrutura de dados que se assemelha a uma árvore binária, com um diferencial em seus nós (páginas), que armazenam mais de uma chave. Assim, essa estrutura se mostra bastante eficiente ao se trabalhar com manipulação de arquivos, uma vez que é possível recuperar um número grande de elementos por vez e, consequentemente, reduzir a quantidade de acesso ao disco.
Uma árvore B é uma árvore equilibrada, de modo que todas as suas folhas devem estar no mesmo nível (mesma distância da raiz). Como já visto, cada página pode conter vários elementos. As quantidades mínima e máxima de elementos são calculadas com base em uma característica da árvore chamada de ordem, que pode apresentar as seguintes definições:
* Quantidade mínima de elementos que cada página (exceto raiz) pode ter (Cormen, 2001,; Bayer e McCreigth, 1972).
* Quantidade máxima de filhos que cada página pode ter (Knuth, 1978).
Além disso, a árvore deve seguir algumas características específicas. São elas:
* Cada página deve ter pelo menos 50% de ocupação, levando em consideração a ordem da árvore (com exceção da raiz).
* O número de filhos deve ser o número de chaves + 1, com exceção das folhas que não possuem nenhum filho.
* Todas as folhas devem estar no mesmo nível, o que faz com que o crescimento da árvore seja sempre para cima.

## Árvore B em disco

Uma árvore B, organizada em disco, deve apresentar no início do arquivo um cabeçalho contendo metadados da árvore. Nesse cabeçalho deve existir um ponteiro para a raiz da árvore, além de outras informações como a ordem da árvore, caso necessário. Alem disso, cada página da árvore deverá conter os dados de cada registro armazenado e os ponteiros para as páginas filhas. Estrutura de uma página em disco, em uma árvore de ordem 5 (definição de Knuth)
* N: Quantidade de registros contidos na página.
* P: Ponteiros para as páginas filhas.
* C: Chave de cada registro.
* D: Dados de cada registro.
Exemplo da estrutura de uma árvore em Java:

## Operações Básicas
#### Busca

O método empregado na busca de uma chave qualquer em uma árvore B é semelhante ao utilizado na busca em uma árvore binária de busca. O caminho percorrido no processo de busca em uma árvore B é o mesmo que em uma árvore binária, sendo apenas necessário acrescentar testes relativos às diversas chaves existentes em cada página (Kutova, 2016). Ao percorrer cada página, deve-se verificar se a chave que está sendo buscada é maior que a chave referente a posição atual da página. Caso a resposta seja sim, continua-se a procura na página atual. Por outro lado, se a chave for menor, deve-se descer para a página filha e continuar a busca (se já estiver em uma folha, a chave não está na árvore).
A figura a seguir mostra um exemplo de busca.
* Ordem da árvore: 3 (definição de Knuth).
* Chave buscada: 6
Exemplo de código em java:

### Inclusão

Vamos pegar a árvore a seguir como exemplo:
Essa operação na árvore B segue duas situações de inserção(Kutova, 2016).
1.Se o elemento couber na página, basta inclui-lo de forma ordenada.
2. Se o elemento não couber na página. Neste caso a página deve ser dividida em duas e o elemento do meio deverá ser promovido , afim de se tornar pai de duas folhas. Para ilustrar vamos inserir o número 42 na árvore abaixo:
No entanto devido a inserções posteriores do número 38 e do número 41, a página agora não oferece espaço suficiente para acomodar o número 42. Vamos então dividir essa pagina, criando duas novas folhas :
E em seguida promover o número 38, e finalmente incluir o número 42 na árvore:

## Bibliografia

* KUTOVA, Marcos. Notas de Aula.
* KUTOVA, Marcos. Algoritmos e Estruturas de Dados III. Belo Horizonte, 2016. Apostila.
* ÁRVORE B. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2017. Disponível em: <https://pt.wikipedia.org/w/index.php?title=%C3%81rvore_B&oldid=48443353>. Acesso em: 20 maio. 2017.