Conceitos Básicos de Organização de Arquivos

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.

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

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

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

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

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.

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.

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:

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.

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

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.

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.

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

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.

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

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.

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