UFPA – UNIVERSIDADE FEDERAL DO PARÁ
Centro de Ciências Exatas e Naturais
Departamento de Informática
Bacharelado em Ciência da Computação
Estrutura de Dados II
Prof.: Antonio B. C. Sampaio
Conceitos Básicos de Organização de Arquivos
Equipe:
• Leandro Lages de C. Faria
• Rodrigo Pinto Cardoso
nº 9908801201
nº 9908801401
Introdução
-
-
Pequenos volumes de dados e o acesso a eles
Problema: aumento do volume de dados e
freqüência de acesso
Uma maneira intuitiva de armazenar arquivos
Estratégia seqüencial ainda muito utilizada
Terminologia
-
O que é arquivo?
-
Registro lógico
-
Características dos campos
-
Registro lógico X Registro físico
Exemplo
Terminologia
-
O que é chave?
Chave primária
Chave secundária
Chave de acesso
Argumento de pesquisa
Chave de um registro
Chave de ordenação
Arquivo Seqüencial
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
Operações
Acesso a um registro
 Inserção de um registro
 Exclusão de um registro
 Alteração de um registro
 Leitura exaustiva dos registros
 Reorganização dos arquivos

Acesso a um registro
Acesso serial (seqüencial)
 Acesso aleatório

– Chave de acesso  chave de ordenação
» Pesquisa seqüencial
– Chave de acesso = chave de ordenação
» Pesquisa binária
Inserção de um registro
Arquivo S – arquivo seqüencial
 Arquivo T – arquivo de transações
 Arquivo A – arquivo atualizado
 A = S e T intercalados
 O problema de inserção de apenas um registro
 Arquivo T usado como uma extensão de S

Exclusão de um registro

Pode ser implementada como a inserção
– Criação de um arquivo de transações.

Pode ser implementada com ajuda de um
campo adicional
– Vantagens
» Eliminação da necessidade de movimentação de
outros registros para preenchimento do espaço
liberado pelo excluído.
Alteração de um registro
Em que consiste?
 Condições para efetuar a operação:

– A alteração não pode fazer com que o registro
assuma um tamanho maior que o original, senão o
registro não poderia ser gravado por falta de espaço
– Não mudar o valor do atributo que seja chave de
ordenação, pois isso implicaria numa mudança de
posição do registro dentro do arquivo
Leitura Exaustiva
Exige a manipulação em paralelo do
arquivo principal S e do arquivo de
transações S
 Seqüência ditada pela chave de ordenação
 Os registros marcados como “excluídos”
não são considerados
 O próximo registro a ser considerado é
aquele de menor chave, considerando o
próximo registro de S e de T.

Reorganização do arquivo
Consiste na geração de um arquivo
seqüencial A, obtido pela intercalação do
arquivo S com o arquivo T de transações.
 Feita através de uma leitura exaustiva de S,
juntamente com T
 Resultado transferido para o arquivo A
 Precede geralmente ao uso do arquivo
gerado para emissão de relatórios ou
efetivação de consultas

Arquivo Seqüencial Indexado




Necessidade de maior eficiência na localização de
um registro num arquivo seqüencial
Um arquivo seqüencial acrescido de um índice
constitui um Arquivo Seqüencial Indexado
Um índice é formado por uma coleção de pares,
com cada par associando uma chave de acesso a
um endereço
Um arquivo seqüencial indexado possui áreas de
extensão para a implementação da operação de
inserção de registros
Índices
A finalidade é permitir a rápida determinação
do endereço de um registro do arquivo, dado
um argumento de pesquisa
 Vantagem: Cada entrada do índice ocupa um
espaço bem menor do que aquele ocupado
pelos dados
 Pesquisa mais rápida

Número
Nome
1
1000
Ana
30
1000
4
2
1050
Bruno
35
2000
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
NUMERO
ENDERECO
1075
1
1350
1480
Índice
Primário
Idade Salário
Área de Extensão
A área de extensão contém os registros
inseridos
 Usada porque é inviável implementar a
operação de inserção como nos arquivos
seqüenciais (alteração total dos índices)
 Principal alternativa: destinar em cada
registro da área principal um campo “elo”
para um endereço da área de extensão

Acesso a um registro

Acesso serial:
– sem usar o índice, como em arquivo seqüencial
– cuidado com as áreas de extensão

Acesso aleatório:
– O argumento de pesquisa define o
caminhamento sobre o índice
Inserção de um registro

Realiza uma busca no arquivo por meio do
índice

