Instituto de Ciências Matemáticas e de Computação
Departamento de Computação e Estatística
SCE183 - Algoritmos e Estruturas de Dados 2
Profs. Resp: Graça Pimentel e Maria Cristina
B-Trees & Cia (IV)

1. Definição e Propriedade de B-trees

Ordem
A definição atual de B-Tree vincula a ordem de uma árvore B ao número de descententes de um nó (isto é,. de ponteiros). Deste modo, numa árvore B de ordem m o número máximo de chaves é m-1.
Exemplo:
Uma árvore B de ordem 8 tem um máximo de 7 chaves por página.

Número mínimo de chaves por página
Quando uma página é dividida na inserção, os nós são divididos igualmente entre as páginas velha e nova. Deste modo, o número mínimo de chaves em um nó é dado por m/2 - 1 (exceto para a raiz).

Exemplo: Uma árvore B de ordem 8 que tem um máximo de 7 chaves por página tem um mínimo de 3 chaves por página.

Nó folha
Os nós folhas são aqueles alocados no nível mais baixo da árvore.

2. Definição formal das Propriedades de B-trees

Para uma B-tree de ordem m:

1. cada página tem um máximo de m descententes
2. cada página, exceto a raiz e as folhas, tem um mínimo de m/2 descendentes
3. a raiz tem um mínimo de dois descendentes - a menos que seja uma folha
4. todas as folhas aparecem num mesmo nível
5. uma página que não é folha e possui k descendentes contém k-1 chaves
6. uma página folha contém no mínimo m/2 -1 e no máximo m-1 chaves

3. Profundidade de Busca no Pior Caso

É importante entender o relacionamento entre o tamanho de página, o número de chaves armazenados em uma página, e o número de níveis que uma B-tree pode ter.

Exemplo: "Você precisa armazenar 1.000.000 chaves e considera utilizar B-tree de ordem 512. Qual o número máximo de acessos para localizar uma chave ? "

Ou seja: quão profunda pode ser a árvore ?
O pior caso ocorre quando cada página tem apenas o número mínimo de descendentes, e possuem, portanto, altura máxima e largura mínima.
Em geral, para um nível d qualquer de um B-tree, o número mínimo de descendentes é dado por (2 * m/2 ) ^ (d-1).

Para uma árvore de N chaves, a sua profundidade no nível das páginas folhas, é dado por d onde:

d <= 1 + log(base 256)m/2((N+1)/2)

Então para a B-tree de ordem 512 com 1.000.000 de chaves

d <= 1 + log256(500.000,5) <= 3.37 Essa é a performance que procuramos !

4) Eliminação, Redistribuição e Concatenação

O processo de divisão (split) de páginas garante a manutenção das propriedades da B-tree durante a inserção. Essas propriedades precisam ser mantidas, também, durante a eliminação de chaves. Caso 1: eliminação mantém número mínimo de chaves na página.
Solução: Chave é retirada e registros internos à página reorganizados.

Caso 2: eliminação de chave que não está numa folha.
Solução: Sempre eliminamos da folha. Se uma chave deve ser eliminada de uma página que não é folha, trocamos a chave com sua sucessora imediata, a qual, com certeza está numa folha, e então eliminamos a chave da folha.

Caso 3: eliminação causa underflow na página.
O número mínimo de chaves por página nessa árvore é m/2 -1 = 6/2 -1=2.
Solução: Redistribuição. Procura-se uma página irmã (mesmo pai) que contenha mais chaves que o mínimo: se existir redistribui-se as chaves entre essas páginas. A redistribuição causa a colocação de uma nova chave de separação no nó pai.

Caso 4: ocorre underflow e a redistribuição não pode ser aplicada.
Quando não existirem chaves suficientes para dividir entre as duas páginas irmãs.
Solução: Deve-se utilizar concatenação: combina-se o conteúdo das duas páginas e a chave da página pai para formar uma única página. Concatenação é o inverso do Splitting. Como consequência, pode causar o underflow da página pai.

Caso 5: underflow da página pai
Solução: No exemplo, a concatenação das páginas 3 e 4 retira D a página 1, causando underflow na página 1. Redistribuição não pode ser aplicada (por quê?). Deve-se utilizar concatenação novamente.

Caso 6: Diminuição da altura da árvore.
Consequência da concatenação dos filhos do nó.
Solução: A concatenação das páginas 1 e 2 absorve a única chave da raiz.

Este caso mostra o que ocorre quando a concatenação é propagada até a raiz. Note que esse nem sempre é o caso: se a página 2 (Q e W) tivesse mais uma chave, aplicaria-se redistribuição em vez de concatenação.

Eliminação de chave em árvore B

1. Se a chave não estiver numa folha, troque-a com seu sucessor imediato.
2. Elimine a chave da folha.
3. Se a folha continuar com o número mínimo de chaves, fim.
4. A folha tem uma chave a menos que o mínimo. Verifique as páginas irmãs da esquerda e direita:

4.1.se uma delas tiver mais que o número mínimo de chaves, aplique redistribuição.
4.2.senão concatene a página com uma das irmãs e a chave pai.
5. Se ocorreu concatenação, aplique passos de 3 a 6 para a página pai.
6. Se a última chave da raiz for removida, a altura da árvore diminui.

5) Redistribuição durante Inserção

Diferentemente da divisão e da concatenação, o efeito da redistribuiço é local. Não existe propagação.
Outra diferença: não existe regra fixa para o rearranjo das chaves e a eliminação de uma chave pode causar o underflow de apenas uma chave na página, e a redistribuição pode mover apenas uma chave para página com problema.

Exemplo: dada uma B-tree de ordem 101, o número mínimo e máximo de chaves é, respectivamente, 50 e 100. Se ocorre o underflow numa página, e a página irmã tem 100 chaves, qualquer número de chaves entre 1 e 50 pode ser transferido.
Normalmente transfere-se 25, e deixa-se as páginas equilibradas.

Redistribuição é uma idéia nova, a qual não foi explorada no algoritmo de inserção. E é uma opção desejável. Em vez de dividir uma página cheia em duas meia-páginas, pode-se optar por colocar a chave que sobra (ou mais que uma!) em outra página.
Essa estratégia deve resultar numa melhor utilização do espaço.

Redistribuição X Divisão
Depois da divisão de uma nó, cada página está 50% vazia. Portanto a utilização do espaco, no pior caso, em uma ávore B que utiliza splitting é de cerca de 50%. Em média, para árvores grandes, prova-se que o índice é de 69%.

Estudos empíricos indicam que a utilização de redistribuição pode elevar o índice de 67% para 85%. Esses resultados sugerem que qualquer aplicação séria de árvore B utilize, de fato, redistribuição durante a inserção.

Algoritmos de Pesquisa
B* Trees