Árvores B - Resumo

Prévia do material em texto

INTRODUÇÃO 
 
Árvores B são árvores de pesquisa balanceadas projetadas para funcionar bem em 
dispositivos de armazenamento secundário. São semelhantes às árvores rubro-negras, mas 
com melhor desempenho com operações de entrada e saída de disco. 
Uma das principais diferenças entre as árvores rubro-negras e as árvores B é o fato 
desta poder ter N filhos. O fator ramificação da árvore B pode ser grande, mas geralmente é 
determinado pelo tamanho do disco. 
Se x um nó interno de uma árvore com n[x] chaves, então x tem n[x] + 1 filhos. As 
chaves no nó separam o intervalos de chaves. 
 
ESTRUTURA DE DADOS NO ESPAÇO DE ARMAZENAMENTO SECUNDÁRIO 
 
A quantidade de dados manipulados por uma árvore B é muito grande, por esse 
motivo é utilizada a memória secundária. Os algoritmos de árvores B precisam de um 
número constante de páginas na memória principal. 
Em um algoritmo de árvore B, se um objeto já está nem disco, é o mesmo é lido com 
a operação DISK-READ e é inserido na memória principal, e então será feita referência ao 
mesmo por meio de ponteiro. Se não, é utilizada a operação DISK-READ para armazená-lo 
com a operação DISK-WRITE. 
As operações devem ser eficientes, gravando e lendo o máximo de informações 
possível. 
Um grande fator de ramificação reduz a altura da árvore e o número de acesos ao 
disco para encontrar as chaves. 
 
DEFINIÇÕES DE ÁRVORE B 
 
Um árvore BT é enraizada com as seguintes propriedades: 
 
1- Todos os nós tem os campos: 
a-) n[x], o número de chaves atualmente armazenadas no nó x. 
b-) as próprias n[x] chaves, armazenadas em ordem não decrescente 
c-) folha[x], um valor bool que é true se x é folha, e false se x for nó interno 
 
2- Cada nó interno x também contém n[x]-1 ponteiros para os filhos. Os nós folhas não tem 
filhos, e assim seus campos c são indefinidos. 
 
3- As chaves chave[x] separam os intervalos de chaves armazenadas em cada subárvore 
 
4- Toda folha tem a mesma profundidade, que é a altura h de uma árvore 
 
5- Existem limites superiores e inferiores sobre o número de chaves que um nó pode conter. 
Esses limites podem ser expressos em termos de um inteiro fixo t>=2 chamado grau 
mínimo da árvore B: 
a-) Todo nó diferente da raiz deve ter pelo menos t-1 chaves. Desse modo, todo nó 
interno diferente da raiz tem pelo menos t filhos. Se a árvore é não vazia, a raiz deve ter 
pelo menos uma chave. 
b-) Todo nó pode conter no máximo 2t-1 chaves. Então um nó interno pode ter no 
máximo 2t filhos. Dizemos que um nó é completo se ele tem 2t-1 chaves 
 
OPERAÇÕES BÁSICAS SOBRE ÁRVORES B 
 
A raiz da árvore B está sempre na memória principal, portanto, DIRK-READ na raiz nunca é 
exigida, mas DISK-WRITE sim. 
Todo nó repassado como parâmetro já tiveram DISK-READ executados sobre eles. 
 
PESQUISA EM UMA ÁRVORE B 
 
A decisão de ramificação é de várias vias, de acordo com o número de filhos do nó. 
B-TREE-SEARCH começa pela raiz de uma subárvore e a chave a ser pesquisada. Se a 
chave for encontrada, retorna-se o nó e o índice que ele se encontra, caso co.trário é 
retornado NULL. Assim que a operação localiza a chave é executa a operação DISK-READ. 
 
COMO CRIAR UMA ÁRVORE B VAZIA 
 
A operação B-TREE-CRAT cria um nó de raiz vazio, e então a operação 
B-TREE-INSERT adiciona as chaves. O procedimento ALLOCATE-NODE aloca o espaço 
em disco a ser utilizado. O nó criado por esta operação não tem informação armazenada, 
portanto não exige a operação DISK-READ. 
 
A INSERÇÃO EM UMA ÁRVORE B 
 
As chaves são inseridas em um nó folha incompleto. O nó folha é dividido ao redor 
de sua chave mediana, que se desloca para o pai identificando o ponto de divisão entre as 
duas árvores novas. Se o pai também estiver completo, ele deve ser dividido, propagando a 
árvore para cima. 
Sempre que é feita uma inserção, todo nó completo encontrado na busca é dividido. 
 
A DIVISÃO DE UM NÓ EM UMA ÁRVORE B 
 
A operação B-TREE-SPLIT-CHILD tem como entrada um nó não completo, um 
índice e seu nó filho completo. Essa operação divide esse filho em dois, que funciona pelo 
método recortar e colar. O nó da direita fica com os maiores filhos, e os nós da esquerda 
com os menores. 
 
INSERÇÃO DE UMA CHAVE EM UMA ÁRVORE B EM UMA ÚNICA PASSAGEM PELA 
ÁRVORE 
 
A operação B-TREE-INSERT utiliza B-TREE-SPLIT-CHILD para garantir que a 
recursão nunca descerá até um nó completo. O procedimento termina chamando 
B-TREE-INSERT-NONFULL para executar a inserção da chave. Esta operação recursiva 
desce a árvore conforme necessário, garantindo que o nó percorrido não está completo, 
chamando a operação B-TREE-SPLIT-CHILD sempre que necessário. 
 
ELIMINAÇÃO DE UMA CHAVE DE UMA ÁRVORE B 
 
A chave pode ser eliminada de qualquer nó, e não apenas da folha, e exige que os 
filhos sejam reorganizados. Deve-se assegurar que um nó não fique pequeno demais com a 
remoção. Sempre que uma chave for eliminada, o nó deve apresentar o número mínimo de 
chaves. 
Quando a operação B-TREE-DELETE for chamada, se for necessário, a chave 
deve se mover até um nó filho antes de ser executada. 
 
Passos para remoção de chave: 
1- Se a chave está num nó folha, eliminar chave 
 
2- Se a chave está num nó interno: 
a-) Se o filho da direita do nó tem a quantidade mínima de chaves, encontrar o 
predecessor da chave a ser eliminada. Eliminar chave e substituir pelo predecessor. 
b-) Se o filho da esquerda do nó tem a quantidade mínima de chaves, encontrar o 
sucessor da chave a ser eliminada. Eliminar chave e substituir pelo sucessor. 
c-) Se nenhum filho tem chaves o suficiente, subir todos os filhos e eliminar a chave. 
 
3- Se a chave não estiver no nó interno, executar uma das operações abaixo, e eliminar a 
chave: 
a-) Se o filho não tiver chaves o suficiente, mas os irmãos sim, mover chave do pai 
para o filho; mover chave de um dos irmãos para o pai; e mover chave apropriada entre os 
filhos. 
b-) Se o filho e nenhum irmão tiver chave, fazer intercalação entre os irmãos e 
mover chave do pai pro filho a fim de se tornar a nova chave mediana. 
 
A maioria das chaves está nas folhas. A operação B-TREE-DELETE não tem 
necessidade de subir pela árvore, apenas descer, mas pode ser necessário voltar a subir 
para reorganizar a árvore.