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:

public class ArvoreB {
    private RandomAccessFile arquivo;     // arquivo contendo a árvore.
    private String           nomeArquivo; // nome do arquivo;
    // ...
    
    private class ArvoreB_Pagina {
        private   final int TAMANHO_REGISTRO = 12; // Tamanho de cada registro 
        protected final int TAMANHO_PAGINA;        // Tamanho de cada página (dependente da ordem)
        protected int    n;       // Quantidade de registros contidos na página
        protected int[]  chaves;  // Array contendo as chaves de cada registro 
        protected long[] dados;   // Array contendo os dados de cada registro 
        protected long[] filhos;  // Array contendo os enderecos das páginas filhas
        // ...
        
        public ArvoreB_Pagina(int ordem) {
            TAMANHO_PAGINA = 4 + (ordem - 1) * 20 + 8;
            this.ordem = ordem;
            n = 0;
            chaves = new int[ordem - 1];
            dados = new long[ordem - 1];
            filhos = new long[ordem];
            
            // Inicializa arrays.
            for (int i = 0; i < ordem - 1; i++) {
                chaves[i] = -1;
                dados[i] = -1;
                filhos[i] = -1;
            }
            
            filhos[ordem -1 ] = -1;
        }
        
        // ...
    }
    
    public ArvoreB(int ordem, String nomeArquivo) throws IOException {
        this.ordem = ordem;
        this.nomeArquivo = nomeArquivo;
        arquivo = new RandomAccessFile(nomeArquivo, "rw");
        
        if (arquivo.length() == 0) {
            arquivo.writeLong(-1); // Árvore vazia.
        }
    }
    
    // ...
}

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

Etapa de busca em uma árvore B

Exemplo de código em java:

public class ArvoreB {
    // Atributos da árvore.
    // ...
    
    private class ArvoreB_Pagina {
        // Atributos da página.
        // ... 
        
        public ArvoreB_Pagina(int ordem) {
            // Construtor da página que inicializa os atributos.
            // ...
        }
        
        protected byte[] getBytes() throws IOException {
            // Retorna um array de bytes com os dados da página.
            // ...
        }
        
        protected void setBytes(byte[] buffer) throws IOException {
            // Seta os dados da página.
            // ...
        }
    }
    
    public ArvoreB(int ordem, String nomeArquivo) {
        // Atributos da árvore.
    }
    
    public long buscar(int chaveBuscada) throws IOException {
        arquivo.seek(0); // Vai para a raiz da árvore.
        long raiz = arquivo.readLong(); // Lê a raiz
        long registro = (raiz != -1) ? buscar(chave, raiz) // Busca registro
                                     : -1; // Se árvore vazia, retorna -1;
        return registro; // Retorn o registro, encontrado ou não.
    }
    
    private long buscar(int chaveBuscada, long pagina) throws IOException {
        if (pagina == -1)
            return -1; // Pagina inexistente.
            
        // Carregando página atual.
        arquivo.seek(pagina);
        ArvoreB_Pagina pa = new ArvoreB_Pagina(ordem);
        byte[] buffer = new byte[pa.TAMANHO_PAGINA];
        arquivo.read(buffer);
        pa.setBytes(buffer);
        
        // Encontrando a página da chave que está sendo buscada.
        int i = 0;
        while (i < n && chaveBuscada > pa.chaves[i) {
            i++
        }
        
        if (i < pa.n) {
            if (chaveBuscada == pa.chaves[i]) // registro encontrado.
                return pa.enderecos[i];
                
            return buscar(chaveBuscada, pa.filhos[i]); // Desce para página filha.
        } else {
            return buscar(chaveBuscada, pa.filhos[i]); // Ultimo filho da página.
        }
    }
}

Inclusão

Vamos pegar a árvore a seguir como exemplo:

Exemplo de árvore b

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.

Inserção do Número 23 na árvore B

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:

Árvore exemplo após a inserção dos números 38 e 41

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 :

Divisão da página

E em seguida promover o número 38, e finalmente incluir o número 42 na árvore:

Árvore Final

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.