B-Trees

Lembram-se das árvores 2,3,4? Já falei delas aqui antes (aqui). Essas árvores tem a capacidade de acumular uma, duas ou três chaves num único nó. Os nome “2,3,4” refere-se à quantidade de links para os nós filhos de cada nó…

Bem… as B-Trees são parecidas. A diferença está na possibilidade de usarmos n chaves em cada nó, onde n é um valor ímpar maior ou igual a 3. Quero dizer, que nós podem ter duas ou mais chaves, mas o limite superior da quantidade deve ser 3 ou mais… Não há limites matemáticos para a quantidade de chaves num nó. Podemos ter nós com 1001 chaves, por exemplo… Na prática, a quantidade de nós é limitada para que não tenhamos que manter listas ordenadas muito grandes. Usarei exemplos com 5 chaves por nó neste texto.

Características das B-Trees e a inserção de chaves:

Cada chave num único nó deve ser arranjada de maneira que a lista esteja em ordem (usarei a ordem crescente aqui, para facilitar o entendimento). Isso quer dizer que:

K_1\leqslant K_2\leqslant\dots\leqslant K_{n-1}\leqslant K_{n}

Enquanto inserimos novas chaves no nó raiz, elas vão sendo colocadas na lista de forma ordenada até a lista ficar cheia (com 5 chaves), a próxima chave inserida, K_6 faz com que o nó sofra uma “divisão” (split). Num split retiramos a chave central e fazemos com que ela “suba” para o nó pai… Quando só temos o nó raiz, essa chave selecionada torna-se o novo nó raiz com dois nós filhos com duas chaves cada:

01-split

Só depois do split a chave K_6 é inserido no nó folha… Todas as inserções sempre são feitas em nós folhas:

02-insert

Outra características menos óbvia é que os nós intermediários e folhas sempre terão \left\lfloor\frac{n}{2}\right\rfloor chaves, no mínimo. Isso fica evidente quando pensamos no processo de split… Apenas nós cheios sofrem split e retirando a chave central (que “sobe”), sobram a quantidade de chaves citada acima para cada lado… A única exceção é o nó raiz, que pode ter apenas uma chave!

Vejamos agora o que acontece se tivermos um nó folha cheio e queremos inserir um item K_9:

03-insert-new-on-full-leaf

Ao percorrer a árvore, determinamos que a chave K_9 deve ser inserida no nó folha mais a direita, que está cheio. Por isso, este nó deve sofrer um split, fazendo com que a chave K_6 “suba” para o nó pai (raiz), dividindo o nó folha em dois e liberando espaço para a inserção de K_9, como mostrado acima.

A regra aqui é: Se formos inserir um item, a cada vez que encontrarmos um nó cheio ao “caminhar” pela árvore (de acordo com o critério da chave), devemos fazer um split. Se ambos o nó raiz e o nó folha estivessem cheios, deveríamos fazer o split do nó raiz e, ao pularmos para o nó folha, fazer o split dele também, subindo a chave central para o nó intermediário… Vejamos como isso funciona neste exemplo mais complexo, ao tentarmos inserir K_9:

04-insert-raiz-e-folha-cheios

Assim, a inserção sempre segue duas regras simples:

  1. Ao “caminhar” pela árvore, ao encontrar um nó cheio, faça um split;
  2. Ao encontrar o nó folha correspondente, insira a chave lá.

Outra característica que não é evidente (embora você possa percebê-la dando uma olhada nos exemplos acima) é que todos os nós folha sempre estarão no mesmo nível. Ou seja, uma B-Tree é “auto balanceada”.

Apagar chaves sempre é mais complicado, né?

Inserir chaves é moleza. As duas regras simples, acima, garantem que a inserção sempre será feita apenas nos nós folha. Não temos esse luxo no caso de apagamento de chaves. Quer dizer, qualquer chave deve poder ser apagada, certo?

O algoritmo de deleção é dividido em duas possibilidades: Uma para chaves contidas em nós folhas e outra para chaves contidas em nós intermediários ou raiz. Ainda assim, cada uma dessas possibilidades tem 5 regras simples.

  1. Se o nó onde a chave se encontra for folha e este nó tiver mais que \left\lfloor\frac{n}{2}\right\rfloor itens (ou seja: n_{itens}>\left\lfloor\frac{n}{2}\right\rfloor), então basta apagar a chave da lista. No exemplo com nós de 5 chaves, se o nó folha tiver 3 chaves ou mais essa regra se aplica, caso contrário, teremos que lidar com a segunda possibilidade;
  2. Se o nó for folha e tiver \left\lfloor\frac{n}{2}\right\rfloor itens, uma das sub regras abaixo se aplica (lembre-se: exceto pelo nó raiz, nenhum outro nó pode ter menos que \left\lfloor\frac{n}{2}\right\rfloor chaves!):
    • Se um dos nós folha irmãos do nó contendo a chave a ser apagada tiver mais que \left\lfloor\frac{n}{2}\right\rfloor itens, apaga-se a chave desejada e realiza-se uma rotação de chaves, onde a chave do nó pai “desce” para o nó folha e uma chave do nó irmão “sobe” para o nó pai. Eis um exemplo ao apagarmos a chave K_6 da árvore abaixo:
      delete2a
      Note que, neste exemplo, tanto faz se escolhermos o nó irmão da direita ou esquerda. O que vai mudar é o sentido da rotação. No caso da árvore resultante, se quiséssemos apagar a chave K_7, por exemplo, teríamos que realizar uma rotação o sentido horário à partir do nó irmão do lado direito (K_3) e a chave K_4 do nó pai;
    • Se os nós folha irmãos do nó contendo a chave a ser apagada tiverem \left\lfloor\frac{n}{2}\right\rfloor itens, então a chave deve ser apagada do nó folha atual e ele deve ser “juntado” com um nó irmão e a chave do nó pai que os divide “desce”, formando um nó cheio. Isso criará um nó “semi-cheio” e diminuirá o nó pai em um item. Eis um exemplo, apagando a chave K_5:delete2b
      De novo, tanto faz usarmos o nó irmão da direita ou da esquerda.A diminuição do nó pai pode ser problemática se ele não for o nó raiz e tiver \left\lfloor\frac{n}{2}\right\rfloor itens. Este caso é discutido abaixo…;
  3. Se o nó não for folha, mas for um nó interno (entre um nó folha e o nó raiz):
    • Se o um dos nós filhos da chave em questão tiver mais que \left\lfloor\frac{n}{2}\right\rfloor, basta apagar a chave desejada, substituíndo-a por uma das chaves de um extremo de um nó filho. Por exemplo, apagando K_6 da subárvore abaixo:
      delee3a
    • Se os nós filhos tiverem \left\lfloor\frac{n}{2}\right\rfloor itens, basta juntá-los e deletar a chave no nó pai (exemplo, deletando K_8):
      delete3b
      Este é o mesmo segundo sub caso do caso 2, lá em cima.

