Árvore B

Exemplo de Árvore B

Em computação, Árvore B ou B-Tree é uma estrutura de dados pertencente ao grupo das árvores, e é muito utilizada em banco de dados e em sistemas de arquivos.

Para inserir ou remover variáveis de um nó, a quantidade de descendentes no nó não poderá ultrapassar sua ordem e nem ser menor que sua ordem dividida por dois (fator de preenchimento). Á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 folhas 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, a Boeing Scientific Research Labs.

Definição

Uma árvore B de ordem "m" é uma árvore que atende as seguintes propriedades:

1. Cada nó tem no máximo "m" filhos
2. Cada nó (exceto a raíz e as folhas) tem pelo menos "m/2" filhos
3. A raiz tem pelo menos dois filhos se ela mesma não for uma folha
4. Todas as folhas aparecem no mesmo nível e carregam informação
5. Um nó não-folha com "k" filhos deve ter k-1 chaves

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, estes que por sua vez também podem ser conhecidos como folhas. 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 número mínimo de elementos, que é dado pela metade do valor da ordem do nó, truncando o número caso a árvore seja de ordem ímpar, exceto para a raiz da árvore, que pode ter o mínimo de um registro. Por exemplo, os nós de uma árvore de ordem 5, devem ter, no mínimo $5/2=2,5$ 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.

Exemplo de estrutura em C:

#define M 5 //ordem da arvore

struct No{
    int n;
    char chave[M-1];
    struct No *pProx[M];
};

Algoritmos

Inserção

Iterações da inserção de valores em uma Árvore B.

1. Primeiro pesquise a chave, para ter a certeza de que esta não existe na árvore.
2. Depois, busque a posição onde esta será inserida. Teste para ver se o nó está cheio.
3. Se nó estiver vazio, insira o valor dentro dele, senão execute uma subdivisão do nó da seguinte forma:
   1. Verifique se o nó-pai está vazio, se sim execute
      1. Passe o elemento do meio do nó para seu pai.
      2. Divida o nó em dois nós iguais.
   2. Se o nó pai estiver cheio, repita as duas linhas acima recursivamente.(Caso todos os nós-pai estiverem cheios, inclusive a raiz, deve ser criada uma nova raiz aumentando assim a altura da árvore.
   3. Somente após satisfazer todas divisões necessárias, insira nova chave.

Exclusão

1. Primeiro pesquise a chave para ter a certeza de que esta existe na árvore.
2. Se existir, verifique se está em folha, e faça a exclusão.
3. Se existir e não estiver em folha, substitua esta chave pela menor chave do filho a direita.
   1. Se o número de chave no nó, for maior do que (Ordem/2 - 1), então termine a rotina.
   2. Senão redistribua as chaves entre os nós vizinhos.

Busca

1. Indique a chave que será procurada.
2. Pesquise desde a raiz até encontrá-la, e então retorne o nó e a posição desta.
3. Se a chave não for encontrada, continue o laço até encontrar um nil das folhas.

Vantagens

1. Melhor desempenho por ter um número menor de nós do que uma árvore binária, por exemplo. Menos nós, significa menos altura que resulta em menos acessos ao disco.
2. Por garantir poucos ponteiros entre os nós, há uma economia de espaço.
3. Maior rapidez em buscas pela utilização de chaves primárias.
4. Sua estrutura é dinâmica, ajustando automaticamente o balanceamento da árvore, a cada inclusão/exclusão.
5. Permite um tempo de acesso de dados menor, em uma busca aleatória, por causa de suas ramificações.

Desvantagens

1. Nó não folha com n chaves, é visitado n vezes, portanto o processo de busca às vezes pode se tornar lento.
2. As árvores B+ sempre mantém uma cópia de todos os dados nas folhas, o que em caso de necessidade de imprimir toda ela, por exemplo, permite uma rápida busca linear, fazendo com que a Árvore B, em comparação, tenha menor performance.

Comparações com outras Estruturas de Dados

Inserção: Mais veloz se comparado à tabelas de hash, por sua capacidade de se ajustar e balancear a cada inserção, isto significa menores colisões, e consequentemente menos laços para encontrar uma posição livre. No caso de precisar expandir, a duplicação é feita somente na folha, e nos nós correspondentes se necessário, o que garante menor espaço vazio alocado e menos ocupação em disco, ao contrário do hash que duplica a tabela por inteiro.

Exclusão: No caso de uma exclusão, Arvores B são capazes de evitar grandes fragmentações, pois se ajustam e balanceiam também nesse momento. Já em tabelas de hash, quando há exclusão de uma chave, o espaço alocado para esta fica vazio, porém ainda alocado. Maior fragmentação significa menor desempenho.

Busca: Árvores B são tão boas e velozes quanto tabelas de hash numa busca por igualdade, porém são muito superiores em velocidade e desempenho em buscas do tipo range. A superioridade da Árvore B, se basea na chave primária, onde a busca começa pela raiz e é direcionada aos nós e filhos de acordo com a chave procurada, isto torna mais objetivo e direto o resultado final. Porém, se comparado a Árvore B+, sua performance pode cair um pouco em uma busca linear. Árvores do tipo B+, sempre têm uma cópia de todos os nós nas folhas, sendo assim, é necessário apenas percorre-las para se ter uma visão completa de todas as chaves da estrutura.

Ver também

• Árvore de busca binária
• Árvore binária
• Árvore B+
• Árvore AVL

Ligações externas

• Animação de uma simples árvore B.
• Applet de uma B-Tree segundo a definição de Bayer & McCreight (1972)
• Aplicação em MS Visual C# que implementa um B-Tree orientada a objetos