04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Universidade Federal do Espírito Santo
Centro de Ciências Agrárias – CCA-UFES
Departamento de Computação
Métodos de Acesso à Arquivo
Estrutura de Dados II
Estrutura de Dados II
COM10078 - 2015-II
Prof. Marcelo Otone Aguiar
[email protected]
www.marceloaguiar.pro.br
Universidade Federal do Espírito Santo - CCA-UFES
Conteúdo Programático da Disciplina
- Métodos de Acesso a Arquivos
‣Estrutura de arquivos;
‣Acesso sequencial;
‣Acesso direto;
2
C.H. Prevista
4 horas
Universidade Federal do Espírito Santo
CCA-UFES
1
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Conceitos Gerais
•
A pesquisa em memória secundária envolve arquivos contendo
um número de registros maior do que o número que a memória
interna pode armazenar.
•
Os algoritmos e as estruturas de dados para processamento
em memória secundária têm de levar em consideração os
seguintes aspectos:
3
•
O custo para acessar um registro é algumas ordens de
grandeza maior do que o custo de processamento na
memória primária.
•
Em memórias secundárias, apenas um registro pode ser
acessado em um dado momento, ao contrário das memórias
primárias, que permitem o acesso a qualquer registro de
um arquivo a um custo uniforme.
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Conceitos Gerais
• (Continuação)
• Para desenvolver um método de pesquisa eficiente,
o aspecto sistema de computação é da maior
importância. As características da arquitetura e
do sistema operacional da máquina tornam os
métodos de pesquisa dependentes de parâmetros que
afetam seus desempenhos. Assim, a transferência
transfer ncia
de blocos entre as memórias
mem rias primária
prim ria e
secundária
secund ria deve ser tão
t o eficiente quanto as
características
caracter sticas dos equipamentos disponíveis
dispon veis o
permitam.
permitam
4
Universidade Federal do Espírito Santo
CCA-UFES
2
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Conceitos Gerais
• A medida que cresce o volume de dados e/ou a
freqüência e a complexidade dos acessos, crescem
também os problemas de eficiência do armazenamento
dos arquivos e do acesso a seus registros.
• Sendo então necessário a sofisticação das técnicas
de armazenamento e recuperação de dados.
• A maneira intuitiva de armazenar um arquivo
consiste na distribuição dos seus registros em uma
ordem arbitrária, um após o outro, dentro da área
destinada a contê-lo.
5
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Conceitos Gerais
• Esta ordem pode ser, por exemplo,
exemplo aquela na qual os
registros são gerados.
• Isto causa uma dificuldade na localização dos
registros e uma perda de eficiência, porém esta
técnica intuitiva é bastante usada, principalmente
durante as fases preliminares da geração de um
arquivos.
6
Universidade Federal do Espírito Santo
CCA-UFES
3
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
ESTRUTURA DOS ARQUIVOS
Universidade Federal do Espírito Santo
CCA-UFES
7
Universidade Federal do Espírito Santo - CCA-UFES
Estrutura dos Arquivos
• Um
arquivo é formado por uma coleção de registros
lógicos
gicos,
gicos cada um deles representando um objeto ou
entidade.
• Um
registro lógico, ou simplesmente registro, é
formado por uma sequência de itens, sendo cada item
chamado campo ou atributo.
atributo Cada item corresponde a
uma característica ou propriedade do objeto
representado.
• Cada campo possui um
nome, um tipo e
um comprimento. O comprimento dos valores de um
atributo pode ser constante para todos os registros
do arquivo, ou variável.
8
Universidade Federal do Espírito Santo
CCA-UFES
4
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Estrutura dos Arquivos
• O armazenamento de um arquivo é feito, via de
regra, por blocos de registros lógicos
l gicos (um bloco é
chamado registro físico), sendo, em cada leitura ou
gravação, lido ou gravado todo um bloco e não
apenas um registro lógico.
• Uma
chave é uma sequência de um ou mais campos em
um arquivo.
• Uma
chave primária é uma chave que apresenta um
valor diferente para cada registro do arquivo,
arquivo de
tal forma que, dado um valor da chave primária, é
identificado um único registro do arquivo.
Usualmente a chave primária é formada por um único
campo.
Universidade Federal do Espírito Santo
CCA-UFES
9
Universidade Federal do Espírito Santo - CCA-UFES
Estrutura dos Arquivos
•
Uma chave secundária difere de uma primária pela
possibilidade de não possuir um valor diferente para cada
registro. Assim, um valor de uma chave secundária
identifica um conjunto de registros.
•
Chave de acesso é a chave utilizada para identificar o(s)
registro(s) desejado(s) em uma operação de acesso a um
arquivo.
•
Argumento de pesquisa é o valor da chave de acesso em uma
operação.
•
Chave de um registro é o valor de uma chave primária em um
particular registro do arquivo.
•
Chave de ordenação é a chave primária usada para
estabelecer a seqüência na qual devem ser dispostos
(física ou logicamente) os registros de um arquivo.
10
Universidade Federal do Espírito Santo
CCA-UFES
5
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
ACESSO SEQUENCIAL
Universidade Federal do Espírito Santo
CCA-UFES
11
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Sequenciais
• Em um arquivo sequencial, os registro são dispostos
ordenadamente, obedecendo a seqüência determinada
por uma chave primária, chamada chave de ordenação.
12
Número
1
2
3
4
Nome
Ana
Bruno
Carlos
Elias
Idade
30
35
27
24
Salário
1000
2000
1500
1200
5
6
7
8
9
Fábio
Gilberto
Hilda
Isa
Marcela
26
31
24
25
23
1300
1600
1000
1600
1800
Universidade Federal do Espírito Santo
CCA-UFES
6
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Sequenciais
• Esta organização, que representa um aperfeiçoamento
em relação àquela na qual os registros são
dispostos aleatoriamente, representa, também, uma
perda de flexibilidade por não acomodar com
simplicidade as operações de modificação do
arquivo.
• O acesso a uma registro, dado um argumento de
pesquisa, é facilitado se a chave de acesso
coincide com a chave de ordenação (ou com sua parte
inicial), pois, nos demais casos, não há vantagem
na seqüencialidade do arquivo.
13
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Sequenciais Indexados
• Quando em um arquivo sequencial o volume de acessos
aleatórios torna-se muito grande, se faz necessário
a utilização de uma estrutura de acesso, associada
ao arquivo, que ofereça maior eficiência na
localização de um registro identificado por um
argumento de pesquisa.
• Um arquivo sequencial, acrescido em um índice
ndice
(estrutura de acesso) constitui um arquivo
seqüencial indexado.
• Um índice é formado por uma coleção de pares, cada
um deles associando um valor da chave de acesso a
um endereço no arquivo. Assim, um índice é sempre
específico para uma chave de acesso.
14
Universidade Federal do Espírito Santo
CCA-UFES
7
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Sequenciais Indexados
• Além do arquivo sequencial e do índice
ndice,
ndice um arquivo
seqüencial indexado possui áreas de extensão que são
utilizadas para a implementação da operação de
inserção de registros.
• A finalidade de um índice é permitir rápida
r pida
determinação
endereço
determina o do endere
o de um registro do arquivo,
arquivo
dado um argumento de pesquisa.
• O endereço identifica a posição onde está armazenado o
registro, na memória secundária.
• Usualmente, cada entrada do índice, formada por um par
(chave do registro, endereço do registro), ocupa um
espaço bem menor do que o registro de dados
correspondente, o que faz com que a área ocupada pelo
índice seja menor do que aquela ocupada pelos dados.
Universidade Federal do Espírito Santo
CCA-UFES
15
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Sequenciais Indexados
• Com isto a pesquisa sobre o índice pode ser feita
com maior rapidez do que se fosse feita diretamente
sobre o arquivo de dados correspondente.
• Este fato constitui a justificativa maior para a
utilização dos índices.
NUMERO
ENDERECO
Número
Nome
1075
1
1
1000
Ana
30
1350
4
2
1050
Bruno
35
2000
1480
7
3
1075
Carlos
27
1500
4
1300
Elias
24
1200
5
1325
Fábio
26
1300
6
1350
Gilberto
31
1600
7
1400
Hilda
24
1000
8
1440
Isa
25
1600
9
1480
Marcela
23
1800
Índice
Primário
16
Idade Salário
1000
Universidade Federal do Espírito Santo
CCA-UFES
8
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Área de Extensão
• A área
rea de extensão
extens o (também chamada área de
overflow) destina-se a conter os registros
inseridos, em um arquivo seqüencial indexado, após
a criação do arquivo.
• Ela constitui uma extensão da área principal de
dados do arquivo.
• Áreas de extensão são necessárias em arquivos
seqüenciais indexados, porque nesses não é viável a
implementação da operação de inserção de registros
do mesmo modo que nos arquivos seqüenciais.
17
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Área de Extensão
• Naquele processo, a maioria dos registros muda de
endereço, o que obrigaria uma completa alteração
nas entradas do índice, a cada atualização do
arquivo.
• Uma possível implementação de áreas de extensão em
um arquivo sequencial indexado consiste em destinar
um em cada registro da área principal um campo de
elo para conter o endereço da lista encadeada de
seus sucessores (ou antecessores) alocados na área
de extensão.
18
Universidade Federal do Espírito Santo
CCA-UFES
9
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Área de Extensão
NUMERO
ENDERECO
1075
1
1350
4
1480
7
Índice
Primário
Registro a ser inserido
1030
1310
1025
Ø
19
Jamanta
Bela
Zacarias
1800
1600
1000
Ø
Número
Nome
1
1000
Ana
Salário Elo
1000
2
1050
Bruno
2000
3
1075
Carlos
1500
Ø
4
1300
Elias
1200
5
1325
Fábio
1300
Ø
101
Ø
6
1350
Gilberto
1600
Ø
7
1400
Hilda
1000
Ø
8
1440
Isa
1600
Ø
9
1480
Marcela
1800
Ø
Ø
100
Ø
100
1025
Zacarias
1000
102
102
Ø
101
1310
Bela
1600
Ø
102
1030
Jamanta
1800
Ø
Área de extensão
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Indexados
• Nos arquivos sequenciais indexados, o compromisso
de manter os registros fisicamente ordenados pelo
valor da chave de ordenação acarreta uma série de
problemas, principalmente no que diz respeito à
operação de inserção de um registro, como a
utilização de áreas de extensão e reorganizações
periódicas.
• À medida que decresce a frequência de acessos
seriais, relativamente à frequência de acessos
aleatórios, a manutenção da sequencialidade física
do arquivo encontra uma compensação cada vez menor
em termos de eficiência de acesso, até tornar-se
antieconômica.
20
Universidade Federal do Espírito Santo
CCA-UFES
10
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Indexados
• A partir deste ponto, torna-se mais conveniente o
uso de um arquivo indexado, no qual os registros
são acessados sempre através de um ou mais índices,
não havendo qualquer compromisso com a ordem física
de instalação dos registros.
• A liberdade na escolha do endereço no qual um
registro é armazenado representa um ganho de
flexibilidade que permite maior eficiência,
principalmente na operação de inserção de um
registro, conduzindo, também, a uma simplificação
da estrutura geral do arquivo, sendo dispensados os
mecanismos complexos de administração de áreas de
extensão.
Universidade Federal do Espírito Santo
CCA-UFES
21
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Indexados
NÚMERO ENDERECO
1000
1050
1075
1300
1325
1350
1400
1480
Índice
4
6
7
9
2
3
1
5
1
Número
1400
Nome
Isa
Idade
25
Salário
1600
2
3
4
1325
1350
1000
Hilda
Ana
Carlos
24
30
27
1000
1000
1500
5
1480
Bruno
35
2000
6
7
1050
1075
Marcela
Gilberto
23
31
1800
1600
8
9
1300
Fábio
26
1300
ÁREA DE DADOS NO DISCO
Exaustivo
22
Universidade Federal do Espírito Santo
CCA-UFES
11
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Indexados
• Em um arquivo indexado, podem existir tantos
índices quantas forem as chaves de acesso aos
registros.
• Um índice
ndice consiste de uma entrada para cada
registro considerado relevante com relação à chave
de acesso associada ao índice.
• As entradas do índice são ordenadas pelo valor da
chave de acesso, sendo cada uma delas constituída
por um par (chave do registro, endereço do
registro).
• A sequencialidade física das entradas no índice
visa a tornar mais eficiente o processo de busca e
permitir o acesso serial ao arquivo.
23
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Indexados
• Um índice é dito exaustivo quando possui uma
entrada para cada registro do arquivo e seletivo
quando possui entradas apenas para um subconjunto
de registros.
• O subconjunto é definido por uma condição relativa
à chave de acesso e/ou a outros atributos do
arquivo.
• Um exemplo de índice seletivo seria o índice dos
funcionários estáveis (há mais de 10 anos na
empresa) sobre o cadastro geral de funcionários de
uma empresa.
24
Universidade Federal do Espírito Santo
CCA-UFES
12
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Indexados
• O maior problema relacionado com a utilização de
arquivos indexados diz respeito à necessidade de
atualização
ndices,
atualiza o de todos os índices
ndices quando um registro
é inserido no arquivo.
• Atualizações nos índices também são necessárias
quando a alteração de um registro envolve atributos
associados a índices.
• Nos arquivos sequenciais indexados, a necessidade
de alteração dos índices é eliminada pelo uso de
áreas de extensão e encadeamento na implementação
de inserções; no entanto, esta estratégia não é
condizente com a idéia de arquivos indexados, nos
quais a manutenção constante dos índices é
necessária.
25
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
ACESSO DIRETO
26
Universidade Federal do Espírito Santo
CCA-UFES
13
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Diretos
• A ideia básica de um arquivo direto consiste na
instalação
instala o dos registros em endereços
endere os determinados
com base no valor de uma chave primária
prim ria,
ria de modo
que se tenha acesso rápido aos registros
especificados por argumentos de pesquisa, sem que
haja necessidade de percorrer uma estrutura
auxiliar (índice).
• Um arquivo direto é semelhante a um arquivo
indexado, no sentido de que, nos dois casos, o
objetivo principal é a obtenção
obten o de acesso
aleatório
aleat rio eficiente.
eficiente
• Em um arquivo direto, aos invés do índice é usada
uma função
fun o que calcula o endereço
endere o do registro a
partir do argumento de pesquisa.
27
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Diretos
• As duas organizações possuem diferenças
importantes, além do modo pelo qual é feito o
acesso.
• Uma delas é o fato de que nos arquivos indexados,
ao contrário dos diretos, o endereço onde um
registro é armazenado independe do valor de sua
chave,
• e uma outra, muito importante, diz respeito a
acessos seriais, que nos arquivos indexados são
providos por meio de índices e nos arquivos diretos
não são previstos, de acordo com a ideia básica.
28
Universidade Federal do Espírito Santo
CCA-UFES
14
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Calculo do Endereço
• Problema: encontrar uma função F que transforme o
valor C da chave de um registro no endereço E
correspondente.
• Existem dois tipos de funções:
fun es:
• Funções
Fun es determinísticas:
determin sticas: associam um único valor
da chave de acesso a cada endereço. Ex.: F(C)= x+1
• Funções
Fun es não
n o-determinísticas
determin sticas (ou probabilísticas):
probabil sticas):
geram para cada valor da chave de acesso um
endereço com a maior unicidade possível “t
tão
o único
nico
quanto possível
Ex.:
poss vel”.
vel
Ex.: F(C)= x mod 4
• Neste caso, pode ocorrer de gerar, para valores
29
distintos de chave, o mesmo endereço, fato este que
é denominado colisão.
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Calculo do Endereço
chave: 150
E=F(chave)
E = 3
30
1
2
3
4
5
NÚMERO
200
NOME
PAULO
SALÁRIO
3100
150
MARIA
2500
250
FABIO
2500
Universidade Federal do Espírito Santo
CCA-UFES
15
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Tratamento de Colisões
• Colisão:
Colis o: ocorre quando é atribuído o mesmo endereço
a dois diferentes valores da chave de acesso
• Havendo colisão, é necessário fazer o tratamento de
colisões, escolhendo um novo endereço para o
registro que a provocou
• Os dois principais métodos de tratamento de colisão
são: Endereçamento
Endere amento Aberto e Encadeamento Puro
31
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Tratamento por Endereço Aberto
• Consiste em fazer uma busca sobre o arquivo
para localização de um endereço livre, sendo
nele armazenado o registro.
• A pesquisa do endereço livre é de forma
sequencial, ou seja, se o endereço E gerado
pela chave estiver ocupado, o próximo a ser
consultado será o endereço E + 1,
1 E +
2,...,M,1,1,...,E - 1 até se encontrar um
lugar vago para armazenar o registro.
32
Universidade Federal do Espírito Santo
CCA-UFES
16
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Tratamento por Encadeamento Puro
• Neste caso, todos ou parte dos registros que
colidem em um mesmo endereço são juntados em
uma lista encadeada, à qual se tem acesso por
meio do endereço gerado pela função de
aleatorização.
33
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
ARQUIVOS INVERTIDOS
34
Universidade Federal do Espírito Santo
CCA-UFES
17
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Invertidos
• Esta organização é baseada em uma mudança nos
papeis de registro e atributos, de tal forma que,
em vez de serem coletados os valores dos atributos
para cada registro, são identificados os registros
que possuem cada um dos particulares valores da
chave de acesso considerada.
• A cada um dos valores da chave de acesso, presentes
no arquivo, é associada uma lista de identificações
de registros, chamada lista invertidas.
35
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Invertidos
• As técnicas usuais na organização de índices
ndices são
válidas também para este caso.
• Contudo, devendo ser tomado o devido cuidado com o
fato de que, em um arquivo invertido, a cada valor
da chave de acesso está associado não apenas um
endereço do registro, mas sim um conjunto de
endereços dos registros que possuem aquele valor da
chave.
• O conjunto de listas invertidas associado a uma
chave de acesso é chamado inversão, sendo que um
arquivo invertido pode assumir uma ou mais
inversões.
36
Universidade Federal do Espírito Santo
CCA-UFES
18
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Arquivos Invertidos
Idade
21
1
Endereços
4
7
23
2
6
25
26
3
5
8
9
Salário
Chaves
2500 1050
3000 1800 2400
3500
4000
1100
1250
7000
1850
37
1200
1950
Chave
Nome
Idade
Salário
1
2
1050
1200
Ademar
Iara
21
23
2500
3500
3
4
5
6
2400
1850
1100
Marcos
Tatiana
Pedro
25
21
26
3000
7000
3500
1250
2000
Enio
Sandra
23
21
4000
4000
1800
Claudia
25
3000
1950
Ivan
23
4000
7
2000
8
9
Universidade Federal do Espírito Santo
CCA-UFES
Universidade Federal do Espírito Santo - CCA-UFES
Inversão por Endereço
• Na primeira inversão, os registros são
identificados por seus endereços físicos.
• Esta modalidade apresenta a vantagem de permitir o
acesso direto ao registro, mas acarreta o problema
de que as listas são válidas apenas para aquela
disposição física dos registros.
• Sendo que, caso o arquivo venha a sofrer uma
reorganização que envolva mudança nos endereços dos
registros, todas as inversões deverão ser novamente
geradas.
38
Universidade Federal do Espírito Santo
CCA-UFES
19
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Inversão por Chave
• Uma alternativa para este problema consiste na
identificação dos registros por meio de uma de suas
chaves primárias, como na segunda inversão.
• Com isto as listas invertidas passam a ser
independentes da localização física dos registros.
• No entanto, há perda de eficiência no acesso, em
virtude da necessidade de determinar o endereço do
registro uma vez obtida a sua chave primária na
lista.
Universidade Federal do Espírito Santo
CCA-UFES
39
Universidade Federal do Espírito Santo - CCA-UFES
Comparativo
Arquivo
Seqüencial
Vantagens
- Acessos seqüenciais
mais eficientes.
-Utilizam índices, que
Seqüencial Indexado agilizam a consulta por
estarem na RAM.
-Não existem áreas de
extensão
- Registros sem
Indexado
compromisso com
armazenamento físico.
Direto
Invertido
40
-Acesso direto, sem
necessidade do índice.
Desvantagens
- Operações de
modificações não são
simples.
- Necessidades de áreas de
extensão, que precisam ser
reorganizadas.
- Atualização do índice
quando da inserção de um
registro.
- Determinar funções que
gerem menor número de
colisões
- As listas invertidas
- Acesso direto ao
registro após localização valem apenas para aquela
disposição física do
da lista invertida.
arquivo.
Universidade Federal do Espírito Santo
CCA-UFES
20
04/11/2015
Universidade Federal do Espírito Santo - CCA-UFES
Próximo Conteúdo
- Busca e Ordenação em memória Secundária
‣Quicksort Externo;
‣Acesso Indexado;
‣ Árvores n-árias;
‣Indexação por espalhamento;
41
C.H. Prevista
12 horas
Universidade Federal do Espírito Santo
CCA-UFES
21