ACH2024 Aula17e18 Arvores B

Prévia do material em texto

1
ACH2024 
Aulas 17 e 18 
Árvores B
Profa. Ariane Machado Lima
2
Nas aulas passadas...
3
https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html
Memória virtual
4
O você acha que o computador deve fazer 
para ler algum dado do HD?
1) Identifica em que setor/trilha/superfície está 
a informação
2) Movimenta o braço de leitura para o cilindro 
correto (para poder acessa a trilha correta)
3) Rotaciona o prato para posicionar a cabeça 
de leitura sobre o setor correto
4) Faz a leitura de um certo nr de bytes 
Passos 2 e 3 (chamados SEEK) são 
mecânicos! Por isso demora tanto!
5
Arquivos de dados
 Bloco: unidade de transferência de dados 
entre memória principal e a memória 
secundária (~ tamanho de uma página)
 É comum considerar que em cada bloco pode 
haver vários registros
 Se R (tamanho fixo do registro) e B (tamanho 
do bloco) e R ≤ B:
fator de blocagem fb = floor(B/R)
6
Organização de arquivos
(como os registros são armazenados nos 
blocos)
 Tipos vistos na aula passada:
– Não ordenada (heap files)
– Ordenada (sorted files)
– Indexada 
 Organização tem impacto nas operações de 
inserção, deleção, modificação, busca, etc.
7
Organização não ordenada
 O arquivo, de r registros espalhados em b blocos, 
não está ordenado
 Inserção eficiente: O(1)
 Busca: O(b)
 Remoção: Precisa achar onde está o registro – O(b)
 Modificação de registro de tamanho variável: Pode 
exigir a remoção de outros registros a serem inseridos 
em outros blocos
 Leitura ordenada: MUITO INEFICIENTE 
Exige uma ordenação primeiro! (ordenação externa) 
8
Organização ordenada
 Os r registros estão ordenados pela chave 
 Leitura ordenada eficiente (sequencial) – O(b)
 O próximo registro pode estar no mesmo bloco
 Mínimo / Máximo estão no cabeçalho do arquivo – O(1)
 Busca: dá para usar busca binária (baseada nos blocos!) - 
O(lg b)
 Inserção/remoção: cara! - O(b) - tem que reorganizar os 
registros na ordem
 Modificação: cara! - O(b) – principalmente se for na chave
9
Organização indexada
 Blocos de dados: em cada bloco os registros são ordenados pela chave 
 Índice primário: blocos de índices ORDENADOS (pelo campo k) contendo 
registros de tamanho fixo com os campos <k,b>, sendo k a chave (primária) do 
primeiro registro (âncora) do bloco apontado por b 
O índice é ordenado 
pelo campo k
 Qual a vantagem?
 Índice tem bi blocos, sendo bi << b (cada entrada é 
menor que um registro, e há só uma entrada por bloco)
 → busca binária no índice é muito mais rápida!!! O(lg bi)
Blocos de dados
Blocos do índice
k
b
10
11
Organização indexada
 Problema: inserção / remoção
 Altera a posição em disco de vários registros
→ altera âncora de vários blocos
→ altera várias entradas do índice primário
 Formas de contornar o problema:
 Remoção por bits de validade
 Usar um arquivo desordenado de overflow (para as 
inserções, se necessário)
 Ou uma lista ligada de overflow (os registros do bloco e 
da lista podem ser ordenados para melhorar a busca)
12
Aula de hoje
 Dá para melhorar?
 O que dá para fazer se o arquivo é muito 
grande e o próprio índice ficou grande (com 
muitos blocos)? 
13
Aula de hoje
 Dá para melhorar?
 O que dá para fazer se o arquivo é muito 
grande e o próprio índice ficou grande (com 
muitos blocos)?
– ÍNDICE DO ÍNDICE!!! 
14
Organização indexada multiníveis
 Nível 1: arquivo de índices para os dados
 Nível 2: arquivo de índices para o arquivo de 
