arquivos_sequeciais_indexados_(slides)

Prévia do material em texto

1
Arquivos Seqüenciais 
Indexados
Professor: Alexandre Scaico
alexandre_scaico@yahoo.com.br
Faculdade de Ciências Sociais Aplicadas
Curso de Sistemas de Informações
Organização e Busca da Informação
2
Introdução
„ Arquivo seqüencial
„ Bom para acesso seqüencial
„ Ruim para acesso aleatório
„ Arquivo de acesso direto
„ Bom para acesso aleatório
„ Ruim para acesso seqüencial
3
Introdução
„ Quando o volume de acessos aleatórios num 
arquivo seqüencial torna-se grande, acrescenta-se 
um Índice (estrutura de acesso), transformando-o 
em um Arquivo Seqüencial Indexado 
„ Um Índice ou Arquivo de Índices é uma coleção 
de registros do tipo <chave do registro de 
dados,endereço do registro de dados> 
„ Ou seja, cada entrada no índice associa um valor de 
chave ao endereço do registro no arquivo de dados, ou 
o endereço de um bloco de dados
4
Introdução
„ Como funciona uma estrutura Seqüencial 
Indexada? 
„ Os registros no arquivo de dados devem estar 
ordenados 
„ Indexar os arquivos em blocos de registros comuns
5
Introdução
Estrutura seqüêncial indexada
6
Introdução
„ Exemplo → arquivo seqüencial indexado com 
blocos de dados de 3 registros
2
7
Introdução
„ No Arquivo de Índice 
„ O atributo CHAVE corresponde a maior chave de um 
bloco de registros 
„ O atributo ENDEREÇO é o endereço do primeiro 
registro no bloco 
„ O acesso aleatório é feito com a utilização do índice 
„ O acesso seqüencial a um registro pode ser feito 
diretamente sobre a área de dados, sem a utilização do 
índice, como se fosse um arquivo seqüencial 
„ Como a quantidade de blocos é menor que a 
quantidade de registros, a pesquisa é mais rápida
8
Operações sobre Arquivos 
Seqüênciais Indexados
„ Arquivos Seqüenciais Indexados têm excelente 
desempenho para a recuperação, modificação e 
exclusão de registros 
„ Porém, a inclusão de registros nestes arquivos não 
é eficiente
9
Inclusão de Registros
„ Ocorre uma carga inicial, onde são criados o 
arquivo de dados e o índice
„ O arquivo de dados é criado a partir de um arquivo 
seqüencial de entrada
10
Inclusão de Registros
„ Inclusão de Novos Registros 
„ (1) Consulta-se o índice e determina-se o bloco do 
arquivo de dados no qual o registro deve ser 
armazenado 
„ A consulta é realizada através da chave primária
„ (2) Caso um bloco fique ou esteja cheio, os novos 
registros para este bloco serão armazenados numa área 
de overflow chamada Área de Extensão
„ (3) Se um registro incluído possuir a maior chave do 
bloco, a respectiva entrada no índice para aquele bloco 
deve ser atualizada com o valor de sua chave
11
Inclusão de Registros
„ Área de Extensão 
„ É uma extensão da área principal de dados 
„ A área de extensão é necessária porque não é viável a 
implementação da operação de inclusão de registros 
em seu endereço adequado
„ Isso acarreta a mudança de endereços dos registros 
posteriores
„Obriga uma completa alteração dos índices a cada nova 
inclusão no arquivo de dados
12
Inclusão de Registros
„ Alternativas de Implementação da Área de 
Extensão 
„ Existem duas alternativas
„ Ambas utilizam um atributo de ligação (ELO)
„ A diferença está em como o encadeamento é realizado 
na área de extensão
3
13
Inclusão de Registros
„ 1ª alternativa → Associar a cada registro do 
arquivo de dados um atributo de ligação (ELO) 
„ Para um registro alocado no arquivo de dados, o 
atributo de ligação contém o endereço do primeiro 
registro de uma lista encadeada de registros com 
valores de chave antecessores, estando esta lista 
alocada na área de extensão 
„ Para um registro alocado na área de extensão, o 
atributo de ligação contém o endereço do registro com 
valor de chave sucessor, estando este na própria área 
de extensão
14
Inclusão de Registros
„ Exemplo da 1ª alternativa
15
Inclusão de Registros
„ Exemplo da 1ª alternativa
„ Registros a incluir em uma área de extensão única com 
início no endereço 200
16
17
Inclusão de Registros
„ 2ª alternativa → Associar a cada bloco de registros 
um atributo de ligação (ELO)
„ O ELO é destinado a conter o endereço do primeiro 
registro de uma lista encadeada de registros com 
valores de chave sucessores, estando esta lista alocada 
na área de extensão 
„ Os registros armazenados na área de extensão terão o 
atributo de ligação (ELO), contendo o endereço do 
registro com valor de chave sucessor, estando este na 
própria área de extensão
„ Dentro do bloco, os registros devem estar ordenados 
fisicamente. Porém, na área de extensão a ordenação é
lógica, feita através do atributo de ligação 18
Inclusão de Registros
„ Exemplo da 2ª alternativa
4
19
Inclusão de Registros
„ Exemplo da 2ª alternativa
„ Registros a incluir em uma área de extensão única com 
início no endereço 200
20
21
Exclusão de Registros
„ Consulta-se o índice e determina-se o bloco do 
arquivo de dados no qual o registro deve estar 
armazenado 
„ A exclusão de um registro é implementada com a 
utilização de um Atributo de Estado indicando se 
o registro foi ou não excluído 
„ Se um registro marcado como "Excluído" possuir a 
maior chave do bloco, a respectiva entrada no índice 
para aquele bloco deve ser atualizada com o valor da 
chave imediatamente antecessora 
22
Exclusão de Registros
„ O atributo de estado deve ser consultado nas 
demais operações, sendo desconsiderados aqueles 
registros com a marca "excluído" 
„ Uma reorganização pode ser feita a fim de 
eliminar fisicamente os registros com a marca 
"excluído"
„ Isto implica na geração de um novo arquivo de dados e 
de um novo índice
23
Alteração de Registros
„ Consulta-se o índice e determina-se o bloco do 
arquivo de dados no qual o registro deve estar 
armazenado 
„ Se a alteração não envolve a chave de ordenação 
do registro, basta realizá-la normalmente, 
alterando os atributos e regravando o registro no 
mesmo endereço
„ Caso contrário, a alteração é implementada em 
duas fases → exclusão do registro e inclusão do 
registro com nova chave
24
Acesso aos Arquivos
„ O acesso aos registros de um arquivo seqüencial 
indexado pode ser feito de três formas
„ Serial, aleatório, busca exaustiva
„ Acesso serial 
„ Diretamente sobre o arquivo de dados, sem a 
utilização do índice 
„ É importante que a busca também considere os 
registros armazenados na área de extensão, os quais 
são acessados por meios do atributo de ligação (ELO)
5
25
Acesso aos Arquivos
„ Acesso aleatório 
„ Feito com a utilização do índice 
„ A chave de busca define o caminhamento sobre o 
índice, que conduz ao endereço do registro desejado 
„ O endereço obtido pode ser o próprio endereço do 
registro ou o endereço do primeiro registro do bloco 
que o contém
„Nesse último caso, é necessária uma busca no bloco, a qual 
pode requerer acessos à área de extensão 
26
Acesso aos Arquivos
„ Acesso por busca exaustiva (leitura de todos os 
registros do arquivo) 
„ Feita diretamente sobre o arquivo de dados, sem o uso 
do índice, devendo incluir os registros localizados na 
área de extensão, os quais são acessados por meio do 
atributo de ligação (ELO)
27
Reorganização dos Arquivos
„ Requisitos para Reorganização 
„ Quando existe acesso freqüente à área de extensão 
„ Para exclusão física dos registros logicamente excluídos
28
Reorganização dos Arquivos
„ Procedimento de Reorganização 
„ (1) Busca exaustiva de todos os registros do arquivo de 
dados e da área de extensão 
„ (2) Criação de um novo arquivo de dados 
„ (2.1) Transferência de todos os registros lidos no passo (1) 
para o novo arquivo de dados, exceto aqueles com a marca 
"Excluído" 
„ (3) Criação de um novo arquivo de índice 
„ (4) Exclusãodos antigos arquivos de dados e de índice, 
e da antiga área de extensão