• Abrir documentação e código fonte.
• Baixar projeto contendo a Árvore B.

Novamente, outro post ecológico! Após a apresentação da Árvore AVL, porque não agora Árvores B?

Árvores B são estrutura de dados bastante utilizadas em sistemas de arquivos e bancos de dados. São geralmente mais densas em informação por nível em comparação com Árvores AVL, o que significa que possuem geralmente uma altura menor mesmo armazenando um mesmo número de elementos.

Em primeiro lugar, devo especificar que este artigo não se destina a explicar o funcionamento das Árvores B em detalhes. Para isto temos uma variedade de fontes e recursos à nossa disposição; descrições sobre o funcionamento de uma Árvore B são facilmente encontradas na internet.

Uma coisa, no entanto, infelizmente não é: Implementações compreensíveis que também sejam, ao mesmo tempo, completas e funcionais.

Como exemplo, não raro encontramos o mesmo problema que tivemos ao encontrar informações sobre Árvores AVL. É dada menos ênfase aos métodos de remoção destas estruturas. Ou então, por vezes encontramos a Árvore B implementada fora de seu contexto: em memória. Árvores B reais servem ao propósito de serem armazenadas em disco; por isso seus nós são geralmente denominados páginas.

Introdução

Imagine que uma Árvore AVL contenha tantos dados que já não caiba mais em memória. Tentando contornar esta situação, podemos definir uma estratégia em que cada nó da Árvore AVL (que armazena no máximo 1 elemento) ocupe uma posição diferente dentro de um mesmo arquivo de dados. Para acessar um filho de um nó, por exemplo, podemos ler em qual posição o filho se encontra, navegar até a posição determinada e o carregarmos em memória. É fácil ver que esta solução resolve o problema da memória, pois a cada vez iremos carregar apenas a informação com o qual queremos trabalhar, e nunca a árvore toda.

Porém, imagine agora que gostaríamos de percorrer a árvore em busca de um elemento qualquer. Imagine também que o elemento em questão não está contido na árvore e que esta árvore tem, em termos gerais, n níveis de altura. Utilizando o algoritmo de busca em árvore binária, teremos de fazer, no mínimo, n leituras em disco para buscar a informação que queremos. Ou melhor, para concluir que não pudemos encontrar a informação que queríamos. Apenas relembrando, não esqueça o fato de que memórias secundárias como o disco rígido são geralmente ordens de magnitude mais lentas do que a memória principal.

Para n pequeno, é evidente que isto não faz diferença – o tempo de acesso a um disco rígido é, geralmente, de alguns milisegundos. Mas lembrando que como estamos falando de árvores realmente grandes, o acesso ao disco pode tornar-se um gargalo considerável.

Nesse contexto, a estrutura AVL torna-se bastante ineficiente. Como então solucionar este problema?

R: Diminuindo o número de seeks necessários para se alcançar uma informação.

A Árvore B (ou B-Tree) emprega uma estrutura paginada ideal para minimizar o acesso em disco. Cada um de seus nós contem não um elemento, mas vários; quantos seu desenvolvedor quiser. A cada acesso, várias, e não apenas uma informação, são lidas de cada vez. Desta maneira a informação torna-se muito mais condensada nos primeiros níveis, e altura da árvore diminui consideravelmente.

Citando a Wikipedia:

Em ciência da computação, Árvore B ou B-Tree é uma estrutura de dados árvores que são 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.

Esta é uma apresentação bastante razoável. No entanto, certa cautela precisa ser tomada pois autores diferentes tratam a ordem da Árvore B de maneiras diferentes, como por exemplo no livro Algoritmos – Teoria e Prática. Neste livro, os autores se referem não à ordem da Árvore, mas à seu grau t, definido como o número mínimo de filhos que um nó não-raiz pode possuir. Como consequência, o número mínimo de elementos de uma Árvore poderá ser tomado como t-1 e o máximo como 2t-1. Com isso, acabam efetivamente definindo a ordem da árvore (a que me refiro como sendo o número máximo de filhos de um nó) como 2t e o número máximo de elementos como 2t-1. Apesar de se enquadrar dentro das regras enunciadas acima na definição da Wikipedia, a apresentação de Árvores B desta forma inclui um pequeno problema.

A ordem de das árvores ficará restrita a termos pares (que estejam na forma 2t), o que simplifica os algorítmos de inserção e remoção, mas acabam por não mais descrever à uma Árvore B de ordem geral.

Por esta razão, o código que apresentaremos e documentaremos a seguir se adequa à Árvores B de qualquer ordem.

Propósito

Como bem sabemos, o propósito de uma Árvore B é otimizar o acesso e a manipulação da informação armazenada em discos, servindo geralmente como estrutura de índice à outros arquivos de registros no qual o índice pode se tornar muito grande para caber em memória. Neste contexto, atuando como índice, a árvore armazenará uma chave e a posição relativa em arquivo (relative record number ou byte offset) em que o registro se encontra no arquivo de registros.

Definições

Antes de prosseguirmos, enunciaremos primeiro algumas definições para que não haja confusão no decorrer deste artigo:

A ordem m da árvore está definida como o número máximo de filhos que um único nó pode possuir;

Logo, o número máximo de elementos num nó e dado por m-1 e o máximo de filhos por m. Já o número mínimo de elementos que um nó pode possuir é dado pela fórmula floor((m-1) / 2).

A Árvore B está implementada em arquivo, então definimos “Offset” como um typedef para long int. Para representar o equivalente em arquivo para o ponteiro nulo (NULL) utilizaremos o valor constante NULLOFFSET como -1L (menos-um na forma de long int). Esta é uma prática comum pois a posição 0, em arquivo, é uma posição válida, ao contrário de seu equivalente em memória.

