Árvore B
Em ciência da computação, uma árvore B é uma estrutura de dados em árvore, auto-balanceada, que armazena dados classificados e permite pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico. A árvore B é uma generalização de uma árvore de pesquisa binária em que um nó pode ter mais que dois filhos. Diferente das árvores de pesquisa binária auto-balanceadas, a árvore B é bem adaptada para sistemas de armazenamento que leem e escrevem blocos de dados relativamente grandes, como discos.
Os dispositivos de memória de um computador consistem na memória principal e secundária, sendo cada uma delas com suas características. A memória primária é mais conhecida como memória volátil de endereçamento direto (RAM), esta por sua vez apresenta baixo tempo de acesso, porém armazena um volume relativamente pequeno de informação e altos custos. Já a memória secundária, possui um endereçamento indireto, armazena um grande volume de informação e possui um acesso (seek) muito lento quando comparada com a memória primária. A árvore B é uma solução para cenários em que o volume de informação é alto (e este não pode ser armazenado diretamente em memória primária) e, portanto, apenas algumas páginas da árvore podem ser carregadas em memória primária. As árvores B são organizadas por nós, tais como os das árvores binárias de busca, mas estes apresentam um conjunto de chaves maior do que um e são usualmente chamados de páginas. As chaves em cada página são, no momento da inserção, ordenadas de forma crescente e para cada chave há dois endereços para páginas filhas, sendo que, o endereço à esquerda é para uma página filha com um conjunto de chaves menor e o à direita para uma página filha com um conjunto de chaves maior. A figura acima demonstra essa organização de dados característica. Se um nó interno x contém n[x] chaves, então x tem n[x] + 1 filhos. As chaves do nó x são usadas como pontos de divisão que separam o intervalo de chaves manipuladas por x em x[x] subintervalos, cada qual manipulado por um filho de x.
Nó ou página
Um nó ou página, geralmente é representado 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 metade da ordem, arredondando-se para baixo, caso a árvore seja de ordem ímpar, exceto a raiz da árvore, que pode ter o mínimo de um registro. Por exemplo, os nós de uma árvore de ordem 5, podem ter, no mínimo ⌊ 5 / 2 ⌋ {\displaystyle \lfloor 5/2\rfloor } 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.
Página raiz
A página raiz das árvores B possuem o limite superior de d-1 chaves armazenadas, mas não apresentam um número mínimo de chaves, ou seja, elas podem ter um número inferior a ⌈d/2⌉-1 de chaves. Na figura acima, essa página é representada pelo nó que possui o registro 7 e 16.
Páginas internas
As páginas internas são as páginas em que não são folhas e nem raiz, estas devem conter o número mínimo (⌈d/2⌉-1) e máximo (d-1) de chaves.
Páginas folha
Estes são os nós que possuem a mesma restrição de máximo e mínimo de chaves das páginas internas, mas estes não possuem apontadores para páginas filhas. Na figura acima são todos os demais nós exceto a raiz.
Estrutura da página
Uma possível estrutura de dados para uma página de árvore B na linguagem C:
O número de acessos ao disco exigidos para a maioria das operações em uma árvore B é proporcional a altura da árvore B. Para construir uma árvore B, primeiro criamos um nó raiz vazio,e depois inserimos novas chaves. Esses procedimentos alocam uma página de disco para ser usada como um novo nó no tempo O(1) As operações básicas sobre uma árvore B são a busca, inserção e remoção de chaves.
Busca
A busca de uma chave k em uma árvore B é muito parecido com uma busca em árvore binária, exceto pelo fato de que, em vez de tomar uma decisão de ramificação binária ou de “duas vias” em cada nó, tomamos uma decisão de ramificação de várias vias, de acordo com o número de filhos do nó. Em cada nó interno x, tomamos uma decisão de ramificação de (n[x] + 1) vias. Esse método toma como entrada um ponteiro para o nó de raiz de uma subárvore e uma chave k a ser pesquisada.
Inserção
A operação de inserção, inicialmente com a árvore vazia, deve garantir que o nó raiz será criado. Criado o nó raiz, a inserção das próximas chaves seguem o mesmo procedimento: busca-se a posição correta da chave em um nó folha e insere a chave garantindo a ordenação destas. Após feito isso, considerando a abordagem de inserção de baixo para cima (Bottom-up) na árvore B, podem ocorrer duas situações: Uma abordagem melhorada para a inserção é a de cima para baixo (Top-down) que utiliza uma estratégia parecida com a inserção de baixo para cima, a lógica para a inserção das próximas chaves (levando em consideração que a raiz já está criada) é a seguinte: busca-se a posição correta da chave em um nó, porém durante a busca da posição correta todo nó que estiver com o número máximo de chaves (d-1) é feita a operação de split, adicionando o elemento intermediário na sequência ordenada de chaves da página no pai e separando os elementos da página em outras duas novas páginas, onde uma vai conter os elementos menores que o elemento intermediário e a outra os elementos maiores que ele, a inserção será feita em um nó folha somente após todo o processo de split e insere a chave garantindo a ordenação destas. Esta abordagem melhorada previne de ter que ficar fazendo chamadas sucessivas ao pai do nó, o que pode ser caro se o pai estiver na memória secundária.
Remoção
A remoção é análoga a inserção, sendo que o algoritmo de remoção de uma árvore B deve garantir que as propriedades da árvore sejam mantidas, pois uma chave pode ser eliminada de qualquer página e não apenas de páginas folha. A remoção de um nó interno exige que os filhos do nó sejam reorganizados. Como na inserção, devemos nos resguardar contra a possibilidade da eliminação produzir uma árvore cuja estrutura viole as propriedades de árvores B. Lembrando que devemos assegurar que um nó não ficará pequeno demais durante a eliminação (a não ser pelo fato da raiz pode ter essa pequena quantidade de filhos). O método para remover a chave k da subárvore com raiz em x deve estar estruturado para garantir que quando ele for chamado recursivamente em um nó x, o número de chaves em x seja pelo menos o grau mínimo t. Essa condição exige uma chave além do mínimo exigido pelas condições normais da árvore B, de forma que, quando necessário, uma chave seja movida para dentro do nó filho.
Busca
Neste algoritmo recursivo os parâmetros recebidos inicialmente devem ser a chave buscada e um ponteiro para a página raiz da árvore B.
Inserção
O algoritmo de inserção em árvore B é um procedimento recursivo que inicialmente ponteiroRaiz aponta para a raiz da árvore em arquivo, key é a chave a ser inserida e chavePromovida representa a chave promovida após um split de uma página qualquer.
Imprimir em Ordem em C
Algoritmo Split dentro da Classe Node em Java
Árvores 2-3-4 são um tipo de árvore B que possuem uma, duas ou três chaves. E, consequentemente, dois, três ou quatro filhos. São utilizadas na implementação de dicionários. Além disso, servem como base para o desenvolvimento do código de árvores preto e vermelho. Existem três situações na mudança de árvore B para árvore rubro-negra: Aplicando essas situações, deve-se checar se as propriedades de árvores rubro-negra são mantidas como o valor do nó da esquerda ser menor que o nó atual.
As árvores B não são as únicas estruturas de dados usadas em aplicações que demandam a manipulação de grande volume de dados, também existem variações desta que proporcionam determinadas características como as árvores B+ e B*. Estas, por sua vez, se assemelham muito com as árvores B, mas possuem propriedades diferentes.
Se compararmos as árvores B com suas variações podemos enumerar algumas características importantes para a escolha de implementação destas:
Além de sua utilização em bancos de dados, uma Árvore B (ou uma variante) também é usada em sistemas de arquivos para permitir acesso aleatório rápido a um bloco arbitrário em um arquivo particular. O problema básico consiste em transformar o bloco de arquivos i {\displaystyle i} em um endereço de bloco de disco (ou talvez para um cilindro-cabeça-sector). O sistema de arquivos da Apple HFS+, NTFS da Microsoft, AIX (JFS2) e alguns sistemas de arquivos Linux, como btrfs e Ext4, usam árvores B. Árvores B* são usadas nos sistemas de arquivos HFS e Reiser4.


