Árvore-B com 3 chaves por página
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11 20
log31 16  1  2.043  3 níveismínimos
Chaves: 4
4
Chaves: 4 3
4
Chaves: 4 3
3 4
Chaves: 4 3 1
3 4
Chaves: 4 3 1
1 3
4
Chaves: 4 3 1 9
1 3
4
Chaves: 4 3 1 9
1 3
4 9
Chaves: 4 3 1 9
4
1 3
9
Chaves: 4 3 1 9 6
4
1 3
9
Chaves: 4 3 1 9 6
4
1 3
6 9
Chaves: 4 3 1 9 6 8
4
1 3
6 9
Chaves: 4 3 1 9 6 8
4
1 3
6 8 9
Chaves: 4 3 1 9 6 8 5
4
1 3
6 8 9
Chaves: 4 3 1 9 6 8 5
4
1 3
5 6
8 9
Chaves: 4 3 1 9 6 8 5
4 8
1 3
5 6
9
Chaves: 4 3 1 9 6 8 5 10
4 8
1 3
5 6
9
Chaves: 4 3 1 9 6 8 5 10
4 8
1 3
5 6
9 10
Chaves: 4 3 1 9 6 8 5 10 13
4 8
1 3
5 6
9 10
Chaves: 4 3 1 9 6 8 5 10 13
4 8
1 3
5 6
9 10 13
Chaves: 4 3 1 9 6 8 5 10 13 7
4 8
1 3
5 6
9 10 13
Chaves: 4 3 1 9 6 8 5 10 13 7
4 8
1 3
5 6 7
9 10 13
Chaves: 4 3 1 9 6 8 5 10 13 7 14
4 8
1 3
5 6 7
9 10 13
Chaves: 4 3 1 9 6 8 5 10 13 7 14
4 8
1 3
5 6 7
9 10
13 14
Chaves: 4 3 1 9 6 8 5 10 13 7 14
4 8 13
1 3
5 6 7
9 10
14
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2
4 8 13
1 3
5 6 7
9 10
14
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2
4 8 13
1 2 3
5 6 7
9 10
14
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18
4 8 13
1 2 3
5 6 7
9 10
14
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18
4 8 13
1 2 3
5 6 7
9 10
14 18
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19
4 8 13
1 2 3
5 6 7
9 10
14 18
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19
4 8 13
1 2 3
5 6 7
9 10
14 18 19
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11
4 8 13
1 2 3
5 6 7
9 10
14 18 19
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11
4 8 13
1 2 3
5 6 7
9 10 11
14 18 19
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11 20
4 8 13
1 2 3
5 6 7
9 10 11
14 18 19
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11 20
4 8 13
1 2 3
5 6 7
9 10 11
14 18
19 20
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11 20
4 8
1 2 3
5 6 7
13 19
9 10 11
14 18
20
Chaves: 4 3 1 9 6 8 5 10 13 7 14 2 18 19 11 20
FIM!
13
4 8
1 2 3
5 6 7
19
9 10 11
14 18
20
Estrutura das páginas
2
D
0
A B
3
E
C
RRN
K
H
8
G
5
I
J
L M
chaves
Página 2
3
D
H
filhos
K
0
3
8
5
contador de chaves
Página 3
2
E
G
NIL NIL NIL NIL
FUNCTION busca (RRN, CHAVE, ACHEI-RRN, ACHEI-POS)
if RRN = NIL then /* para a recursão */
return NAO-ACHEI
else
carregue a página indicada por RRN em PAGE
procure a CHAVE em PAGE
POS = posição onde CHAVE ocorre ou devia ocorrer
if CHAVE encontrada then
ACHEI-RRN = RRN
ACHEI-POS = POS
return ACHEI
else
/* desçe um nível na direção do FILHO */
return(busca(PAGE.FILHO[POS], CHAVE, ACHEI-RRN, ACHEI-POS))
endif
endif
end FUNCTION