UNIVERSIDADE ESTADUAL DE MARINGÁ
DEPARTAMENTO DE INFORMÁTICA
Prof. Yandre Maldonado
Busca em Memória
Secundária
Prof. Yandre Maldonado e Gomes da Costa
[email protected]
1
Busca em Memória Secundária
Prof. Yandre Maldonado
• Busca de um item em uma massa de
dados que não cabe na memória principal;
• Procura-se reduzir ao máximo o número
de acessos à memória secundária;
Por que o tempo de acesso à memória
secundária é tão mais lento?
2
Busca em Memória Secundária
• Segundo (Drozdek, 2002), o tempo de acesso
em memória secundária é dado por:
Tacesso = Tlatência + Tprocura + Ttransferência
Prof. Yandre Maldonado
– Tlatência: tempo decorrido até que o disco gire para que
a cabeça de leitura se posicione sobre o bloco a ser
lido;
– Tprocura: deslocamento da cabeça de leitura até a trilha
a ser lida;
– Ttransferência: dado pela taxa de transferência
(capacidade do dispositivo);
3
1
Busca em Memória Secundária
• Um exemplo:
Prof. Yandre Maldonado
– Supondo um acesso à um dispositivo que gira a 3000
rpm em que se pretende transferir 5 kbytes;
– Neste caso: Tlatência = 10 ms (tempo de meia volta);
– Supondo que sejam gastos 40 ms para se localizar a
trilha a ser lida: Tprocura = 40 ms;
– Considerando um dispositivo com taxa de
transferência de 1000 kbytes/s: Ttransferência = 5 ms;
– Assim:
Tacesso = 10 ms + 40 ms + 5 ms = 55 ms
4
Busca em Memória Secundária
Prof. Yandre Maldonado
• O exemplo mostra um tempo de acesso
da ordem de ms;
• O tempo de execução de instruções pela
CPU é da ordem de microssegundos,
nanossegundos, ou mais rápido;
• Assim fica clara a necessidade de diminuir
acessos em memória secundária;
5
Busca em Memória Secundária
• Árvore B (Bayer e McCreight, 1972)
Prof. Yandre Maldonado
– Estrutura projetada para diminuir o número de
acessos em uma busca;
– Agrupa vários itens em um só nó, formando
um agrupamento conhecido como página;
página
6
2
Busca em Memória Secundária
Prof. Yandre Maldonado
• Observe que a ordem da árvore se altera:
neste exemplo ela se torna quaternária;
• Diminuição do número de buscas na
estrutura;
– Um exemplo (Ziviani, 2002):
• Busca em uma massa com 106 (1 milhão) de
registros;
– Em uma ABB: log2106 ≅ 20
– Na árvore descrita anteriormente: log4106 ≅ 10
– Se ampliássemos o número de registros por nó para
127, qualquer elemento poderia ser encontrado com, no
máximo, 3 buscas na estrutura;
7
Busca em Memória Secundária
• Número de registros por página:
Prof. Yandre Maldonado
– Segundo (Drozdek, 2002), na prática o
número de registros por página deve variar
entre 50 e 500;
– De acordo com (Cormen et al., 2002), este
número pode variar entre 50 e 2000;
– De fato, é interessante que este número seja
tal que corresponda aproximadamente ao
tamanho de um bloco do disco (aproveita-se
melhor o tempo de acesso);
8
Busca em Memória Secundária
• Exercícios:
Prof. Yandre Maldonado
– Calcule o tempo de acesso de 250 kbytes de dados
em um disco que gira a 7200 rpm e que possui taxa
de transferência de 2000 kbytes/s. Considere ainda
que a cabeça de leitura gasta 70 ms para se deslocar
de um extremo ao outro do disco e que, nesta
situação, a cabeça se encontra inicialmente em um
extremo do disco e a trilha a ser lida encontra-se à
uma distância que equivale a 2/3 da distância
máxima possível a ser percorrida;
– Qual é o número médio (aproximado) de buscas
realizadas para se encontrar um registro em uma
Árvore que possui 63 registros por página e que
armazena uma massa de 108 registros?
9
3
Busca em Memória Secundária
• Definição de Árvore B:
– Segundo (Ziviani, 2002), uma Árvore B de
ordem m* é tal que:
Prof. Yandre Maldonado
• Cada página possui, no mínimo m registros (e
m+1 descendentes) e no máximo 2m registros (e
2m+1 descendentes), exceto a página raiz, que
pode conter entre 1 e 2m registros;
• Todas as páginas folha aparecem no mesmo
nível.
10
* Diverge de outras definições.
Busca em Memória Secundária
• Relação entre as páginas e suas páginas
filhas:
chave1
Prof. Yandre Maldonado
pág1
pág2
chave2
...
chave2m
pág3
pág2m
pág2m+1
– Registros armazenados na página i são
menores do que a chave i e maiores do que a
chave i-1;
11
Busca em Memória Secundária
• Exemplo de Árvore B:
30
Prof. Yandre Maldonado
10
3
4
8
9
40
20
11
13
17
25
28
33
36
50
43
45
48
52
55
– Ordem m=2 com 3 níveis;
– Todas as páginas contêm 2, 3 ou 4 registros, exceto
a raiz;
12
4
Busca em Memória Secundária
• Particularidades de Árvore B:
Prof. Yandre Maldonado
– Depois de uma série de inserções e
remoções a árvore apresenta taxa de
ocupação de 69% (Drozdek, 2002);
– Crescimento das folhas para a raiz;
– Inserção de registros:
• Caso trivial: inserir o registro em uma página com
menos de 2m registros;
• Caso a página já tenha 2m registros, deve-se criar
uma nova página;
13
Busca em Memória Secundária
• Exemplos de inserção:
Prof. Yandre Maldonado
– Seqüência a inserir: 50, 20, 30, 37, 42, 47, 41
e 60;
– Árvore de ordem m=2;
a
50
b
20
50
c
20
30
50
d
20
30
37
50
14
Busca em Memória Secundária
– Criação de nova página:
• Transfere-se o elemento central da seqüência que
provocou o estouro para a página do nível superior
e cria-se duas páginas com os demais elementos;
Prof. Yandre Maldonado
– Note que, isto também pode provocar estouro na página
do nível superior;
– Ainda resta inserir: 42, 47, 41 e 60;
d
20
30
37
50
15
5
Busca em Memória Secundária
– Continuando a inserção:
• Próximo registro: chave 42;
d
20
30
37
50
Prof. Yandre Maldonado
– Seqüência ordenada das 2m+1 chaves: 20, 30, 37, 42,
50;
– A chave central (37) é transferida para o nível superior e
cria-se duas páginas com as demais;
e
20
37
30
42
50
16
Busca em Memória Secundária
– Continuando a inserção:
f
37
Prof. Yandre Maldonado
Inserindo 47
20
30
g
42
47
50
41
42
47
37
Inserindo 41
20
30
50
17
Busca em Memória Secundária
– Continuando a inserção:
h
Inserindo 60
Prof. Yandre Maldonado
20
30
37
47
41
42
50
60
– Exercício:
• A partir desta árvore descreva a inserção de uma
seqüência de registros com chaves 31, 32, 43, 44,
61 e 62.
18
6
Busca em Memória Secundária
– Árvore obtida:
i
Prof. Yandre Maldonado
20
30
31
32
37
47
41
42
43
44
50
60
61
62
– Exercício:
• Agora, faça a inserção dos registros com chaves
33 e 45.
19
Busca em Memória Secundária
– Árvore obtida:
Prof. Yandre Maldonado
20
32
30
j
31
37
33
41
42
43
47
44
50
45
60
61
62
– Exercício:
• Agora, faça a inserção dos registro com chave 63.
20
Busca em Memória Secundária
– Árvore obtida:
43
Prof. Yandre Maldonado
k
20
30
31
37
32
33
41
42
44
45
47
61
50
60
62
63
21
7
Busca em Memória Secundária
• Operação de remoção:
– Caso trivial 1:
• Quando o registro a ser removido estiver em uma
página folha com pelo menos m+1 registros;
Prof. Yandre Maldonado
– Quando o registro a ser removido não estiver
numa página folha:
• Substitui-se o registro por um que contenha uma
chave adjacente (antecessora ou sucessora);
– Caso trivial 2:
• Quando o substituo estiver originalmente em uma
página com, pelo menos, m+1 registros;
22
Busca em Memória Secundária
– Exemplo (caso trivial 1)
• Remover o registro com chave 38 da seguinte
árvore:
Prof. Yandre Maldonado
43
31
20
30
32
33
37
38
40
41
42
44
45
47
61
50
60
62
63
23
Busca em Memória Secundária
– Exemplo (caso trivial 2)
• Remover o registro com chave 43 da seguinte
árvore:
Prof. Yandre Maldonado
43
31
20
30
32
33
37
40
41
42
44
45
47
61
50
60
62
63
24
8
Busca em Memória Secundária
Prof. Yandre Maldonado
42
31
20
30
32
37
33
40
44
41
45
47
61
50
60
62
63
25
Busca em Memória Secundária
– E quando, após uma remoção, uma página
fica com menos de m registros?
Prof. Yandre Maldonado
• Neste caso uma propriedade da Árvore B é
violada;
• Com isto, é necessário tomar emprestado um
registro da página vizinha;
– Nesta situação, duas coisas podem ocorrer:
• O número de registros da página vizinha é maior
que m. Assim, basta tomar um registro
emprestado e trazê-lo para a página em questão
via página pai.
26
Busca em Memória Secundária
– Exemplo
• Remover o registro com chave 33 da seguinte
árvore:
Prof. Yandre Maldonado
43
31
20
30
32
33
37
40
41
42
44
45
47
61
50
60
62
63
27
9
Busca em Memória Secundária
Prof. Yandre Maldonado
43
31
20
30
32
40
37
41
44
42
45
47
61
50
60
62
63
28
Busca em Memória Secundária
Prof. Yandre Maldonado
• A segunda possibilidade é a de que a
página vizinha também tenha exatamente
m registros (neste caso as duas juntas têm
2m-1 registros);
• Nesta situação as duas páginas devem ser
“fundidas” em uma só;
29
Busca em Memória Secundária
• Exemplo: remoção do registro com chave 41 da
seguinte árvore:
31
Prof. Yandre Maldonado
20
30
32
40
37
41
42
37
40
31
20
30
32
42
30
10
Busca em Memória Secundária
Prof. Yandre Maldonado
– Observe que, dependendo do contexto, o
processo pode se propagar até a raiz;
– Exemplo: remover o registro com chave 41 da
seguinte árvore:
43
31
20
30
32
40
37
41
44
42
45
47
61
50
60
62
63
31
Busca em Memória Secundária
– Etapa 1:
43
Prof. Yandre Maldonado
31
20
30
32
37
40
44
42
45
47
61
50
60
62
63
32
Busca em Memória Secundária
– Etapa 2:
Prof. Yandre Maldonado
31
20
30
32
37
40
43
42
47
61
44
45
50
60
62
63
33
11
Busca em Memória Secundária
– Resultado:
Prof. Yandre Maldonado
31
20
30
32
37
40
43
47
61
44
42
45
50
60
62
63
34
Busca em Memória Secundária
• Eliminação de uma chave em Árvore B:
Prof. Yandre Maldonado
1. Se a chave não estiver numa folha, troque-a com seu sucessor
imediato.
2. Elimine a chave da folha.
3. Se a folha continuar com o número mínimo de chaves, fim.
4. A folha tem uma chave a menos que o mínimo. Verifique as páginas
irmãs da esquerda e direita:
4.1.se uma delas tiver mais que o número mínimo de chaves, aplique
redistribuição.
4.2.senão concatene a página com uma das irmãs e a chave pai.
5. Se ocorreu concatenação, aplique passos de 3 a 6 para a página
pai.
6. Se a última chave da raiz for removida, a altura da árvore diminui.
35
Busca em Memória Secundária
• Exercício:
– Dada a seguinte Árvore B, descreva o estado da
mesma após realizar a remoção dos registros com
seguintes seqüências de chave;
Prof. Yandre Maldonado
• 45, 30 e 28;
• 50, 8, 10, 4, 20, 40, 55, 17, 33, 11 e 36;
• 3, 9 e 52.
30
3
4
8
9
11
10
20
13
17
25
28
33
36
40
50
43
45
48
52
55
36
12
Busca em Memória Secundária
• Soluções possíveis:
10
Prof. Yandre Maldonado
3
4
8
9
11
13
17
25
40
50
20
33
36
43
48
52
55
13
3
25
9
13
25
43
43
48
52
48
37
Busca em Memória Secundária
• Uma forma de declarar a estrutura de uma
página de ordem 2:
Prof. Yandre Maldonado
const int m = 2;
typedef struct no_arvoreB arvoreB;
struct no_arvoreB {
int num_chaves;
int chaves[2*m];
arvoreB *filhos[2*m+1];
bool folha;
};
38
Busca em Memória Secundária
• Algoritmo de varredura em ordem:
Prof. Yandre Maldonado
void
void em_ordem(arvoreB
em_ordem(arvoreB *raiz)
*raiz)
{{
int
int i;i;
ifif (raiz
(raiz !=
!= NULL)
NULL)
{{
for
for (i(i == 0;
0; ii << raiz->num_chaves;
raiz->num_chaves; i++)
i++)
{{
em_ordem(raiz->filhos[i]);
em_ordem(raiz->filhos[i]);
printf("\n%d",
printf("\n%d", raiz->chaves[i]);
raiz->chaves[i]);
}}
em_ordem(raiz->filhos[i]);
em_ordem(raiz->filhos[i]);
}}
}}
39
13
Busca em Memória Secundária
• Algoritmo de Busca (busca na página):
Prof. Yandre Maldonado
int
int busca_binaria(arvoreB
busca_binaria(arvoreB *no,
*no, int
int info)
info)
{{
int
int meio,
meio, i,i, f;f;
ii == 0;
0;
ff == no->num_chaves-1;
no->num_chaves-1;
while
while (i(i <=
<= f)f)
{{
meio
meio == (i(i ++ f)/2;
f)/2;
ifif (no->chaves[meio]
(no->chaves[meio] ==
== info)
info)
return(meio);
return(meio); //Encontrou.
//Encontrou. Retorna
Retorna aa posíção
posíção em
em que
que aa chave
chave está.
está.
else
else ifif (no->chaves[meio]
(no->chaves[meio] >> info)
info)
ff == meio
meio -- 1;
1;
else
else ii == meio
meio ++ 1;
1;
}}
return(i);
return(i); //Não
//Não encontrou.
encontrou. Retorna
Retorna aa posição
posição do
do ponteiro
ponteiro para
para oo filho.
filho.
}}
40
Busca em Memória Secundária
• Algoritmo de Busca (busca na árvore):
Prof. Yandre Maldonado
bool
bool busca(arvoreB
busca(arvoreB *raiz,
*raiz, int
int info)
info)
{{
arvoreB
arvoreB *no;
*no;
int
int pos;
pos; //posição
//posição retornada
retornada pelo
pelo busca
busca binária.
binária.
no
no == raiz;
raiz;
while
while (no
(no !=
!= NULL)
NULL)
{{
pos
pos == busca_binaria(no,
busca_binaria(no, info);
info);
ifif (pos
(pos << no->num_chaves
no->num_chaves &&
&& no->chaves[pos]
no->chaves[pos] ==
== info)
info)
return(true);
return(true);
else
else no
no == no->filhos[pos];
no->filhos[pos];
}}
return(false);
return(false);
}}
41
Busca em Memória Secundária
• Trabalho prático:
Prof. Yandre Maldonado
– Implementar em linguagem C as operações de
inserção e remoção em uma Árvore B de ordem 2;
– O trabalho pode ser feito individualmente ou em
dupla;
– A data de entrega é 02/10/2006;
– O código fonte deverá ser apresentado pela dupla ao
professor;
– A nota será individual, pois dependerá inclusive do
desempenho durante a apresentação;
– Se forem identificados trabalhos copiados, todos os
envolvidos terão nota zero.
42
14
Busca em Memória Secundária
• Referências Bibliográficas:
Prof. Yandre Maldonado
– Cormen, Thomas H. et al. Algoritmos – teoria
e prática. Rio de Janeiro: Elsevier, 2002;
– Drozdek, Adam. Estrutura de Dados e
Algoritmos em C++. São Paulo: Pioneira
Thomsom Learning, 2002;
– Ziviani, Nivio. Projeto de Algoritmos – com
implementações em Pascal e C. São Paulo:
Pioneira Thomsom Learning, 2002;
43
15