índices nível 1
 Se no nível 2 precisar de mais de um bloco, 
criar nível 3!
 ….
 
15
16
Organização indexada multiníveis
 Nível 1: arquivo de índices para os dados
 Nível 2: arquivo de índices para o arquivo de índices 
nível 1
 Se no nível 2 precisar de mais de um bloco, criar nível 3!
 ….
 Busca: binária em cada nível (rápida!) - O(t) - precisa 
acessar t blocos, sendo t o número de níveis
t = ceil(logfbi r1),
fbi = nr de registros que cabem em um bloco de índice (fator de 
blocagem)
r1 = nr total de registros de índice no nível 1 
17
Organização indexada multiníveis
 Nível 1: arquivo de índices para os dados
 Nível 2: arquivo de índices para o arquivo de índices 
nível 1
 Se no nível 2 precisar de mais de um bloco, criar nível 3!
 ….
 Busca: binária em cada nível (rápida!) - O(t) - precisa 
acessar t blocos, sendo t o número de níveis
t = ceil(logfbi r1),
fbi = nr de registros que cabem em um bloco de índice (fator de 
blocagem)
r1 = nr total de registros de índice no nível 1 
18
Organização indexada multiníveis
 Nível 1: arquivo de índices para os dados
 Nível 2: arquivo de índices para o arquivo de índices 
nível 1
 Se no nível 2 precisar de mais de um bloco, criar nível 3!
 ….
 Busca: binária em cada nível (rápida!) - O(t) - precisa 
acessar t blocos, sendo t o número de níveis
t = ceil(logfbi r1),
fbi = nr de registros que cabem em um bloco de índice (fator de 
blocagem)
r1 = nr total de registros de índice no nível 1 
19
Organização indexada multiníveis
 Inserção / remoção: ?
20
Organização indexada multiníveis
 Inserção / remoção: cada vez mais 
complicado!!! 
 Posso ter que alterar tudo!
21
Organização indexada multiníveis
 Inserção / remoção: cada vez mais 
complicado!!! 
 Posso ter que alterar tudo!
 O que fazer??? Como ter uma busca eficiente 
mas permitir uma inserção e remoção 
razoável? 
22
Lembrando de AED 1...
 Busca eficiente sem gastar memória:
23
Lembrando de AED 1...
 Busca eficiente sem gastar memória:
 Busca binária (em um vetor)
 Mas o problema era justamente inserção / 
deleção
 Qual era a alternativa de continuar fazendo 
busca binária mas permitir dinamismo de 
inserção / remoção?
24
Lembrando de AED 1...
 Busca eficiente sem gastar memória:
 Busca binária (em um vetor)
 Mas o problema era justamente inserção / 
deleção
 Qual era a alternativa de continuar fazendo 
busca binária mas permitir dinamismo de 
inserção / remoção?
 Árvores Binárias de Busca!!!!
25
Lembrando de AED 1...
 Busca binária (em um vetor):
-4, 2, 3, 5, 19, 21, 25
 Árvores Binárias de Busca:
IMPLEMENTAÇÃO ?
26
Lembrando de AED 1...
 Busca binária (em um vetor):
-4, 2, 3, 5, 19, 21, 25
 Árvores Binárias de Busca:
27
Podemos 
pensar em algo 
semelhante para 
melhorar o 
dinamismo dos 
índices 
múltiníveis?
28
Podemos pensar em algo semelhante para 
melhorar o dinamismo dos índices 
múltiníveis?
 Árvores de busca n+1-árias!
 N = quantos registros são representados em um nó 
(bloco) da árvore, cada registro com uma chave ki
 N+1 ponteiros para nós filhos contendo registros com 
chaves em cada intervalo
O segredo será mantê-las balanceadas!
29
ÁRVORES B !!!
 Registros organizados pela árvore, assim como na árvore 
