Método de Acesso Dinâmico:
B-Tree - Busca e Inserção
Chaves de busca sem duplicatas
AULA 8
Profa. Sandra de Amo
GBC053 – BCC
2013-1
B-Trees : Método de Acesso
Dinâmico

Nós internos da árvore são alterados à medida que novos registros são
inseridos nas folhas, ou quando registros são deletados.

Quando tais nós são alterados ?

Operações de inserção e deleção são balanceadas de modo a que cada
nó interno tenha uma ocupação mínima e máxima.

Uma ocupação mínima de 50% é garantida em cada nó (exceto a raiz)

Arvore é Balanceada

Todos os caminhos da raiz até a folha têm o mesmo comprimento.

Cada nó (exceptuando a raiz) contém m entradas, onde
d ≤ m ≤ 2d, d = ordem da B-tree

A raiz contém m entradas onde 1 ≤ m ≤ 2d

Páginas das folhas são ligadas em sequência através de ponteiros – podem
ser percorridas em sequência nas duas direções.

Altura da árvore : Devido ao grande espalhamento da árvore, sua altura é
raramente maior do que 4
Formato de um nó interno
Pi = ponteiros que apontam para um núm. de página no nível imediatamente inferior
Ki = valor do atributo chave do índice.
Exemplo: se o atributo chave é idade então Ki é um valor de idade.
P0 K1 P1 K2 P2 K3
...
Pi
K < Ki+1
Valores K da chave nesta página
são < Ki+1
Ki+1 Pi+1 ...
Km Pm
K ≥ Ki+1
Valores K da chave nesta página
são ≥ Ki+1
Busca (entradas sem duplicatas)
Ordem = 2 : cada nó interno contém K entradas, 2 <= K <= 4
Chave de busca contém chave candidata (não há duplicatas)
13
5* 7*
24
30
15 ?
5?
2* 3*
17
14*16*
19* 20* 22*
24* 27* 29*
33* 34* 38*39*
Inserção
Se nó onde deve ocorrer a inserção não está cheio
Exemplo inserindo 23 *
13
2* 3*
5* 7*
14*16*
17
24
19* 20* 22* 23*
30
24* 27* 29*
33* 34* 38*39*
Inserção: se nó onde deveria ocorrer
a inserção já está cheio
 Variante 1 : Se nó está cheio divida e ajuste os nós
ancestrais.
 Variante 2 : Testa primeiro se pode redistrisbuir
num nó vizinho. Em caso negativo, divide.
 Ideal
 Nós intermediários: sempre dividir, não redistribuir
 Nós Folha: procure redistribuir entre os vizinhos



Se tiver espaço no vizinho direito, redistribua.
Caso contrário, verifica se tem espaço no
vizinho esquerdo, e redistribua
Caso contrário: divida a folha cheia.
Inserção : Testando vizinho à direita
Inserindo 6*
13
2* 3* 5* 7*
6*
CHEIA !!
14
* 16*
16*
14*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Inserção : Testando vizinho à direita
Inserindo 6*
13
2* 3* 5* 7*
2* 3* 5* 6* 7*
14*
14
* 16*
16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Inserção : Testando vizinho à direita
Inserindo 6*
13
7*
2* 3* 5* 6*
7*
2* 3* 5* 6* 7*
14* 16*
14* 16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Resumo:
Inserção da chave X na folha P
 P está cheia
 Vizinho à direita VD tem espaço e pai(VD) = pai(P)
 Insere X em P  Obtém página P’ com 2d+1 elementos
 Transfere último elemento Y de P’ para primeira posição de VD
 Seja Pai = pai(VD) = pai(P)
 Pti = ponteiro de Pai apontando para VD
 Ki = chave em Pai antes de
 Substitui Ki por Y
