Árvores B (B-Tree)

• Assunto: Árvores B (B-Trees) - algoritmos e implementações em C e Java.

Start presentation

1 - O que é B-Tree (Árvore-B)

• O criador das árvores B: Rudolf Bayer e Ed McCreight;
• Acredita-se que a letra 'B' vem de balanceamento
• Balanceamento = todos os nós folha da árvore estão em um mesmo nível.
• Pode ser também:
  • B = sobrenome Bayer; ou
  • B = Boeing (Boeing Scientific Research Labs)

2 - Árvore-B versus Árvores Binárias

• Árvore binária precisa ser rebalanceada;
• Árvore-B não precisa ser rebalanceada;
• O balanceamento da árvore é necessário para diminuir a altura da árvore e portanto, diminuir o número de acessos do pior caso;
• binary tree:
  

• B-tree:
  

3 - Utilizações de B-Tree

• B-Tree são bastante utilizadas em:
  • Sistemas de arquivos
  • Bancos de dados

4 - Características de uma B-Tree

• B-tree [1]:
  

• Cada nó é formado por uma sequência de chaves e um conjunto de ponteiros;
• Uma chave possui dois ponteiros associados, um que pode apontar para uma sub-árvore à esquerda (com chaves filhas menores ou iguais) e outra que pode apontar para uma sub-árvore à direita (com chaves filhas maiores);
• O número de ponteiros em um nó excede o número de chaves em 1;
• O número máximo de ponteiros em um nós é a ordem da árvore; porém, existe controvérsias, alguns definem que o número de elementos será 2^ordem. Ou seja, para ordem=2, teremos 4 elementos; para ordem=3, teremos 8 elementos, etc.
• Um nó folha não possui filhos (seus ponteiros são nulos);
• Todos nós internos (exceto o nó raiz) tem pelo menos ceil(m/2) filhos não-vazios;
• Exemplo: uma B-Tree de ordem 6 possui no máximo 5 chaves e 6 filhos;

5 - Exemplo de implementação de nó

Este é um exemplo de implementação de nó:

typedef struct
{
   int contador_chaves;  // contador de chaves
   TipoItem chave[3];    // array para armazenar as 3 chaves
   long subarvore[4];    // array para armazenar os ponteiros
} TipoNo;

Este exemplo possui:

• ordem: 4
• chaves: 3
• tipo do item: TipoItem
• tipo do nó: TipoNo

6 - Algoritmo de inserção B-Tree

1. Pesquisando na árvore, encontrar o nó-folha onde o novo elemento deverá ser inserido;
2. Se o nó-folha contém menos que o número máximo de elementos, há espaço para mais um. Insira o novo elemento no nó, mantendo a os elementos ordenados;
3. Senão o nó folha é dividido (split) em dois nós:
   1. Um mediano é escolhido entre os elementos folha e o novo elemento;
   2. Valores menores que o mediano são inseridos no novo nó-esquerdo e valores maiores que o mediano são inseridos no novo nó-direito, com o mediano agindo como um valor separador;
   3. O valor separador é adicionado ao nó do pai, o qual pode causar uma nova divisão e assim por diante.

7 - Exemplo de inserção B-Tree

Usaremos o simulador: http://slady.net/java/bt/

• 1) Iremos inserir a seguinte sequência:

3  14 7  1  8  5  11 17 13 16 23 12 20 26 4  16 18 24 25 19

• 2) Configurar ordem como 2 (existem controvérsias na definição do que é ordem). Definimos anteriormente como ordem
• 3) Inserir os 4 primeiros números: 3 14 7 1.
  • note que não houve necessidade de divisão (split);
• 4) Inserir o valor 8:
  • note que não há mais espaço no nó, é necessário determinar o mediano (7) e realizar a divisão do nó;
• 5) Inserir os valores 5, 11 e 17:
  • note que não houve necessidade de divisão;
• 6) Inserir 13:
  • Note que há necessidade de divisão e perceba que a chave mediana é movida para o nó pai;
• 7) Inserir 6, 23, 12 e 20:
  • note que não houve necessidade de divisão (split);
• 8) Inserir 26:
  • note que o nó-folha mais à direita foi dividido (split).
• 9) Inserir 4:
  • note que o nó-folha mais à esquerda foi dividido (split) e o valor mediano é movido para o nó pai;
• 10) Inserir os valores 16, 18, 24 e 25:
  • note que não houve necessidade de divisão;
• 11) Finalmente, insira o 19:
  • note que os nós 14, 16, 17 e 18 se dividem, enviando o mediano 17 para o nó-pai. No entanto, o nó pai está cheio, portanto ele se divide, enviando o mediano 13 para formar um novo nó raiz.

8 - Para próxima aula: implementação em laboratório

• Será mostrado e explicado a implementação de BTree;
• Entregar em duplas via fórum do moodle a implementação de BTree em C e Java funcionando;
• Fórum: onde é utilizado B-Tree? Postar algum link onde cita a utilização prática de b-tree (banco de dados, sistemas operacionais, etc.);

9 - Projeto

• Criar grupos de 4 participantes para implementar, explicar e pesquisar uso das variações de B-Tree:
  • B*Tree
  • B+Tree

10 - Referências

1. CARLSON, David. Software Design Using C++. Acessado em 01 agosto de 07, disponível em http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

Cadastro de referências

• Set TITLE = B-Tree