Inserção do registro na lista de extensão do
seu antecessor na área principal, conforme a
figura
NUMERO
ENDERECO
1075
1
1350
4
1480
7
Índice
Primário
Registro a ser inserido
1025 Jamanta
Zacarias
1000
Ø
1310
Bela
1600
1030
1800
Número
Nome
1
1000
Ana
1000
2
1050
Bruno
2000
Ø
100
Ø
3
1075
Carlos
1500
Ø
4
1300
Elias
1200
Ø
101
5
1325
Fábio
1300
Ø
6
1350
Gilberto
1600
Ø
7
1400
Hilda
1000
Ø
8
1440
Isa
1600
Ø
9
1480
Marcela
1800
Ø
Ø
Ø
Salário Elo
100
1025
Zacarias
1000
102
102
Ø
101
1310
Bela
1600
Ø
102
1030
Jamanta 1800
Área de extensão
Ø
Inserção de um registro
Número
Nome
1
1000
Ana
30
1000
4
2
1050
Bruno
35
2000
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
NUMERO
ENDERECO
1075
1
1350
1480
Índice
Primário
Idade Salário E ?
*
*
*
*
Exclusão de um registro

Implementada com ajuda de um campo de
estado adicional

Nas demais operações, desconsidera-se os
registros marcados como excluídos
Alteração de um registro
Realiza uma busca no arquivo por meio do
índice
 Se não envolver a chave de ordenação

– O registro é lido, seus campos alterados e
novamente gravado na mesma posição

Se envolver a chave de ordenação
– O registro é excluído, após sua leitura, e depois
inserido novamente na posição correspondente
Leitura Exaustiva

Leitura feita sem o uso do índice, de acordo
com a chave de ordenação

Os registros da área de extensão devem ser
acessados também por meio do elo da área
principal
Reorganização do arquivo
Necessidade de acessos freqüentes às áreas de
extensão e desconsideração dos registros excluídos
geram perda de desempenho das operações
 Registros excluídos logicamente ocupam um
espaço considerável
 Leitura exaustiva e transferência de todos os
registros para uma nova área, deixando livre a área
de extensão
 Geração de um novo índice após a transferência
dos dados

Reorganização do arquivo

A reorganização deve ser feita periodicamente,
quando o arquivo não estiver sendo utilizado,
geralmente quando o arquivo de extensão tiver
um certo tamanho
Arquivo Indexado
Ao contrário do arquivo seqüencial indexado,
não há a necessidade de manter os registros
fisicamente ordenados.
 Seqüencialidade física do arquivo cada vez
menos vantajosa em termos de acesso
 Assim, torna-se mais eficiente o uso de arquivo
indexado, não havendo compromisso com a
ordem física do arquivo
 Maior eficiência principalmente nas operações de
inserção, dispensando o uso das áreas de
extensão

Índices
As entradas do índice são ordenadas pelo valor
da chave de acesso, cada uma constituída por um
par (chave, endereço), visando tornar mais
eficiente o processo de busca e o acesso serial ao
arquivo
 Índice Exaustivo: entradas para cada registro do
arquivo
 Índice Seletivo: entradas para um subconjunto
dos registros

Índices
NÚMERO
ENDERECO
1000
4
Número
Nome
Idade Salário
1
1400
Isa
25
1600
2
1325
Hilda
24
1000
3
1350
Ana
30
1000
4
1000
Carlos
27
1500
5
1480
Bruno
35
2000
1050
6
1075
7
1300
9
1325
2
1350
3
6
1050
Marcela
23
1800
1400
1
7
1075
Gilberto
31
1600
1480
5
8
1300
Fábio
26
1300
9
Índice
Exaustivo
Índices
Sem um índice exaustivo, é necessária uma
tabela de alocação para indicar os espaços
alocados para o arquivo
 Desvantagens: necessidade de atualização de
todos os índices quando um registro é inserido ou
alterado em alguns casos, ao contrário dos
arquivos seqüenciais indexados

Acesso a um registro

Acesso serial:
– Feito através dos índices, pois as entradas do índice
são ordenadas pelo valor da chave de acesso.
– Geralmente o bloco do índice que contém a próxima
entrada já está na memória, por ser o mesmo da
última acessada, requerendo-se apenas uma leitura
do disco

Acesso aleatório:
– Busca-se o argumento de pesquisa num índice, para
obtenção do endereço desejado
Inserção de um registro
O registro é armazenado em qualquer endereço
vago dentro da área alocada para o arquivo
 Seus pares (chave, endereço) são inseridos nos
índices correspondentes
 Para um índice seletivo, é necessária uma
verificação prévia

Exclusão de um registro

