B-Árvores

Autor: Luiz Filipe de Almeida

Dado um inteiro m >= 2, uma B-árvore de ordem m é um árvore multiária de busca que satisfaz as seguintes condições:

• a raiz contém entre 1 e 2m-1 chaves (e tem entre 2 e 2m filhos);
• todas as demais células contém entre m-1 e 2m-1 chaves (e têm entre m e 2m filhos);
• todas as folhas da árvore têm a mesma profundidade.

Fato: Para uma B-árvore de ordem t com n >= 1 elementos e altura h vale:

Representação de uma célula

A célula genérica de uma B-árvore pode ser descrita em C através de uma struct do tipo:

onde:

• ORDEM é especificado em um #define apropriado.
   Ex.: #define ORDEM 3 // define que a B-árvore terá ordem 3
• nchaves é o número de chaves efetivamente ocupadas na célula
• A ordem das chaves dentro da célula é tal que: v->chave[0] < v->chave [1] < ...
• A sub-árvore v->filho[i] contém chaves com valores entre v->chave[i-1] e v->chave[i+1]. É isso que torna a B-árvore uma árvore de busca.
• se v for uma folha, v-> folha recebe o valor TRUE; caso contrário, folha tem valor FALSE.

Operações em B-árvores

Listagem

Para percorrer e imprimir todos os elementos de uma B-árvore, basta uma função simples como esta:

void percorreB (struct celula_B* r)
// recebe um apontador para uma B-árvore e imprime a chave de todas as suas células
{
  int i;
  if (r != NULL)
  {
    for (i = 0; i < r->nchaves; i++)
    {
      percorreB (r->filho[i]);
      printf ("%d", r->chave[i]);
    }
    percorreB (r->filho[r->nchaves+1]);
  }
}

Busca

struct B_celula*
buscaB ( struct B_celula*r, int x)
// devolve um apontador para a célula da árvore que contém a chave x
{
  if (r == NULL) return NULL;
  for (i = 0; i < r->nchaves && r->chave[i] < x, i++);
  if (i == r->nchaves) return buscaB (r->filho[i], x);
  if (r->chave[i] == x) return r;
  return buscaB(r->filho[i], x);
}

Inserção

Inserir um elemento em uma B-árvore é um pouco mais complicado que inserir um elemento em uma árvore binária de busca. Uma operação fundamental usada durante a inserção é a quebra de um nó cheio ao redor de seu elemento mediano (vide figura a seguir).

Para fazer essa quebra, é utilizada uma função como esta:

struct celula_B*
quebra_celula (struct celula_B* r, struct celula_B* f, int i )
// recebe um apontador f para o elemento a quebrar e um apontador r para seu pai, e
// devolve um apontador u para  a segunda "metade" após a quebra ("metade" que acaba de ser criada)
{
  struct celula_B* u;
  u = (struct celula_B*) malloc (sizeof (struct celula_B));
  u->folha = f-> folha;  // TRUE se f é folha
  u->nchaves = f->nchaves = ORDEM-1;    // As duas partes terão no máximo a metade de sua capacidade utilizada

  for (j = 0; j < ORDEM; j++)
    u->filho[j] = f->filho[ORDEM+j];    // copia a "segunda metade" dos elementos 
                                        // de f para a "primeira metade" dos 
                                        // elementos de u

  for ( j = r->nchaves+1; j > i; j--)
    r->chave[j] = r->chave[j-1];        // Abre espaço em r para o novo elemento
  r->chave[i] = f->chave[ORDEM-1];      // O elemento "do meio" de f  "sobe"
                                        // para a vaga criada na célula r
  r->nchaves++;
 
 for (j = r->nchaves+1; j > i + 1; j--)
    r->filho[j] = r->filho[j-1];        // Acerta todos os ponteiros para os filhos de r

  r->filho[i + 1] = u;
  return u;
}