binária de busca
 Logo, se a chave é única, não há repetição de valores 
 Abaixo é representada só a chave para simplificar a figura, 
mas na verdade deve conter, para cada chave ki, o resto do 
registro (demais dados daquele item) ou um ponteiro pi para o 
registro (ki, pi)
30
ÁRVORES B+
Nós internos (de índices)
Nós folhas (de dados)
Variação da árvore B, na qual:
 os nós internos armazenam apenas os índices (ponteiros de filhos 
e chaves)
 as folhas armazenam os registros de dados (conectadas da 
esquerda para a direita, permitindo acesso sequencial ordenado 
mais eficiente)
 Blocagem menor (cabem mais registros nos nós internos → altura menor)
31
Árvore B Clássica
 Vamos começar estudando a árvore B 
clássica, depois fica fácil adaptar para a árvoreB+
32
Árvore B - Definição
33
Árvore B - Definição
34
Árvore B - Definição
chaves
35
Árvore B - Observação
36
Árvore B – altura máxima
37
Operações Básicas em Árvores B
38
39
o nó x 
raiz
40
Inserção em árvore B
Ex: Como inserir o nó “O” nesta árvore (t = 4)?
As inserções ocorrem sempre nas folhas
41
Inserção em árvore B
Ex: Como inserir o nó “O” nesta árvore (t = 4)?
Antes, precisa resolver o problema do nó cheio...
As inserções ocorrem sempre nas folhas
42
Inserção em árvore B
Ex: Como inserir o nó “O” nesta árvore (t = 4)?
Antes, precisa resolver o problema do nó cheio...
As inserções ocorrem sempre nas folhas
43
Inserção em árvore B
 O que aconteceria se o nó pai também estiver cheio?
 Teria que dividir também o pai, o que poderia causar subdivisões em 
cascata
 Todo nó teria que guardar ponteiros para o nó pai 
 Aumentar o conteúdo de um nó → diminui o fator de blocagem → diminui o 
fator de ramificação → aumenta a altura da árvore 
 Além disso (e principalmente), as subdivisões podem alterar em qual 
nó o registro deve ser armazenado (teria que buscar novamente o 
local da inserção)
Então uma solução é, durante a busca da localização de inserção 
do nó, no caminho da raiz até uma folha, se achar um nó filho (a 
ser seguido) cheio, já o subdivide
Vamos assumir que o nó atual (pai do nó cheio) não é cheio, a 
menos da raiz que deve ser tratada separadamente 
0 2 4 6 8 
10 20
12 14
Ex: inserção do “5”
44
Inserção em árvore B
 O que aconteceria se o nó pai também estiver cheio?
 Teria que dividir também o pai, o que poderia causar subdivisões em 
cascata
 Todo nó teria que guardar ponteiros para o nó pai 
 Aumentar o conteúdo de um nó → diminui o fator de blocagem → diminui o 
fator de ramificação → aumenta a altura da árvore 
 Além disso (e principalmente), as subdivisões podem alterar em qual 
nó o registro deve ser armazenado (teria que buscar novamente o 
local da inserção)
 Então uma solução é, durante a busca da localização de 
inserção do nó, no caminho da raiz até uma folha, se achar um 
nó filho (a ser seguido) cheio, já o subdivide
 Vamos assumir que o nó atual (pai do nó cheio) não é cheio, a 
