Conservativos (dados não desaparecem qdo. desligamos máquina)
Desvantagens
Acesso comparativamente muito lento
Alteração/Inclusão de dados às vezes ainda
mais lenta.
Dispositivos de Acesso Seqüencial
Exemplo típico: Fita
Extremamente lentos.
Utilizados para:
armazenar dados que vão ser acessados todos de uma só vez
e
não vão mais ser alterados.
Uso típico: Backup
Gerência de arquivos não se ocupa muito destes
dispositivos.
Dispositivos de Acesso Randômico/Aleatório
Exemplo típico: Disco
Relativamente rápidos
Utilizados para:
Dados que sofrem freqüêntes pesquisas
Dados muito alterados ou não definitivos
Uso típico: área de trabalho ou banco de dados
Base para as técnicas que serão vistas.
Noção Intuitiva
Usamos RAM para armazenar dados temporariamente enquanto estamos processando-os.
Usamos dispositivos de armazenamento secundário para guardar dados
não processados e dados depois de processados.
Solução Intuitiva: Um programa carrega todos os dados
que necessita em uma estrutura de dados na memória, os processa
completamente e depois os escreve de volta.
Problemas:
Dados podem não caber na mémoria.
Ler e depois reescrever todos os dados de um conjunto toma muito tempo.
Pode ser que estejamos interessados em processar somente uma pequena fração
do conjunto.
Objetivo Principal
Solução para o problema da leitura/escrita
de todos os dados:
trabalhamos com os dados organizados em arquivos.
só trazemos para a memória dados que queremos alterar
só escrevemos em disco novos dados que queremos incluir
só retiramos do disco dados que queremos eliminar.
Fator mais restritivo: o tempo de acesso aos dados
organizamos os arquivos de forma a minimizar o tempo de acesso aos dados
eficiência na organização tem prioridade maior que
economia de espaço (pode ser desperdiçado moderadamente)
Motto Básico
Organizamos os dados de forma a minimizar
o número de acessos à memória secundária
para executar uma operação (procura, inserção,
alteração, deleção).
Para isto utilizamos:
organizações de dados mais rígidas de que na memória
(mesmo que isso signifique desperdício de espaço)
técnicas de indexação
algoritmos de busca
Disco
Exemplo típico para uma memória secundária de acesso
aleatório.
Compreender a forma de armazenamento é importante.
Modelo de estruturação do disco serve para todos os outros
meios secundários.
Modelo Simplificado
Dados são organizados em superfícies, trilhas e setores,
blocos.
Um arquivo pode ser imaginado como sendo constituído por uma seqüência
de dados no disco.
Acesso é feito através do posicionamento de um cabeçotes
de r/w em qualquer ponto.
Uma unidade de alocação do disco (um bloco ou um setor) possui
um endereço físico no disco.
Podemos endereçar estes da mesma forma que fazemos com a RAM
Modelo mais Realista
O disco pode apresentar fragmentação: i.é., os dados
não estão exatamente em espaços contíguos,
mas em unidades de alocação longe umas das outras, encadeadas
como uma lista.
O encadeamento é tarefa do sist.op. e do hardware do disco.
Para Trabalhar
Tudo o que precisamos para trabalhar com técnicas
de gerência de arquivos é imaginar:
que um arquivo é uma seqüência de dados sem buracos meio.
que podemos acessar qualquer parte deses dados através de seu endereço
relativo (a partir do início).
que só podemos incluir um dados novos no fim
dados do meio só podem ser alterados.
Apagar um dado significa marcá- lo como apagado ou substituí-lo
por outro
Tipos de Arquivos
Há basicamente dois tipos de arquivos,
olhados do ponto de vista do armazenamento de informação:
Arquivos de Formato Variável
Arquivos de Registros
Arquivos de formato variável
São arquivos onde a única unidade de endereçamento
possível é o byte.
Os arquivos não são organizados em estruturas. Exemplo típico:
arquivos texto.
Mesmo sendo os arquivos texto organizados em linhas, estas têm tamanho
variável e não servem para endereçar o arquivo, i.é.,
você não sabe a que distância do começo do arquivo
a "linha 13" está.
São tratados como arquivos de acesso seqüencial.
Arquivos de Registros ou de Acesso Randômico
São arquivos organizados em unidades (maiores que 1 byte) de tamanho
sempre igual, chamadas registros.
Registros têm a mesma filosofia que as structs em C ou records em
Pascal.
São conjuntos de dados com tamanho fixo, mesmo que uma parte não
seja aproveitada.
Permitem que sejam usados como unidade de endereçamento relativa.
Ex.: Registro 34278
Ex.: Podemos armazenar um nodo de uma árvore como um registro. O
ponteiro "direita" apontará para o endereço relativo de um
registro representando outro nodo no arquivo.
Técnicas de Gerência de Arquivos são voltadas aos Arquivos
de Registros.
Acesso a Registros
Quase todas as linguagens de programação provêm uma
facilidade para o acesso a arquivos de endereçamento randômico.
Ex.: Comando seek( arquivo, posição) em Pascal.
O acesso é feito simplesmente fornecendo-se
o endereço relativo (número de registro).
O resto (encontrar a trilha e o setor, posicionar
o cabeçote, etc) é incumbência do sist. operacional
e do hardware do dispositivo e é transparente ao programador/usuário.
Feito o acesso pode-se realizar uma operação
de leitura ou escrita.
Definições
Registro
Elemento básico de um arquivo de acesso randômico.
Todos os registros de um arquivo têm geralmente o mesmo tamanho.
Ítem
de Dados
É o campo de um registro.
Ocorrência
É uma instância de um registro com determinados
valores.
Organização
Física
A forma de organização de de um arquivo, sua
estrutura (de dados e de índices). Contrapartida ao conceito de
Estrutura de Dados.
Escolha da Organização
de Arquivos
Principal Objetivo:
Fornecer caminhos de acesso aos registros durante as operações
de recuperação e atualização de dados.
Critérios:
Consultas sempre envolvem buscas. Os caminhos de acesso aos registros devem
tornar essas buscas o mais eficientes possível.
Depende:
Tipos de consultas permitidas
Número de chaves (só uma ou chaves secundárias)
Ex.: Vamos indexar uma lista telefônica só por nome ou
também por rua ou número
Modos de recuperação e de atualização.
Tipos de Consulta
empregado : registro {
nome : string
cargo : string
salário : inteiro
dataBase : tipoData
endereço : string
}
Consulta simples: cargo = motorista
Consulta em uma faixa: salário > 560
Consulta booleana:
cargo = motorista E salário > 300 E dataBase = 15
Indexação
Podemos usar um campo de uma estrutura de registro para identificar
esse registro. Chamamos a este campo de chave.
Índice é uma estrutura
de dados que mantém o conjunto de chaves de um arquivo e seus endereços
e serve de referência para os registros.
Índice Primário (ou Indexação
por Chave Primária) é um índice único que organiza
o arquivo através do campo considerado mais importante" ou "identificador"
da sua definição de registros. Ex.: "empregado" por nome.
Índice Secundário (ou
Indexação por Chave Secundária) é um índice
que organiza o arquivo referenciando outro campo ou combinação
de campos. Ex.: Indexamos "empregado" por nome e por data-base.
Data-base é um índice secundário.
Métodos de Gerência/Organização
Arquivos Seqüenciais
Primária
Arquivos Indexados Seqüenciais
Primária
Árvores
AVL, B
Primária
K-D
Primária, Secundária
Listas (Primária e Secundária)
Multilista
Arquivo Invertido
Arquivos Seqüenciais
Um registro está atrás do outro.
Leitura é realizada seqüencialmente
Escrita só no final.
Indexação: Ordenação
por Chave Primária
Indexação Primária: Podemos
ordenar o arquivo pelo campo chave. Semelhante à lista ordenada
em um vetor.
Vantagem: Acesso seqüencial de um conjunto
de dados é o mais rápido.
Útil qdo. sempre tenho de processar quase
todos os elementos.
Desvantagens: Inclusão e Exclusão
é extremamente custosa.
2 soluções:
Cópia
Inclusão/Exclusão com o algoritmo da lista ordenada em vetor
Exemplo: Inclusão em Arquivo Seqüencial
com Chave
Arquivos Indexados Seqüenciais
Arquivos Seqüenciais passíveis de serem acessados através
de tabelas de índices.
Exemplo mais típico: ISAM (IBM).
Indexed Sequential Access Method
Mais utilizado método de gerência de arquivos durante muito
tempo.
Suportado por linguagens de programação MUITO velhas como
COBOL ou PL/1.
Existia como Pacote de Software disponível inicialmente só
para mainframes (Ex.: IBM 4341 e linha 370).
Mais tarde passou a existir também para PCs sobb DOS.
Arquivos Indexados Seqüenciais: Características
Arquivo ordenado por chave primária
Tabela de índices também ordenada por chave primária
é usada para acessar áreas do arquivo.
Originalmente essa tabela ficava no começo do próprio arquivo.
Pode ser implementada como um arquivo separado.
Tabela de índices pode ter vários níveis (índice
hierárquico).
Inserções são realizadas na área de
overflow ou área de espaço livre. Também indexada
na tabela.
Deleções somente são marcadas.
Atualização periódica através de cópia
do arquivo.
