Aula 05 - Conceitos Básicos de Organização de Arquivos


Equipe:
Leandro Lages -  leandrolages@bol.com.br 
Rodrigo Cardoso - rp.c@mailbr.com.br


Objetivo da Aula:
Apresentar ao aprendiz os principais conceitos e terminologias utilizados na organização de arquivos, além de introduzir conceitos e diferenças entre arquivos seqüenciais, arquivos seqüenciais indexados, arquivos indexados, arquivos diretos e arquivos invertidos.


Manual de Referência Eletrônica
- Download da apresentação em ppt


Atividades da Aula:
1. Introdução
2. Terminologia
3. Introdução aos Arquivos Seqüenciais
4. Introdução aos Arquivos Seqüenciais Indexados
5. Introdução aos Arquivos Indexados
6. Introdução aos Arquivos Diretos
7. Introdução aos Arquivos Invertidos
8. Quadro Comparativo entre as Organização de Arquivos
9. Exercícios


1. Introdução

O armazenamento de pequenos volumes de dados, via de regra, não encerra grandes problemas no que diz respeito à distribuição dos registros dentro de um arquivo, desde que a freqüência de acessos aleatórios a registros não seja muito elevada.

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 a sofisticação das técnicas de armazenamento e recuperação de dados uma conseqüência da necessidade de acesso rápido a registros pertencentes a grandes arquivos ou, simplesmente, arquivos muito solicitados.

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. Esta ordem pode ser, por 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.

A seguir, após a apresentação da terminologia usada neste capítulo, são apresentadas introduções sobre quatro estratégias de organização de arquivos voltadas para o acesso por meio de chaves primárias, que são Arquivo Seqüencial, Arquivo Seqüencial Indexado, Arquivo Indexado, Arquivo Direto, e uma, Arquivo Invertido, voltada para acesso por meio de chaves secundárias. << topo

2. Terminologia

Um arquivo é formado por uma coleção de registros lógicos, cada um deles representando um objeto ou entidade.

Um registro lógico, ou simplesmente registro, é formado por uma seqüência de itens, sendo cada item chamado campo ou 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.

O armazenamento de um arquivo é feito, via de regra, por blocos de registros 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 seqüê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, 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.

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. << topo

3. Introdução aos Arquivos Seqüenciais

Em um arquivo seqüencial, os registro são dispostos ordenadamente, obedecendo a seqüência determinada por uma chave primária, chamada chave de ordenação. Na figura abaixo, é apresentado um exemplo de arquivo seqüencial, no qual é usado como chave de ordenação o atributo NÚMERO.

NÚMERO NOME IDADE SALÁRIO
100 Pedro 23 1000
150 Leandro 20 500
200 Rodrigo 19 270
250 Maria 30 5000
300 Celso 27 2500
350 Ana 42 9000
400 João 22 2100
450 Gisele 23 1300
500 Jack 21 800
550 Sandra 24 2400

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.

As operações nos arquivos seqüenciais, bem como nas demais organizações, serão vistas nas próximas aulas. << topo

4. Introdução aos Arquivos Seqüenciais Indexados

Quando em um arquivo seqüencial o volume de acessos aleatórios torna-se muito grande, configura-se a necessidade de 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 do que os métodos vistos para arquivos seqüenciais.

Um arquivo seqüencial, acrescido em um í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.

Além do arquivo seqüencial e do í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.

- Índices

A finalidade de um índice é permitir rápida determinação do endereço de um registro do 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. Com isto a pesquisa sobre o índice pode ser feito 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.

Veja a figura abaixo, que apresenta o arquivo seqüencial indexado:

NÚMERO ENDEREÇO
100 1
150 2
200 3
250 4
300 5
|---------ÍNDICE---------|
  NÚMERO NOME SALÁRIO
1 100 PEDRO 3000
2 150 JOÃO 1500
3 200 MARIA 2500
4 250 CARLA 3000
5 300 MAX 2000
 |-----------ÁREA DE DADOS NO DISCO------------|

- Áreas de Extensão

A área de 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 que nos arquivos seqüenciais. 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 seqüencial 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, conforme a figura:

NÚMERO ENDEREÇO
100 1
150 2
175 2
200 3
250 4
275 4
300 5
|---------ÍNDICE---------|
  NÚMERO NOME ELO
1 100 PEDRO -
2 150 JOÃO 10
3 200 MARIA -
4 250 CARLA 20
5 300 MAX -
 |-----------ÁREA DE DADOS NO DISCO------------|
  NÚMERO NOME ELO
10 175 BILL -
20 275 NARA -
30      -
40        -
50       -
|----------------ÁREA DE EXTENSÃO----------------|

<< topo

5. Introdução aos Arquivos Indexados

Nos arquivos seqüenciais indexados, o compromisso de manter os registros fisicamente ordenados pelo valor da chave de ordenação, com o objetivo de prover um acesso serial eficiente, acarreta uma série de problemas, principalmente no que diz respeito à operação de inserção de um registro, conduzindo à necessidade de utilização de áreas de extensão e efetivação de reorganizações periódicas.

À medida que decresce a freqüência de acessos seriais, relativamente à freqüência de acessos aleatórios, a manutenção da seqüencialidade física do arquivo encontra uma compensação cada vez menor em termos de eficiência de acesso, até tornar-se antieconômica.

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 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. 