menos da raiz que deve ser tratada separadamente 
45
Exemplo
Inserção 
t = 3
46
Exemplo
Inserção 
t = 3
47
Exemplo
Inserção 
t = 3
48
Exemplo
Inserção 
t = 3
49
Exemplo
Inserção 
t = 3
50
Exemplo
Inserção 
t = 3
51
Exemplo
Inserção 
t = 3
52
Exemplo
Inserção 
t = 3
53
54
O que precisa fazer?
55
O que precisa fazer?
Aloca e inicializa z
Ajusta y
Ajusta x
56
Aloca e inicializa z
57
Aloca e inicializa z
58
Aloca e inicializa z
Ajusta y
59
Aloca e inicializa z
Ajusta y
60
Aloca e inicializa z
Ajusta y
Ajusta x
61
Aloca e inicializa z
Ajusta y
Ajusta x
62
Aloca e inicializa z
Ajusta y
Ajusta x
Note que assume-se que as chaves e filhos 
começam na posição 1 !!!
63
COMPLEXIDADE:
64
COMPLEXIDADE:
Acessos ao disco: O(1)
CPU: O(t) 
65
66
Não preciso escrever s no disco pois
isso já será feito no B-Tree-Split-Child
67
68
COMPLEXIDADE:
Acessos ao disco: O(h) = O(lgt b)
CPU: O(t*h) = O(t lgt b) 
69
Não preciso escrever s no disco pois
isso já será feito no B-Tree-Split-Child
COMPLEXIDADE:
Acessos ao disco: O(h) = O(lgt b)
CPU: O(t*h) = O(t lgt b) 
70
Remoção em árvores B
x
71
Remoção em árvores B
x
y
72
Remoção em árvores B
x
x
y
y
73
Remoção em árvores B
74
Remoção em árvores B
x
y z
75
Remoção em árvores B
x
x
y
y
z
76
Remoção em árvores B
x
ci[x]
Deletar B:
77
Remoção em árvores B
Algum problema?
x
ci[x]
Deletar B:
78
Remoção em árvores B
Algum problema?
Se ci[x] tem o nr mínimo de chaves, 
 se tiver que deletar desse nó vai dar problema...
x
ci[x]
Deletar B:
79
Remoção em árvores B
x
ci[x]
Deletar B:
80
Remoção em árvores B
x
ci[x]
Deletar B:
81
x
ci[x]
82
x
ci[x]
83
Remoção em árvores B
x
84
Remoção em árvores B
x
x
(pelos procedimentos anteriores, já sei que o nó x tem pelo menos t chaves) 
85
Remoção em árvores B
 Atenção quando um dos nós for a raiz:
 Ela pode ter menos do que t-1 chaves
 Se ficar com zero chaves precisa desalocar o 
bloco e atualizar quem é a nova raiz.
 Precisa de uma camada extra sobre a chamada 
da deleção:
86
Remoção em árvores B
B-Tree-Delete-From-Root(T, k){
r ← raiz[T];
se (n[r] = 0) retorna;
senão B-Tree-Delete(r,k);
se (n[r] = 0 E (! leave[r]){
raiz[T] ← c1[r];
desaloca(r);
}
}
87
Remoção em árvores B
Exercício: IMPLEMENTEM EM CASA!!!!
Pode cair na prova P3….
88
Comentários sobre árvores B+
89
ÁRVORES B+
Nós internos (de índices)
Nós folhas (de dados)
Variação da árvore B, na qual:
 os nós internos armazenam apenas os índices (ponteiros de filhos e 
chaves)
 as folhas armazenam os registros de dados (conectadas da 
esquerda para a direita, permitindo acesso sequencial ordenado 
mais eficiente)
 Blocagem menor (cabem mais registros nos nós internos → altura menor)
90
Comentários sobre árvores B+
Adaptações dos algoritmos:
 Busca: tem sempre que descer às folhas
 Inserção: 
 Split : 
 mediana de uma folha é COPIADA para o pai
 Mediada de um nó interno é MOVIDO para o pai
 Remoção: nas folhas
 Se k (chave a ser removida) ocorrer em um nó interno, 
o valor deve ser substituído pelo valor predecessor nas 
folhas
91
Referências
Livro do Cormen: cap 18 (3a ed.)
Sobre árvores B+: 
SILBERSCHATZ A. et al. Database System 
Concepts. 6th ed. Ed. McGrawHill. Seção 11.3 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84
	Slide 85
	Slide 86
	Slide 87
	Slide 88
	Slide 89
	Slide 90
	Slide 91