Algoritmos e Estruturas de Dados/Árvores B

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

Exemplo de Árvore B

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.

Introdução

O estudo das diferentes estruturas de dados vistas anteriormente foi realizado supondo um custo de acesso aos dados uniforme e da mesma ordem de grandeza que as demais operações. Porém, na prática, isso nem sempre é o caso. Em sistemas computacionais atuais, a memória é organizada hierarquicamente, sendo o custo de acesso inversamente proporcional ao custo financeiro. Por ordem decrescente de velocidade de acesso (e por ordem crescente de custo financeiro), temos: registros internos do processador, memória cache, memória principal (RAM), memória secundária (disco rígido), memória externa (mídia ótica, fitas).

Um exemplo é quando é preciso representar e manipular através de buscas, inserções e remoções, uma quantidade de dados tal que a capacidade da memória principal disponível não é suficiente. Neste caso, por razões econômicas (o custo de expansão da memória principal) ou tecnológicas (o maior tamanho de memória principal que o sistema operacional pode gerenciar), torna-se necessário recorrer a memória secundário para armazenar parte dos dados.

Historicamente, o tempo de acesso a memória secundária (discos ou fitas) sempre foi muito superior ao de acesso a memória principal. Nas tecnologias atuais, o fator relacionando esses dois tempos torna entre $10^{4}$ e $10^{5}$: o tempo de um acesso em memória secundária é equivalente ao tempo de execução de 10.000 a 100.000 instruções. Em geral, os sistemas gerenciadores de bancos de dados devem operar vários usuários em paralelo. Supondo uma média de 50 usuários concorrentes, e um tempo médio de acesso ao disco de 10ms, o número médio de acessos que um usuário pode fazer é de 2 por segundo.

Por exemplo, supõe que você deve elaborar um sistema de gerenciamento de um banco de dados que tem cerca de 25.000.000 (vinte-e-cinco milhões) de registros. Cada registro tem um tamanho de 1kB e uma chave de 4 bytes (supondo a existência de uma relação de ordem entre as chaves). A quantidade total de memória necessária é de 25 GB (vinte-e-cinco gigabytes). Se for usada uma árvore binária balanceada, por exemplo uma árvore rubro-negra, os números médio e máximo de acessos à memória secundária numa busca seria 48 ($\approx 2\times \log 25.000.000$)$. Os tempos médios e máximos de busca seriam portanto 12s e 24s. Em certas aplicações, esses números podem não ser aceitáveis.

As árvores B são um tipo de árvores de busca que foram projetadas para minimizar o número de acessos à memória secundária. Como o número de acessos à memória secundária depende diretamente da altura da árvore, as árvores B foram projetadas para ter uma altura inferior às árvores rubro-negras ou AVL, para um dado número de chaves. Para manter o número de registros armazenados e, ao mesmo tempo, diminuir a altura, uma solução é aumentar o grau de ramificação da árvore (o número máximo de filhos que um nó pode ter). Assim árvores B são árvores de busca que possuem um grau de ramificação geralmente muito maior que 2. Além disso, a cada nó de uma árvore B são associados mais de um registro de dados: se o grau de ramificação de um nó for $g$, este pode armazenar até $g-1$ registros. A figura abaixo mostra um exemplo de árvore B, com grau de ramificação dos nós de até 4.

Em geral o grau de ramificação de uma árvore B é determinado pelas características físicas da memória secundária empregada, pois memórias secundárias usualmente têm uma unidade atômica de leitura/escrita. Para armazenar uma árvore B, cada nó da árvore será armazenado numa unidade de memória secundária. Por exemplo, supondo que a unidade tem uma capacidade de 4kB e que seu endereço seja codificado sobre 4 bytes. O maior grau de ramificação possível neste caso é denotado $g_{max}$ e é tal que: $4.g_{max}+1024.(g_{max}-1)\leq 4096$, ou seja $g_{max}\leq 3$.

Esse grau de ramificação é muito perto do das árvores balanceadas. A altura do árvore B correspondente não será significativamente inferior a altura que teria uma árvore binária correspondente.

Uma alternativa é, no lugar de armazenar o registro inteiro no nó da árvore B, colocar a chave e uma referência a um unidade de disco que contem essa informação. Em nosso exemplo, o tamanho de uma referência é 4 bytes. Supondo que o tamanho da chave seja também de 4 bytes, o grau de ramificação é tal que: $(g_{max}\times 4)+[(g_{max}-1)\times (4+4)]\leq 4096$, ou seja $g_{max}=342$.

Neste caso, cada nó armazena 341 chaves com a referência ao registro correspondente. A raiz pode ter até 342 filhos e 116964 netos. A capacidade desta árvore B é $(1+342+342^{2})\times 341=40.001.674$ referências.

Supondo que a raiz sempre fica em memória principal, são necessários, no máximo, dois acessos a memória secundária para achar uma chave, e de um terceiro acesso para ler o registro correspondente. Utilizando os parâmetros da discussão acima, o tempo de espera do usuário devido as transações com a memória secundária cai para 1,5s (a comparar com as estimativas de até 24s com uma implementação por árvores rubro-negra).

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 $5/2$ 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

1. Primeiro, pesquise a posição onde este nó será incluído. Então, insira o valor dentro do nó.
2. Se nenhum nó ficou errado, acima ou abaixo da ordem div 2, o processo é terminado.
3. 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

1. Primeiro, busque um valor a ser excluído. Então, remova-o de dentro de um nó.
2. Se nenhum nó teve problema, o processo é terminado.
3. Se algum nó estiver errado, então há duas possibilidades:
   1. 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.
   2. 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.

Exercício

Seja uma árvore B de altura $a$ e grau máximo de ramificação $g_{max}$. Dar, em função de $a$ e $g_{max}$, o número máximo de referências que essa árvore B pode armazenar.

Ligações externas

• Animação de uma simples árvore B.
• Applet de uma B-Tree

Esta página é um esboço de informática. Ampliando-a você ajudará a melhorar o Wikilivros.