Disponível somente no TrabalhosFeitos 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...
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...
Ler documento completo
Por favor, assinar para o acesso.