Árvores B

Motivação: pesquisa em disco
 Tempo de acesso a disco determinante nas operações
 Com disco de 10 ms de tempo de acesso:
100 acessos por segundo
em máquina de 25 MIPS, 1 acesso custa tanto como 250 000 instruções
... e velocidade de cálculo tem aumentado mais que velocidade de disco
 Podemos gastar muito cálculo para evitar 1 acesso a disco
 Exemplo: registo dos cidadãos portugueses guardado em árvore binária





N=10M de registos, chave de 32 bytes e total de registo de 256 bytes (BD 2.5GB)
Blocos de 8KB  312 500 blocos
Pior caso: acesso em tempo linear, 312 500 acessos a disco (52 min) (ou 10M !)
Médio: 1.38 log N acessos, 32 acessos a disco ou 0.3s
Nó a profundidade tripla: 100 acessos a disco ou 1s
B-tree
Árvore B

Árvore equilibrada multivia
 Objectivo: pesquisa externa, minimizar acessos a disco
 Utilização: construir índices auxiliares em Bases de Dados
 nos nós existem referências a blocos do disco
 escolha da ordem da árvore depende do número de registos do índice que cabem
num único bloco (unidade básica de acesso a disco)
Uma árvore-B de ordem M é uma árvore de M vias em que
1. Os dados estão guardados nas folhas
2. Os nós internos guardam até M-1 chaves; a chave i representa a menor
chave na subárvore i+1
3. A raiz é uma folha ou tem entre 2 e M filhos
4. Todos os nós internos, excepto a raiz, têm entre M/2 e M filhos não
vazios.
5. Todas as folhas estão à mesma profundidade e têm entre L/2 e L registos
de dados
B-tree
Árvore B para exemplo do ficheiro

Cada nó deve caber em 1 bloco de disco
 Assumir bloco de disco de 8 192 bytes
 Em cada nó interior:
 M-1 chaves de 32 bytes e M ramos com 4 bytes (endereço de novo bloco)
 32 ( M -1) + 4 M  8192
 M = 228, M/2 = 114
 Nos nós folha:
 256 bytes para cada registo
 bloco comporta 32 registos
 L = 32
 No ficheiro de 10 000 000 de registos
 no máximo 10 000 000 /16 = 625 000 folhas
 no máximo  log 114 625 000  = 3 níveis acima das folhas
B-tree
Árvore-B de ordem 4
M= 4
21
12
1,4,8,11
15
12,13
25
15,18,19
21,24
31
25,26
48
72
41
31,38
59
41,43,46
48,49,50
84
59,68
72,78
91
84,88
91,92,99
• até 3 chaves em cada nó interno
• até 4 ponteiros em cada nó interno (mínimo é 2)
• L = 4 (mas poderia ter outro valor)
B-tree
Inserção em Árvore-B 2-3
22 : -
22 : -
16 : -
8,11,12
16, 17
18
41 : 58
22,23,31
41, 52
16 : -
41 : 58
8,11,12 16,17,18
58,59,61
22,23,31
41, 52
1
58,59,61
22 : -
2-3 (número de filhos)
Mínimo: 2
11 : 16
19
41 : 58
Máximo: 3
1, 8
11, 12
16, 17,18 22,23,31
41, 52
58,59,61
B-tree
Inserção em Árvore-B 2-3
22 : -
11 : 16
1, 8
11, 12
41 : 58
16, 17
18, 19
22,23,31
41, 52
58,59,61
16 : 22
11 : -
1, 8
11, 12
18 : -
16, 17
18, 19
41 : 58
22,23,31
41, 52
28
58,59,61
B-tree
Inserção em Árvore-B 2-3
16 : 22
11 : -
1, 8
11, 12
18 : -
16, 17
18, 19
41 : 58
22, 23
28, 31
41, 52
58,59,61
16 : 22
11 : -
1, 8
11, 12
18 : -
16, 17
18, 19
28 : -
22, 23
28, 31
58 : -
41, 52
58,59,61
B-tree
Inserção em Árvore-B 2-3
16 : 22
11 : -
1, 8
18 : -
11, 12
16, 17
28 : -
18, 19
22, 23
(repetida)
58 : -
28, 31
41, 52
58,59,61
22 : 16 : -
11 : -
1, 8
11, 12
• Árvore-B
cresce para a raiz
41 : -
18 : -
16, 17
18, 19
28 : -
22, 23
28, 31
58 : -
41, 52
58,59,61
B-tree
Apagamento em Árvore B

Pesquisa da chave a apagar e apagamento na folha respectiva
 Se a folha fica com número de chaves não abaixo do mínimo: terminar
 Se a folha fica com número de chaves abaixo do mínimo: reparar árvore
 Se a folha do lado tiver número de chaves acima do mínimo: pedir chave emprestada

“do lado” significa com o mesmo pai, para não complicar excessivamente a manutenção dos nós interiores
 Se a folha do lado não tiver número de chaves acima do mínimo: fundir folhas e propagar
 Havendo fusão de nós, a reparação prossegue nos níveis superiores da árvore
 Se a fusão de nós resulta em a raiz ter apenas 1 filho: raiz passa para o filho e altura da
árvore diminui

Árvore-B cresce e diminui na raiz
 altura da árvore aumenta quando se tem de partir a raiz (e criar novo nó raiz)
 altura da árvore diminui quando a raiz tem 2 filhos e estes se fundem
B-tree
Árvore-B para pesquisa em memória
Árvore de ordem 5 ou B 3-5
a, b, f, g
k
d, h, m
a b f g
f
a b
f
g k
j
a b d
e, s, i, r
f j
a b d
g h k m
g h
f j
k m
a b d e
g h i
k mr s
B-tree
Inserção em árvore-B 3-5
x
f j r
a b d e
g h i
k m
s x
c, l, n, t, u
c f j r
a b
d e
g h i
k l m n
s t u x
B-tree
Inserção em árvore-B 3-5
p
j
c f
a b
d e
m r
g h i
k l
n p
s t u x
• Nesta representação:
• chaves estão organizadas na árvore à maneira das árvores de pesquisa
• nós internos e folhas são da mesma natureza
Apropriado para estruturas em memória central
B-tree
Exercício
a) Inserir a chave 40
M= 4
13
7
2
3
23
5
7
13
11
17
31
19
23
43
31
37
41
43
47
29
B-tree
Exercício (cont.)
M= 4
13
7
2
3
23
5
7
13
11
17
31
19
23
43
31
29
37
43
40
47
41
B-tree
Exercício (cont.)
b) Apagar a chave 7
M= 4
7
2
3
5
7
13
11
17
13
40
23
31
19
23
43
31
29
37
43
40
47
41
B-tree
Exercício (cont.)
b) Apagar a chave 11
M= 4
5
2
3
13
5
11
17
13
40
23
31
19
23
43
31
29
37
43
40
47
41
B-tree
Exercício (cont.)
M= 4
2
3
5
13
17
13
40
23
31
19
23
43
31
29
37
43
40
47
41
B-tree
Exercício (fim)
M= 4
23
13
2
3
40
43
31
5
13
17
19
23
31
29
37
43
40
47
41
B-tree