É liberada a área de dados ocupadas pelo
registro (o registro é excluído fisicamente) e
são removidas as entradas do índice
correspondente
Alteração de um registro
Se houver um argumento de pesquisa, o endereço
do registro é determinado por uma busca sobre o
índice; senão, o endereço deve ser conhecido
 Se não aumentar o comprimento do registro, os
campos são alterados e gravados na mesma
posição, atualizando-se apenas o índice; senão a
alteração é implementada pela exclusão e posterior
inserção do registro

Leitura Exaustiva
Se existir pelo menos um índice exaustivo, esta
operação pode ser efetuada por meio de
sucessivos acessos seriais
 Caso contrário, ela só é possível com a
manutenção de uma tabela de alocação, contendo
todos os endereços ocupados

Reorganização do arquivo

Geralmente não é exigida pelos arquivos
indexados, porque os espaços liberados
pelas exclusões dos registros são
reutilizados nas operações de inserção
UFPA – UNIVERSIDADE FEDERAL DO PARÁ
Centro de Ciências Exatas e Naturais
Departamento de Informática
Bacharelado em Ciência da Computação
Estrutura de Dados II
Prof.: Antonio B. C. Sampaio
Conceitos Básicos de Organização de Arquivos
Parte 2
• Equipe:
• Leandro Lages de C. Faria
• Rodrigo Pinto Cardoso
nº 9908801201
nº 9908801401
Arquivo Direto
Consiste na instalação dos registros em
determinados endereços, baseados no valor de
uma chave primária (ao contrário do arquivo
indexado)
 Utiliza uma função que calcula o endereço de um
registro, eliminando a necessidade de um índice
 Objetivo principal é o mesmo do arquivo
indexado, que é obter acesso aleatório eficiente
 Outra diferença: acesso serial não previsto

Cálculo 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 determinísticas: associam um único valor da
chave de acesso a cada endereço. Ex.: F(C)= x+1
– Funções não-determinísticas (ou probabilísticas):
geram para cada valor da chave de acesso um
endereço com a maior unicidade possível.
Ex.: F(C)= x mod 4
Número
Nome
Idade Salário
Elo
1
1000
Ana
30
1000
7
2
1075
Bruno
35
2000
Ø
3
1100
Carlos
27
1500
Ø
4
1300
Elias
24
1200
6
5
1400
Fábio
26
1300
Ø
6
1350
Gilberto
31
1600
Ø
7
1050
Hilda
24
1000
Ø
8
1440
Isa
25
1600
Ø
9
1480
Marcela
23
1800
Ø
Cálculo dos endereços associados ao campo NÚMERO
com a função F(C)=[(C-900)/61]+1
Tratamento de colisões
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 Aberto e
Encadeamento Puro

Tratamento por Endereçamento Aberto
Ao ocorrer colisão, é feita uma busca no
arquivo para localizar um endereço livre.
 Essa busca pode ser feita de três maneiras:
Pesquisa seqüencial, Pesquisa no bloco e
Realeatorização

Tratamento por Encadeamento Puro

Todos os registros que colidem em um endereço
são juntados numa lista encadeada associada
àquele endereço
Acesso a um registro
Acesso serial: feito com o uso de uma função
que preserve a ordem dos registros. Senão, é
necessário se conhecer o valor da chave do
próximo registro
 Acesso aleatório: feito pela aplicação da função
de cálculo de endereço ao argumento de
pesquisa C, sendo obtido o endereço E = F(C)

Inserção de um registro
A função F, de cálculo de endereço, é aplicada à
chave C do registro a ser inserido, resultando o
endereço E = F(C)
 Se houver colisões, utiliza-se um dos métodos de
tratamento de colisão citados anteriormente

Exclusão de um registro

O registro é acessado e, se necessário, é colocado
o valor “excluído” no seu campo de estado

Caso esteja encadeado em alguma lista de colisão,
pode ser removido dela (ou não!), de acordo com
a implementação
Alteração de um registro
Se a alteração não mudar o valor da chave de
acesso nem aumentar o comprimento do
registro, este é simplesmente lido, alterado e
gravado no mesmo endereço
 Caso contrário, o registro é excluído, alterado e
novamente inserido, de acordo com a operação
de inserção em arquivos diretos

Leitura Exaustiva dos registros
Efetivada pela aplicação sucessiva da operação de
acesso a um registro, usando como argumento de
pesquisa cada valor da chave de acesso presente
no arquivo
 Caso seja usada uma leitura serial, esta só será
possível se for usada uma função de cálculo de
endereço que preserve ordem dos registros pelo
valor da chave de acesso

