ESTRUTURA DE DADOS: APOSTILA
Autora: Adriana Raposo
Organização de Arquivos
Quando se cria ou se projeta um arquivo de dados é de máxima importância, a análise da
filosofia de trabalho que motivou a sua criação e do suporte a ser utilizado, para que se determine
o tipo de organização mais adequado para seus registros. Quanto à organização, o arquivo
poderá ser:
• Serial;
• Seqüencial;
• Seqüencial-indexado;
• Direto;
• Indexado.
1. Organização Serial
Pela organização serial, os registros são armazenados de acordo com a ordem de
inserção, sem nenhum compromisso com qualquer ordenação.
O acesso a tais registros se dá pela PESQUISA SERIAL, desde o primeiro registro até
encontrar o registro desejado.
2. Organização Seqüencial
Nos arquivos que utilizam esta organização, os registros são gravados em ordem
seqüencial (ocupam posições contíguas de memória), por suas respectivas chaves (primárias),
havendo, pois, uma perfeita ordenação, tanto lógica quanto física. A chave de cada registro é um
atributo comum a todos eles e, em princípio, capaz de individualizar cada um; o nome, por
exemplo, não é uma chave ideal no cadastro de uma empresa, tendo em vista a possibilidade de
homônimos; já o número de matrícula apresenta-se como excelente atributo para esse fim.
Se, em um arquivo seqüencial, não se elege qualquer atributo como chave, os registros
são arquivados simplesmente de acordo com sua ordem de chegada.
As figuras abaixo dão a idéia da disposição dos registros de um arquivo seqüencial
armazenado em uma fita magnética:
IRG
01 Ivan
IRG
03 Mônica
IRG
Registro Físico = Registro Lógico
04 Silvio
IRG
05 Tiago
Fator de Bloco = 1
Registro Lógico
IRG
01 Flávio
02 Roberto
Registro Físico
03 Filipe
IRG
05 Ana
IRG
06 Paulo
Fator de Bloco = 3
Pelas figuras, vê-se que intervalos entre os registros, denominados IRG (Inter Record
Gap); esses intervalos visam a que os dispositivos de leitura e gravação tenham oportunidade de
algumas ações mecânicas entre a leitura e/ou gravação propriamente dita, como, por exemplo,
aceleração ou desaceleração da fita magnética.
O computador só pode acessar um registro de cada vez, a partir do primeiro.
A principal vantagem do arquivo seqüencial é o rápido acesso a registros, quando a grande
maioria deles tem que ser pesquisada seja em tarefas de mera consulta ou em trabalhos de
atualização.
2
Ele poderá estar armazenado em veículos de acesso seqüencial (fita magnética) ou de
acesso direto (disco ou tambor magnético). Neste último caso, a consulta em um registro é feita
través do processo denominado PESQUISA BINÁRIA; é lido inicialmente o registro desejado; em
seguida, lê-se o registro central dessa metade e, assim sucessivamente, até que, diante de um
segmento relativamente curto de arquivo, é feita uma busca seqüencial.
Quanto à atualização, tendo em vista a necessidade de que seja mantida a ordenação
física dos registros, a operação requer que o arquivo seja copiado, a fim de remover espaços
resultantes das exclusões e, por outro lado, acomodarem-se, em suas devidas posições, os novos
registros incluídos.
Pelo que foi visto, é fácil depreender-se que a organização seqüencial é recomendável
quando uma grande parte dos registros é processada de cada vez. Vê-se, também, que um alto
fator de bloco é desejável em muitos casos dessa organização, uma vez que compensa trazer pra
a memória uma boa quantidade de registros lógicos de cada vez, pelo fato de que a grande
maioria deles, em verdade, deverá ser processada.
A atualização de um arquivo seqüencial é feita pela técnica balance-line, em que um
terceiro arquivo (novo arquivo mestre) é gravado a partir da comparação entre os registros da
versão disponível do arquivo mestre com os registros do arquivo de movimento. O exemplo que
segue dá a idéia do processo.
Seja criar em fita magnética a nova versão de um arquivo mestre onde os registros se
encontram seqüencialmente ordenados por seu código. Naturalmente, o arquivo de movimento
está ordenado pelo mesmo critério. Para facilidade, suponha-se fator de bloco igual a 1.
São lidos inicialmente: o 1º registro do arquivo mestre e o 1º registro do arquivo de
movimento. Suponha-se que a chave do registro lido no arquivo mestre seja 0001 e a chave do
registro de movimento seja 0008. Levados à memória principal esses dois registros, é feita a
comparação; como o registro do arquivo mestre é de ordem mais baixa, o 1º registro do arquivo
mestre é transcrito na nova fita.
Esse procedimento vai-se repetir até que se leia, no arquivo mestre, um registro de chave
igual ou maior que 0008. Suponhamos que se leia o registro de chave 0008; neste caso, os
campos do registro do arquivo mestre são alterados de acordo com a nova versão, ou seja, de
acordo com o que foi lido no arquivo de movimento; em seguida, essa nova versão do registro
0008 é gravada na fita nova.
No caso de se ler no arquivo mestre um registro com chave superior à do arquivo de
movimento, o registro movimento é gravado em fita nova; lê-se, então, novo registro do arquivo de
movimento e continua-se procedendo analogamente, até que o último seja gravado na nova fita.
Essa fita conterá, então a nova versão do arquivo mestre.
Num arquivo seqüencial, não se fazem operações de gravação quando se está lendo, nem
operações de leitura quando se está gravando.
Resumo dos procedimentos em arquivos seqüenciais:
• PESQUISA (ACESSO): consulta-se os registros seqüencialmente (dispositivo de acesso
seqüencial), por blocos (dispositivo de acesso seqüencial) ou por pesquisa binária (dispositivo
de acesso direto).
• INCLUSÃO: copia-se o arquivo até o registro de ordem n (enésimo na ordenação); grava-se o
registro que se quer incluir naquela posição (respeitando-se a seqüência); copia-se o restante
do arquivo; apaga-se o arquivo anterior; renomeia-se o novo arquivo.
• EXCLUSÃO: Arquivo em disco: deleta-se o registro; compacta-se o arquivo. Arquivo em fita:
copia-se o arquivo para um novo suporte (fita ou disco) deixando-se de gravar o registro que se
deseja excluir.
• ATUALIZAÇÃO: Balance-line.
3. Organização Seqüencial-Indexada
Cada registro é acessado de modo direto; logo, a organização não se presta a veículos de
gravação/leitura seqüencial.
Quando se cria um arquivo seqüencial-indexado, ficam reservadas três áreas no veículo de
gravação: uma área denominada principal (ou primária), onde são gravados os registros
propriamente ditos, escalonados pela chave em subáreas; uma área destinada a um índice, que
indica a subárea da área principal onde determinado grupo de registros se encontra gravado; e a
3
terceira área, denominada área de overflow, onde se encontram os registros que não foram
alojados na área principal.
A área principal, também chamada de primária, é definida quando o arquivo é gerado. Ela
é ampliada (caso mais comum) ou reduzida cada vez que o arquivo é reorganizado.
A área de índices é um arquivo seqüencial criado pelo sistema, onde cada registro
estabelece um segmento na área principal, e contém o endereço de início do segmento e a chave
mais alta do mesmo. Assim, o sistema acessa de maneira direta um segmento da área principal a
partir da área de índices, de forma semelhante à procura de um capítulo de um livro a partir de
seu índice.
Por ocasião da reorganização, os registros são mantidos ordenados seqüencialmente
segundo a chave de ordenação, mas inteiramente contidos na área principal, esvaziando-se a
área de overflow (ou área de excedentes).
Subárea 1
Subárea 2
100
200
100
200
Subárea 1
Subárea 2
Subárea N
900
900
Subárea N
ÍNDICES
PRINCIPAL
OVERFLOW
Nas inclusões subseqüentes, novos registros são gravados na área de overflow. Esses
registros são mantidos em listas subordinadas às diversas subáreas da área principal.
Cada registro é, pois, acessado através de um diretório CHAVE-ENDEREÇO (índice).
Em cada subárea da área principal os registros estão logicamente ligados em seqüência,
pelas chaves.
Depreende-se, portanto, que movimentos de atualização de um arquivo seqüencialindexado não implicam a necessidade de regravar todo o arquivo. Porém, após algumas inclusões
torna-se conveniente reorganizar o arquivo a fim de que um crescente aumento da área de
overflow não venha torna-lo menos funcional.
A pesquisa a um registro em arquivo seqüencial-indexado leva o computador a verificar,
pela chave, se o registro está na área principal ou na área de overflow e, em seguida, em que
subárea de uma dessas duas se encontra; localizada a subárea, o registro é buscado
seqüencialmente.
É conveniente ressaltar que a organização de um arquivo seqüencial-indexado pode ser
feita através de um programa especificamente criado para tal fim ou mediante a aplicação de um
SORT baseado na chave do arquivo.
Chave K1
Chave K2
.
.
.
Chave Kn
CHAVES
Chaves
K1,K2
Endereços
A1
K3,Ki
A2
Km,Kn
Aj
ÍNDICES
ENDEREÇOS
4
Esta organização apresenta a vantagem de acesso rápido e, além disso, o sistema se
encarrega de relacionar a posição de cada registro com seu conteúdo através da área de índices.
Também é trabalho do sistema a gerência das áreas de índices e de overflow.
Seus inconvenientes são a necessidade de espaço adicional para a área de índices e o
desperdício de espaço que ocorre ao ficarem espaços intermediários livres após sucessivas
atualizações.
Resumo dos procedimentos em arquivos seqüenciais-indexados:
• PESQUISA (ACESSO): normalmente através do diretório CHAVE-ENDEREÇO (a partir de uma
prévia consulta à área de índices). Em casos em que seja mais prático, a pesquisa também
pode ser feita seqüencialmente: nesse caso, o sistema acessa diretamente a área de dados,
isto é, sem acessar inicialmente a área de índices.
• INCLUSÃO: grava-se o registro; o sistema atualizará os ponteiros: o registro anterior apontará
para o incluído e o registro incluído apontará para o anteriormente apontado. Se for o caso, o
sistema atualizará a área de índices.
• EXCLUSÃO: deleta-se o registro; compacta-se o arquivo. O sistema reorganizará os ponteiros
e, se for o caso, a área de índices.
• ATUALIZAÇÃO: lê-se todo o arquivo, inclusive a área de overflow; ordena-se e grava-se o
arquivo. O sistema reorganizará a área de índices; a área de overflow ficará vazia.
4. Organização Direta ou Aleatória ou Relativa
K1
A1
K2
A2
Kn
An
Nesta organização, as informações são acrescentadas e acessadas aleatoriamente
mediante a sua posição, ou seja, indicando o lugar relativo que ocupam dentro do conjunto de
posições possíveis.
O acesso é mais imediato, uma vez que é feito através de um relacionamento entre a
chave e o endereço do registro.
Os registros são armazenados com base em uma relação de endereços previamente
estabelecidos, onde esses endereços são criados em função de todas as possibilidades de
variação da chave.
Quando o endereço é gravado, apagado, alterado ou, simplesmente, pesquisado, seu
endereço reservado é utilizado.
Nesta forma de organização pode-se ler e escrever registros em qualquer ordem e em
qualquer lugar. A grande vantagem é a rapidez de acesso a um determinado registro.
Apresenta o inconveniente de ser tarefa do programador o estabelecimento da relação
entre a posição que um registro ocupa e o seu conteúdo; alem disso, há o risco de se desperdiçar
parte do espaço reservado para o arquivo, já que podem ficar trechos vazios entre um registro e
outro.
IRG
02 Maria
IRG
01 Fred
IRG
06 Oscar
Arquivo Randômico de Acesso Direto
Pelo acesso direto, é reservado um endereço (na memória auxiliar) para cada um dos
registros do arquivo. A chave deste arquivo deve ser numérica, uma vez que será utilizada na
construção do endereçamento.
5
Como vantagem, este tipo de arquivo randômico provê maior rapidez no trato de um
registro isolado. Porém, pode apresentar muita memória reservada e não utilizada.
Arquivo Randômico de Acesso Calculado (ou de Endereçamento Indireto)
Este é usado para diminuir a não utilização de memória reservada.
O domínio da chave é concentrado, ou seja, é mais próximo da necessidade real, dos
registros realmente presentes.
Para calcular o endereço, aplica-se uma função à chave:
ENDEREÇO = RESTO (CHAVE, N)
onde N é o número primo mais próximo do total de registros.
Fatalmente ocorrem os sinônimos, registros com endereços iguais. No entanto, tal cálculo
só é aceitável quando causar menos de 20% de sinônimos.
Na ocorrência de sinônimos, o primeiro registro é gravado no endereço e, para o outro é
colocado um indicador (pointer) no primeiro registro mostrando a localização do segundo. Se
houver um terceiro, é colocado um outro indicador no segundo informando a localização do
terceiro. E assim por diante.
OBS: O pointer fica como campo adicional.
3. Organização Indexada
Os registros são armazenados em um arquivo de organização serial e para cada campo,
através do qual se deseja acesso direto, deve-se criar um arquivo de índices. Este é o processo
de indexação.
Para acessar os registros de um arquivo indexado é utilizada a PESQUISA
BINÁRIA.