Pti
Exercicio
Inserir a chave 30*
13
2* 3* 5* 7*
14*
14
* 16*
16*
17
24
19* 20* 22*
32
24* 27* 28* 29*
33* 34* 38*
Inserção : Testando vizinho à esquerda
Inserindo 35*
8
2* 3* 5* 7*
814** 14*
16* 16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
33* 34* 35* 38* 39*
Inserção : Testando vizinho à esquerda
Inserindo 35*
8
2* 3* 5* 7*
814** 14*
16* 16*
17
24
19* 20* 22*
34
24* 27* 29* 33*
34* 35* 38*39*
Resumo:
Inserção da chave X na folha P
 P está cheia
 Vizinho à direita VD



Vizinho à esquerda VE tem espaço e pai(VE) = pai(P)
Insere X em P  Obtém página P’ com 2d+1 elementos
Transfere primeiro elemento Y de P’ para última posição de VE
Seja Pai = pai(P) = pai(VE)
Pti = ponteiro de Pai apontando para P
Ki = chave em Pai antes de Pti
Substitui Ki por Y







não tem espaço ou
não existe ou
pai(VD) ≠ pai(P)
Exercicio
Inserir a chave 25*
13
2* 3* 5* 7*
14*
14
* 16*
16*
17
24
19* 20* 22*
32
24* 27* 28* 29*
33* 34* 38*39*
Discussão
 Distribuição nas folhas vizinhas não acarreta
mudança aumento de ocupação dos nós pais
 Portanto: Nós pais não ultrapassam
ocupação máxima



Não precisam ser divididos nem redistribuídos
entre seus vizinhos
Não há crescimento da altura da árvore
Modificações não se propagam para nós
acima do nó-pai
Inserção : Vizinhos estão cheios
Divisão da Folha
Inserindo 8*
Cheia !
13
2*
7* 8*
3* 5* 7*
2* 3* 5* 7*
Cheia !
8*
17
13* 14* 15* 16*
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Divisão de nós intermediários
13
5
2*
3* 5* 7*
7* 8*
17
13* 14* 15* 16*
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Divisão de nó intermediário
17
13
5
2*
3* 5* 7*
7* 8*
24
14* 16*
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Resumo: Divisão de Folha
Inserção da chave X na folha P
 P está cheia
 Vizinho à direita VD não tem espaço ou não existe ou pai(VD) ≠
pai(P)
 Vizinho à esquerda VE não tem espaço ou não existe ou pai(VE)
≠ pai(P)
 Insere X em P  Obtém página P’ com 2d+1 elementos
 Divide página P em duas páginas P1 e P2
 P1 tem d elementos
 P2 tem d+1 elementos
 Pai = pai(P)
 Elimina ponteiro de Pai que aponta para P
 Y = primeiro elemento de P2
 Insere novo nó Y em Pai
 Insere dois novos ponteiros em Pai
à esquerda de Y apontando para P1
à direita de Y apontando para P2
Se Pai ultrapassar tamanho máximo : Divide(Pai)
Resumo: Divisão de nó intermediário
Divide(P), P = nó intermediário, P ≠ raiz
Tamanho(P) = 2d+1
 X = chave do meio de P
 Divide P em P1 e P2


P1 contém os d primeiros elementos de P
P2 contém os d últimos elementos de P
 Seja Pai = pai(P)
 Insere X em Pai
 Elimina ponteiro de Pai que apontava para P
 Insere dois novos ponteiros em Pai
à esquerda de X apontando para P1
à direita de X apontando para P2
Se Pai ultrapassar tamanho máximo : Divide(Pai)
Resumo: Divisão de Raiz
Divide(P), P = nó intermediário, P = raiz
Tamanho(P) = 2d+1
 X = chave do meio de P
 Divide P em P1 e P2


P1 contém os d primeiros elementos de P
P1 contém os d últimos elementos de P
 Cria novo nó raiz R com única chave X, em nível acima do nível dos
nós P1 e P1
 Insere dois ponteiros em R
à esquerda de X apontando para P1
à direita de X apontando para P2
Exercicio: Insira (49,*)
16
8
25
11
17* 19* 23* 24* 26* 28*
2* 5* 6*
12* 14* 15*
8* 9* 10*
34
45
35* 37* 38* 40* 46* 47* 48* 54*
55
56* 58* 60*65*