Fundamentos de arquivos

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1587 palavras )
  • Download(s) : 0
  • Publicado : 10 de maio de 2012
Ler documento completo
Amostra do texto
Fundamentos de Arquivos
SCC203 – Algoritmos e Estruturas de Dados II

Arquivos


Informação mantida em memória
secundária







HD
Disquetes
Fitas magnéticas
CD
DVD

2

Discos X Memória Principal


Tempo de acesso


HD: ~ microsegundos s (10-6)



RAM: ~ nanosegundos s (10-9)



HDs são centenas – e até milhares – de vezes
mais lentos quememória RAM

3

Discos X Memória Principal


Exemplo:




O acesso à RAM equivale a buscar uma
informação no índice de um livro que está em
suas mãos
O acesso a disco seria equivalente a mandar
buscar a mesma informação em uma biblioteca

4

Discos X Memória Principal


Capacidade de Armazenamento





HD – muito alta, a um custo relativamente baixo
RAM – limitadapelo custo e espaço

Tipo de Armazenamento



HD – não volátil
RAM – volátil

5

Discos X Memória Principal


Em resumo




Então






acesso a disco é muito caro, isto é, lento!

o número de acessos ao disco deve ser
minimizado
a quantidade de informações recuperadas em um
acesso deve ser maximizada

Estruturas de organização de informação em
arquivos6

Organização de Arquivos


Meta: minimizar as desvantagens do uso da
memória externa




Minimizar o tempo de acesso ao dispositivo de
armazenamento externo

De forma independente da tecnologia
Tempo de Acesso = nro. de acessos * tempo de 1 acesso

7

Discos X Memória Principal




Estruturas de dados eficientes em memória
principal são inviáveis em disco
Seriafácil obter uma estrutura de dados
adequada para disco se os arquivos fossem
estáveis (não sofressem alterações)


Solução: organização adequada de arquivos no
disco, e de informações em arquivos
8

Discos X Memória Principal




O ideal é que a informação necessária possa ser
obtida com apenas 1 acesso a disco.
 Se o ideal não pode ser atingido, deseja-se chegar
o mais próximopossível.
Por exemplo, o método de busca binária permite que
um registro pesquisado entre 50.000 seja encontrado
em no máximo 16 comparações (log250.000 ~ 16)
.... mas acessar o disco 16 vezes para buscar uma
informação é tempo demais. Precisamos de
estruturas que permitam recuperar esse mesmo
registro em dois ou três acessos!
9

Discos X Memória Principal




Queremosestruturas que agrupem informações de
modo a permitir que toda (ou quase toda) a
informação necessária seja obtida, idealmente, em
uma única operação de acesso a disco
Por exemplo, se precisamos do nome, endereço,
telefone, saldo, número da conta, etc. de um certo
cliente, é preferível obter toda essa informação de
uma só vez ao invés de ficar procurando em vários
lugares...

10

Discos XMemória Principal


História - Cronologia









Dados em fitas com acesso sequencial
Arquivos cresceram demais e o acesso sequencial
ficou proibitivo
Uso de índices que, com o crescimento dos
arquivos, também ficam ineficientes
Uso de árvores para apontar para os arquivos,
mas árvores crescem de maneira desigual
AVLs







Qual a dificuldade?

Árvores B eárvores B+
Hashing seria uma boa opção, mas arquivos não
são estáveis
Hashing dinâmico
11

Arquivo Físico e Arquivo Lógico






Arquivo Físico: sequência de bytes
armazenada no disco
Arquivo Lógico: arquivo como visto pelo
aplicativo que o acessa
Associação arquivo físico – arquivo
lógico: iniciada pelo aplicativo, gerenciada
pelo S.O.
12

Arquivo Físico e Arquivo Lógico


Arquivo Físico: conjunto de bytes no disco,
geralmente agrupados em setores de dados.
Gerenciado pelo sistema operacional

Arquivo Lógico: modo como a linguagem
de programação enxerga os dados. Uma
sequência de bytes, eventualmente
organizados em registros ou outra estrutura
lógica.
13

Arquivo Físico e Arquivo Lógico


Arquivo lógico é como usar um telefone para
se...
tracking img