Neste ponto vale a pena especificar o que seria “juntar” dois nós filhos com \left\lfloor\frac{n}{2}\right\rfloor itens… Trata-se do inverso de um split (chamarei de unsplit)… A chave do nó pai é apagada deste nó, trazida para o centro do nó filho “juntado” e, recursivamente, deletada do novo nó filho… Dessa forma ela pode propagar-se até um nó folha, onde será apagada de acordo com as regras propostas acima. Essa “propagação” não é importante, já que apenas ocorrerá n-1 vezes, onde n é o número de níveis da árvore.

Determinando o tamanho máximo de uma B-Tree:

Como cada nó tem tamanho máximo, podemos calcular, no caso extremo, onde temos todos os nós completamente preenchidos, o tamanho máximo da árvore:

\displaystyle n=1+\left(\sum_{x=1}^k K^x\right)

Onde k é o número máximo de níveis, excluindo o nó raiz (nível 0) e K é o número de chaves por nó. Uma árvore com nós de 5 chaves e 4 níveis tem 781 nós, uma de 5 níveis terá 3901, no máximo. A equação acima poderia ser simplificada para n=\sum_{x=0}^k K^x, mas preferi deixar o “1 +” evidente para explicitar a existência incondicional do nó raiz.

Considere agora como um nó estaria codificado na memória: Em primeiro lugar, precisamos manter registro de quantas chaves existem no nó. Depois, precisamos manter as chaves e os links. Ajuda também manter um “bit” extra, indicando se o nó é folha o não (esse bit pode ser codificado junto com o byte contendo a quantidade de chaves). Por exemplo:

#define MAX_KEYS 5
#define MIN_KEYS ((int)MAX_KEYS / 2)

struct node_s {
  uint8_t type:2;  // 0=root, 1=intermediário, 2=folha
  uint8_t num_keys:6;
  key_t keys[MAX_KEYS];
  struct node_s *children[MAX_KEYS+1];
};

A estrutura acima permite que tenhamos um máximo de 64 chaves num único nó (se num_keys começar a contagem de 1). O tamanho do nó depende do tipo da chave e do número delas. Vamos supor que nossas chaves sejam do tipo uint32_t. A estrutura node_s terá 69 bytes, para as 5 chaves por nó. Parece demasiado, mas considere uma árvore AVL, por exemplo… Cada nó dessa árvore tem dois bits com o valor do balanceamento, a chave e dois nós. Ou seja, nas mesmas condições, 21 bytes. Mas, para guardamos 5 chaves precisaríamos de 5 nós ou 105 bytes… No caso extremo, com 64 chaves por nó, a B-Tree teria nós com 777 bytes. Uma árvore AVL com a mesma quantidade de nós consumiria 1344 bytes… A B-Tree é mais econômica!

Revisando as vantagens das B-Trees sobre as árvores AVL e Red-Black

Vimos que as B-Trees tendem a ser mais econômicas… Outra vantagem é que a rotina de inserção é mais rápida, eventualmente exigindo splits de alguns nós. A rotina de deleção, embora pareça mais complicada, geralmente é tão veloz quanto as das suas irmãs…

No caso das árvores red-black, algumas vezes elas ficam “capengas” ou “desbalanceadas”. As B-Trees não ficam e ainda têm a vantagem de que todos os nós folha sempre ficam no mesmo nível.

Outra vantagem é a alocação de nós… No caso das B-Trees, uma razoável quantidade de chaves é alocada de uma tacada só… Mas, é claro, a taxa de aproveitamento desses nós inicia-se em pouco menos de 50% da alocação. Considerando a economia que as B-Trees nos dão, mesmo assim, é um bom negócio.

Uma coisa que pode ser vista como desvantagem é a necessidade de manter as chaves num nó em ordem. Ao invés de lidarmos apenas com os algoritmos de inserção e deleção, teremos que lidar com ordenação linear também. Considerando que um nó tem tamanho limitado de chaves, esses algoritmos são bem simples e, mesmo que nós grandes fossem usados, alguma variação de qsort poderia ser usado… Da mesma forma, uma vez que as chaves são ordenadas, para encontrar uma chave dentro de um nó, podemos usar algoritmos como binary search, o que acelera bastante a busca.

Mesmo que a pesquisa por nó seja linear, a quantidade de níveis de uma B-Tree é menor que a de uma árvore AVL equivalente, tendendo a torná-la mais rápida.

Num outro artigo mostrarei formas de otimizar as B-Trees. Existem variações desse tipo de árvore de multinível, como as B+Trees e B*Trees.

Anúncios