Implementação

O código que apresentamos e documentamos a seguir se adequa à Árvores B de quaisquer ordens. A implementação foi feita em C++ no Microsoft Visual Studio, sem utilizar as extensões .NET/CLI (apesar da solução, em si, possuir código misto pois estava atrelada à uma interface gráfica em WinForms).

Clique aqui para ver o código e a documentação completos da Árvore B (BTree) em Arquivo (em C++) gerados pela ferramenta Doxygen. O código é, claro, livre para quaisquer adaptações desde que permaneça sob a Licença MIT e suas informações autorais sejam mantidas. Mas lembre-se de que o código tem fins meramente educativos e não deve ser utilizado num ambiente onde a performance é um fator crítico. Ou, melhor, não deve ser utilizado em outro lugar fora um trabalho acadêmico simples.

Diagrama de Classes

O Nó (BTreeNode)

O nó da Árvore B, aqui chamado de BTreeNode, pode conter vários elementos, em contraste com a Árvore AVL, em que pode haver apenas um. A Árvore B pode ser vista como uma generalização da Árvore AVL para ordens superiores, ou a Árvore AVL como uma especialização da Árvore B para ordem 2 (m=2).

Assim, o nó deve conter um vetor de elementos e um vetor de filhos, onde estes filhos, ao invés de conter ponteiros em memória, contem ponteiros em arquivo (Offsets) para os próximos nós.

É nesta classe que estão contidos os métodos split() e merge(), que divide um nó em dois e intercala dois nós em um único nó, respectivamente. Estes métodos são chamados durante a operação de Inserção ou de Remoção pela classe principal BTree, que é a classe gerenciadora dos nós. Mais informações serão apresentadas à seguir.

A Lista de Disponíveis (DStack)

Como a estrutura da Árvore B é mantida em arquivo, não basta alocarmos/desalocarmos nós em memória utilizando new e delete como fazíamos na Árvore AVL. Temos que alocar uma posição no arquivo que acomoda a árvore e armazenar o nó nesta posição; ao deletarmos um nó temos que, de algum modo, avisar que a posição que antes acomodava o nó agora está vaga. Para isto, utilizamos outra estrutura em arquivo denominada lista de disponíveis, que é responsável por registrar, na forma de uma lista encadeada, onde estão os registros disponíveis e assim indicar qual a próxima posição vaga no arquivo. Para simplificação, esta lista é, na verdade, geralmente implementada como uma pilha.

Assim, suponha que a pilha está vazia (a posição inicial registrada é NULLOFFSET) e a posição 241 foi desocupada. Então ao chamar o método push(241) a lista de disponíveis deverá caminhar até a posição 241, escrever NULLOFFSET e então registrar que 241 é o começo da pilha.

Agora suponha que 340 foi desocupada. Então o método push(340) irá caminhar até a posição 340, escrever 240, que é o endereço do nó que antes era começo da pilha, e registrar que a pilha começa agora na posição 340. Assim por diante, push(500) caminhará até a posição 500, escreverá o endereço do começo anterior (340) e registrará que a posição inicial é, agora, 500. Assim, os nós vão se encadeando – cada posição disponível carrega uma referência a próxima posição disponível ou a NULLOFFSET se não há nada mais além daquele ponto.

Para remover, pop() simplesmente deverá ler quem é a posição inicial, e, caso seja diferente de NULLOFFSET, caminhar até esta posição, ler qual é o endereço do próximo nó (ou NULLOFFSET, caso não haja mais nós) e então registrar esta posição como a nova posição inicial.

Clique aqui para visualizar a implementação da lista de disponíveis em C++.

A Árvore (BTree)

A classe BTree, ou Árvore B, deve ser responsável por gerenciar seus nós, alocando, dealocando, carregando e descarregando, tentando o máximo possível minimizar a quantidade de nós carregados em memória de cada vez. É nela que estão contidos os métodos de inserção e remoção, que em nossa implementação são recursivos.

Abaixo está uma pequena descrição sobre o funcionamento da inserção e remoção, porém note que seus códigos correspondentes são, na verdade, bem mais elaborados que esta pequena introdução. Felizmente, há comentários no decorrer do código para auxiliar em seu entendimento.

Inserção / Split

O método de inserção da classe BTree pode cair no caso em que não é mais possível armazenar informação num nó pois este está cheio. Quando isto acontece, chama-se o método-membro Split do nó que está cheio, que dividirá o nó em dois e retornará uma referência em arquivo (Offset) ao novo nó criado durante a divisão. O método que controla a inserção está presente na classe BTree, enquanto o split pertence ao BTreeNode.

Remoção / Merge

Analogamente a inserção, o método de remoção da classe BTree poderá cair no caso em que seja necessário remover um elemento de um nó mas efetuar esta operação violaria a regra sobre o número mínimo de elementos que um nó deve conter. Neste caso, a árvore pode encontrar o elemento sucessor (imediatamente seguinte) ao elemento que estamos tentando remover, trocar os dois e então remover o substituto recursivamente, ou, caso não seja possível emprestar de ninguem, realizar uma intercalação entre dois nós mínimos formando um novo nó completo. Esta intercalação é conhecida como merge. O método que controla a remoção está presente na classe BTree, enquanto o merge pertence ao BTreeNode.

Código fonte em C++

O código fonte pode ser navegado na íntegra clicando-se aqui. Para fazer download de uma solução Visual Studio 2008 contendo o fonte, clique aqui.