Reorganização do arquivo
Melhor eficiência de acesso
 Feita com o intuito de agrupar registros de
cada lista em posições próximas
 A remoção dos registros excluídos é feita
nessa operação, se já não tiver sido feita

Arquivo Invertido
Mudança nos papéis de registro e campos
 Uso da chave secundária
 Serã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
invertida

Estrutura de um Arquivo Invertido
Generalização do conceito de arquivo
indexado, para acesso por meio de chaves
secundárias.
 As técnicas usuais de organização de
índices são válidas também, sendo que a
cada valor da chave é associado o conjunto
de endereços dos registros que possuem
aquele valor

Idade
Endereços
21
1
4
7
23
2
6
9
25
3
8
26
5
Salário
Chaves
2500
1050
3000
1800
2400
3500
1100
1200
4000
1250
1950
7000
1850
2000
Chave
Nome
Idade
Salário
1
1050
Ademar
21
2500
2
1200
Iara
23
3500
3
2400
Marcos
25
3000
4
1850
Tatiana
21
7000
5
6
1100
Pedro
26
3500
1250
Enio
23
4000
7
2000
Sandra
21
4000
8
9
1800
Claudia
25
3000
1950
Ivan
23
4000
Operações
Inserções e exclusões em lista invertidas
ocorrem sempre como uma conseqüência de
modificações pelo arquivo de dados
associado.
 Operação de acesso: é a mais interessante
em relação a este tipo de arquivo, por
possuir alternativas e características
próprias para isto.

Acesso ao Arquivo
Quais os nomes dos funcionários que
possuem idade igual a 21?
 Quais os nomes dos funcionários que
possuem idade igual a 23 e salário de 4000?
 Quais os nomes dos funcionários que
possuem idade igual a 23 ou salário de
4000?
 Quais as chaves dos funcionários com
salário entre 2500 e 3500?

Conclusões
Suporte a acessos associativos (por valor)
aos dados.
 Usado em banco de dados relacionais
 Arquivos Multilistas.
 Pode-se dizer que os dois são equivalentes,
diferindo apenas na forma pela qual são
indicados os grupos de registros que
possuem o mesmo valor num campo.

Vantagens e Desvantagens de
cada Tipo de Arquivo
VANTAGENS
Seqüencial
Seqüencial
Indexado
DESVANTAGENS
Registros dispostos ordenada- Não acomoda com simplicidamente
(acessos
e
buscas de as operações de modificação
Necessita de um arquivo de
seqüenciais mais eficientes)
transações, que precisa ser
reorganizado periodicamente
Registros dispostos ordena- Necessita de áreas de extensão
damente
As áreas de extensão precisam
Utiliza índices, que são mais ser reorganizadas periodicaeficientes do que os métodos do mente, para evitar possíveis
perdas de desempenho
Arq. Seqüencial de localização de
Novo índice deve ser gerado se
registros
houver mudança de endereço de
Os índices não precisam ser registros ou de atributos
atualizados
associados a ele
VANTAGENS
Não
Indexado
Direto
Invertido
há necessidade dos registros
ficarem ordenados, pois se
utilizam índices
Não existem áreas de extensão
Logo, há maior flexibilidade nas
operações de modificação
Reorganizações não são exigidas
Não há necessidade de se percorrer um índice
Acesso aleatório eficiente, calculando-se endereços de registros
através de uma função
DESVANTAGENS
Novo
índice deve ser gerado
se houver mudança de endereço
de registros ou de atributos
associados ao índice
Determinar
funções que gerem
endereços com o maior grau de
unicidade possível
Uso de funções ñ-determinísticas para se obter endereços do
arquivo pode causar colisões
Acesso direto ao registro após As listas invertidas valem
sua localização na lista invertida apenas para aquela disposição
física do arquivo
Nova inversão deve ser gerada
se houver mudança de endereço
de registros
Perguntas
1) Qual é a diferença entre o acesso aleatório e o
2)
3)
4)
5)
acesso seqüencial?
Explique sucintamente a operação de inserção em
Arquivos Seqüenciais.
Para que servem as áreas de extensão em
Arquivos Seqüenciais Indexados?
Cite uma vantagem do Arquivo Seqüencial
Indexado sobre Arquivo Seqüencial.
Qual a vantagem e desvantagem no uso de
Arquivos Indexados?
6) Como são determinados os endereços dos
registros em Arquivos Diretos?
7) Para que servem os métodos de
Tratamento de Colisão? Cite alguns deles.
8) Em que consiste o uso de Arquivos
Invertidos?