Operações de Inserção e
Remoção – BTree
Resumo
Profa. Sandra de Amo
BCC - UFU
Inserção de Registros nas Folhas

Caso a ocupação não fique acima da máxima :
insere, não altera nada nos niveis superiores

Caso a ocupação fique acima da máxima



Tenta distribuição com vizinho à direita.
Caso não der: tenta distribuição com vizinho à esquerda
Caso não der: Divide folha com nó inserido, produzindo
dois nós N1 e N2.

N2 precisa de um ponteiro vindo do nó acima !
Inserção: distribuição nas folhas





Não há aumento no número de folhas
Não há aumento de ponteiros vindo do nivel
superior
Não há aumento de registros no nó pai
Não há modificações propagadas para os níveis
superiores ao nível do nó pai.
Só há modificação de registro R no nó pai:

R = registro do lado esquerdo do ponteiro apontando
para a folha da direita.
Inserção: Divisão de 1 folha em 2 folhas
F1 e F2



Número de folhas cresce de um.
Número de ponteiros saindo do nó pai cresce de um.
Número de registros no nó pai deve crescer de um.
Caso nó pai não tenha ocupação máxima antes da
alteração:
 Primeiro registro de F2 sobe para nó pai em posição
adequada.
 Ponteiro à esquerda do novo nó deve apontar para F1
 Ponteiro à direita do novo nó deve apontar para F2
Inserção: Divisão de 1 folha em 2 folhas
F1 e F2
Caso nó pai tenha ocupação máxima antes da
alteração:



Subida de registro para o nó pai causa overflow no nó.
Nó pai fica com 2d+1 elementos após “subida”
Solução simples
 Divide nó pai em dois nós N1 e N2 com d elementos cada
(ocupação mínima)
 Elemento do meio M sobe para nó pai do pai.
 Ponteiros do nó pai para seus filhos não são alterados !
 Ponteiros à esquerda e à direita de M apontam para N1 e N2
respectivamente
Remoção de Registros nas Folhas

Caso a ocupação não fique abaixo da mínima :
remove, não altera nada nos niveis superiores

Caso a ocupação fique abaixo da minima
 Tenta distribuição com vizinho à direita.
 Caso não der: tenta distribuição com vizinho à
esquerda
 Caso não der: Junta folha com nó removido com à
direita ou, se não der, com a esquerda.
Remoção: distribuição nas folhas





Não há diminuição no número de folhas
Não há diminuição de ponteiros vindo do nivel
superior
Não há diminuição de registros no nó pai
Não há modificações propagadas para os níveis
superiores ao nível do nó pai.
Só há modificação de registro R no nó pai:

R = registro do lado esquerdo do ponteiro apontando
para a folha da direita envolvida na distribuição
Remoção: Junção de 2 folhas



Número de folhas decresce de um.
Número de ponteiros decresce de um.
Número de registros no nó pai decresce de um.

Caso nó pai não fique abaixo da ocupação minima


Remove-se registro R à esquerda do ponteiro apontando para o nó
do nível inferior, à direita.
Caso nó pai fique abaixo da ocupação minima


Tenta JUNTAR com nó irmão, à direita ou à esquerda.
Caso não der para juntar (pois o resultado teria ocupação maior do
que a máxima), DISTRIBUI com um dos nós irmãos (tente primeiro o
da direita, se não der, tente o da esquerda).
Remoção: Junção de nós N1 e N2 em
um nível intermediário I

Há diminuição de nós no nível I.



Há diminuição de ponteiros vindo do nível I-1 (pois houve diminuição de
nós no nível I).


Porém o número K de ponteiros saindo do nível I deve continuar o mesmo que
antes da junção, pois o nível abaixo (I+1) necessita de K ponteiros !
Logo, é necessário que apareça um novo registro no nível I. (1)
Logo, há diminuição de registros no nível I-1. (2)
De (1) e (2) conclui-se que




um registro do nível I-1 deve descer para o nível I
Qual é este nó que desce ?
Registro R à esquerda do ponteiro apontando para o nó N2 (da direita) DESCE para o
novo nó juntado N1+N2.
Este ponteiro da esquerda é eliminado do nível I-1
Modificação se propaga recursivamente para o
nível I-1, já que houve diminuição de nós neste nível
Remoção: Distribuição de elementos entre
nós N1 e N2 em um nível intermediário I

Não há diminuição de nós no nível I.

Não há diminuição de ponteiros vindo do nível I-1.

Não há diminuição de registros no nível I-1
Entretanto, as coisas não são tão simples
assim...
Supondo que o último registro do nó N1 virou primeiro registro do nó N2
Nível I - 1
22
< 22
≥ 22
???
Nó N1
5
135
17
13
20
17
O ponteiro vermelho não
pode ser1eliminado.
nó para
≥ 17
Logo, o preto
será
2 ponteiros ??
< 20
eliminado.
20 ≤
O registro 17 deve sumir do nó N1!
Nó N2
Nível I
30
1 ponteiro para
2 nós ??
Nível I+1
≥30
chave < 22
22 ≤ chave < 30
É preciso mais um registro entre o
20 e o 30 para ganhar um ponteiro !
Ajuste final
22
< 17
5
135
≥ 13
< 17
≥ 17
17
13
17
≥ 17
< 20
20
20 ≤ chave < 22
305
13
22 ≤ chave < 30
17
≥30
Exercicio para entregar

Você acha que o ajuste final poderia ser feito “subindo” o 20 e
descendo o 22 ao invés de “subir” o 17 e descer o 22 ? Explique
sua resposta !
20
5
135
13
17
17
?
22
?
305
?
Sugestão: para onde apontariam os ponteiros
à direita de 17 e à esquerda de 22 ?
E o ponteiro à direita do 22 ? Reveja slides 11, 12 e 13
13
17
Exercicio: Remove 34*
5
2* 3*
5* 7* 8*
135
14*16*
21
50
18
13
20
17
18* 19*
27
20* 21*
22* 24*
30
27*29*
33* 34*