Veja a figura abaixo, que apresenta o indexado:

NÚMERO ENDEREÇO
100 4
150 3
200 1
250 5
300 2
|---------ÍNDICE---------|
  NÚMERO NOME SALÁRIO
1 200 PAULO 3100
2 300 JOSÉ 4500
3 150 MARIA 2500
4 100 MARISA 5000
5 250 FABIO 2500
 |-----------ÁREA DE DADOS NO DISCO------------|

- Índices

Em um arquivo indexado, podem existir tantos índices quantas forem as chaves de acesso aos registros. Um í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 seqüencialidade física das entradas no índice visa a tornar mais eficiente o processo de busca e permitir o acesso serial ao arquivo.

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.

O maior problema relacionado com a utilização de arquivos indexados diz respeito à necessidade de atualização de todos os í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 seqüenciais 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. << topo

6. Introdução aos Arquivos Diretos

A idéia básica de um arquivo direto consiste na instalação dos registros em endereços determinados com base no valor de uma chave primá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 de acesso aleatório eficiente. Em um arquivo direto, aos invés do índice é usada uma função que calcula o endereço do registro a partir do argumento de pesquisa.

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 idéia básica.

Veja a figura abaixo, que apresenta o arquivo direto:

chave: 150--->

E=F(chave)

---> E = 3

 |-------->

                                                            
  NÚMERO NOME SALÁRIO
1 200 PAULO 3100
2      
3 150 MARIA 2500
4      
5 250 FABIO 2500
 |-----------ÁREA DE DADOS NO DISCO------------|

- Cálculo de Endereços

O primeiro problema com os arquivos diretos é o da determinação de uma função F, que transforme o valor da chave C de um registro no endereço E que lhe corresponde no arquivo.

Podemos considerar dois tipos de funções, sendo o primeiro constituído pelas funções determinísticas, as quais associam um único valor da chave de acesso a cada endereço. Este tipo de função apresenta vantagens evidentes; no entanto, é impossível, em termos práticos, encontrar uma função determinísticas simples para um grande número de registros. Aquelas que poderiam ser usadas seriam tão complexas que eliminariam as vantagens do acesso direto, além de necessitarem adaptações a cada inserção sofrida pelo arquivo. Não têm, portanto, maior interesse prático.

O segundo tipo é formado pelas funções probabilísticas, as quais geram para cada valor da chave um endereço "tão único quanto possível", podendo gerar, para valores distintos de chave, o mesmo endereço, fato este que é denominado colisão.

- Tratamento das Colisões

Um dos aspectos mais importantes na organização de arquivos diretos diz respeito ao problema das colisões, que é uma conseqüência do uso de funções não determinísticas para a transformação dos valores da chave de acesso em endereços do arquivo.

Para se tratar as colisões, as soluções mais freqüentes usadas são Endereçamento Aberto com Pesquisa Seqüencial e Encadeamento. A primeira 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 seqüencial, ou seja, se o endereço E gerado pela chave estiver ocupado, o próximo a ser consultado será o endereço E + 1, E + 2,...,M,1,1,...,E - 1 até se encontrar um lugar vago para armazenar o registro.

Na segunda solução,  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. As duas estratégias mais usadas são a utilização de áreas de extensão e encadeamento puro. << topo

7. Introdução aos 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.

As técnicas usuais na organização de índices são válidas também para este caso, 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. Na figura abaixo, é representado um arquivo invertido com duas inversões associadas à chave secundária IDADE, uma contendo os ENDEREÇOS e outra NÚMEROS.

IDADE ENDEREÇOS
20 2 8 9
22 1 5  
23 4    
25 6 10  
27 3 7  

 
  NÚMERO NOME IDADE
1 350 PEDRO 22
2 200 GISA 20
3 150 MAX 27
4 250 SANDRA 23
5 400 PAULO 22
6 600 CARLA 25
7 450 ROBSON 27
8 300 CELSO 20
9 100 RENATA 20
10 550 LEANDRO 25
 
IDADE NÚMEROS
20 200 300 100
22 350 400  
23 250    
25 600 550  
27 150 450  

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.

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, havendo, no entanto, 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. << topo

8. Quadro Comparativo entre as Organização de Arquivos

Eis um quadro comparativo, que lista as vantagens e desvantagens das várias organizações de arquivos.

Arquivo Vantagens Desvantagens
Seqüencial - Acessos seqüenciais mais eficientes. - Operações de modificações não são simples.
Seqüencial Indexado -Utilizam índices, que agilizam a consulta por estarem na RAM. - Necessidades de áreas de extensão, que precisam ser reorganizadas.
Indexado -Não existem áreas de extensão
- Registros sem compromisso com armazenamento físico.
- Atualização do índice quando da inserção de um registro.
Direto -Acesso direto, sem necessidade do índice. - Determinar funções que gerem menor número de colisões
Invertido - Acesso direto ao registro após localização da lista invertida. - As listas invertidas valem apenas para aquela disposição física do arquivo.

9. Exercícios

Após ter estudado a introdução das organizações de arquivos, faça os exercícios do assunto clicando aqui.
<< topo

 

voltar