Arquivos Sequenciais
Indexados
Prof. Flávio Humberto Cabral Nunes
Conteúdo
1.
2.
3.
4.
Introdução
Índices
Área de Extensão (Área de Overflow)
Operações
Capítulo: 9 (APOSTILA).
Introdução
Arquivos sequenciais são utilizados para
acessos seriais
Mas quando o volume de acessos aleatórios
em um arquivo sequencial é muito grande, é
necessário utilizar uma estrutura de acesso,
associada ao arquivo, que aumente a
eficiência na localização dos registros
Arquivo Sequencial Indexado
Um arquivo sequencial acrescido de um
índice (estrutura de acesso)
Um índice é formado por uma coleção de
pares que associam um valor de chave a um
endereço no arquivo
Além do arquivo sequencial e dos índices,
possui áreas de extensão que são utilizadas
para implementar a 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.
O endereço identifica a posição onde está
armazenado o registro no arquivo
Índices são formados por dois campos:
–
–
Chave do registro
Endereço do registro
Índices
Ocupam um espaço bem menor do que o
registro de dados correspondente
Assim, a pesquisa sobre o índice pode ser
feita com maior rapidez do que se fosse feita
diretamente sobre o arquivo de dados
correspondente
Isto justifica a utilização de índices
Exemplo
ÍNDICE
ÁREA DE DADOS NO DISCO
Número Endereço
Número
Nome
Salário
100
1
1
100
Pedro
3000
150
2
2
150
João
1500
200
3
3
200
Maria
2500
250
4
4
250
Carla
3000
300
5
5
300
Max
2000
Exemplo
class Cliente {
public:
int codigo;
char empresa[61];
char telefone[13];
char endereco[61];
char numero[11];
char complemento[26];
char bairro[26];
char cep[9];
char cidade[26];
char estado[3];
}
Busca Sequencial (Código)
...
// usuário fornece o argumento de pesquisa cc
...
while(fin.read((char*)&c, sizeof(Cliente))) {
leituras++;
if(c.codigo == cc) {
imprime(c);
break;
}
}
Busca Sequencial (Resultado)
A resposta do código é o tempo em que a
pesquisa começa, o registro encontrado e o
tempo em que a pesquisa finaliza
Foram necessários 0,55 segundos para
localizar o registro de código 9000.
–
Foram pesquisados 8473 registros
Busca Sequencial no Arquivo de
Índices (Código)
...
// o usuário fornece o argumento para pesquisa: cc
...
while(index.read((char*)&ind, sizeof(Indice))) {
leituras++;
if(ind.chave == cc) {
registro.seekg(ind.endereco*sizeof(Cliente),
ios::beg);
registro.read((char*)&reg, sizeof(Cliente));
imprime(reg);
break;
}
}
Busca Sequencial no Arquivo de
Índices (Resultado)
A resposta do código é o tempo em que a
pesquisa começa, o registro encontrado e o
tempo em que a pesquisa finaliza
A busca pelo registro 9000 gastou apenas
0,05 segundos.
Isso mostra que o tamanho do arquivo
interfere no tempo de busca
Índices Estruturados em Vários Níveis
Pode ser estruturado em vários níveis para
tornar a busca mais eficiente.
O número de níveis é proporcional ao
número de entradas do índices
Índices Estruturados em Vários Níveis
Como os registros estão ordenados no
arquivo de dados
–
–
–
Usa-se uma entrada para cada bloco
Armazena-se o valor da maior chave do bloco
Armazena-se o endereço de início do bloco
Dessa forma, economiza-se espaço, pois
não é necessário ter uma entrada do índice
para cada registro lógico
Índices
Índices associados à chave de ordenação
são chamados de índices primários e os
demais de índices secundários
Normalmente, são implementados utilizandose árvores B ou B+, principalmente devido à:
–
–
Facilidade (flexibilidade) de inserção/exclusão
Eficiência das pesquisas nessas árvores (poucos
níveis)
Área de Extensão (Área de Overflow)
Destina-se a conter os registros inseridos,
em um arquivo sequencial indexado, após a
criação do arquivo.
Ela constitui uma extensão da área principal
de dados do arquivo
Área de Extensão (Área de Overflow)
Áreas de extensão são necessárias em
arquivos sequenciais indexados porque
nesses não é viável a implementação da
operação de inserção de registros do mesmo
modo que nos arquivos sequenciais
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
Campo de Elo
Uma possível implementação de áreas de
extensão em um arquivo sequencial
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
Campo de Elo (Exemplo)
ÁREA DE DADOS NO DISCO
Número Nome Elo
ÍNDICE
Número Endereço
1
100
Pedro
-
2
150
João
10
3
200
Maria
-
4
250
Carla
20
5
300
Max
-
100
1
150
2
175
2
200
3
250
4
275
4
ÁREA DE EXTENSÃO
300
5
Número Nome Elo
10
175
Bill
3
20
275
Nara
5
Campo de Elo por Registro
Cada registro lógico na área principal de
dados possui um campo de elo, que contém
o endereço da lista encadeada e ordenada
de seus antecessores armazenados na área
de extensão
Nas inserções, um registro é inserido na lista
de extensão de seu sucessor da área
principal (a menos que ele seja inserido no
final do arquivo, por sua chave ser maior que
todas as outras do arquivo
Campo de Elo por Registro
ÁREA DE DADOS NO DISCO
Inserir: 165 - Marta
ÍNDICE
Número
Nome
Elo
1
100
Pedro
-
Número
Endereço
2
150
João
-
100
1
3
200
Maria
10
150
2
4
250
Carla
-
175
3
5
300
Max
20
200
3
250
4
275
5
300
5
ÁREA DE EXTENSÃO
Número
Nome
Elo
10
175
Bill
-
20
275
Nara
-
Campo de Elo por Registro
ÁREA DE DADOS NO DISCO
Inserir: 165 - Marta
ÍNDICE
Número
Nome
Elo
1
100
Pedro
-
Número
Endereço
2
150
João
-
100
1
3
200
Maria
30
150
2
4
250
Carla
-
165
3
5
300
Max
20
175
3
200
3
250
4
275
300
ÁREA DE EXTENSÃO
Número
Nome
Elo
10
175
Bill
-
5
20
275
Nara
-
5
30
165
Marta
10
Campo de Elo por Bloco
Cada bloco de registros na área principal de
dados possui um campo de elo, que contém
o endereço da lista de extensão do bloco.
Sendo que dentro de cada bloco os registros
estão ordenados e todos os da área de
extensão possuem valor de chave maior do
que os que estão no bloco da área principal
de dados
Campo de Elo por Bloco
Um registro é inserido no bloco selecionado
e o maior do bloco vai para a área de
extensão
Os registros já armazenados podem mudar
de posição (endereço) quando um novo
registro é inserido, assim sendo, não deve
ser usado quando há índices secundários
para o arquivo
Campo de Elo por Bloco
O arquivo ocupa espaço para a área
principal de dados menor que a organização
com um campo de elo por registro, pois só
terá um campo de elo a caba bloco em vez
de a cada registro lógico
A ordenação dentro do bloco é feita em
memória, portanto não acarreta grande custo
adicional
Campo de Elo por Bloco
ÁREA DE DADOS NO DISCO
Inserir: 130 - Marta
ÍNDICE
Número
Endereço
175
1
250
3
B1
B2
Número
Nome
Elo
1
100
Pedro
-
2
150
João
10
3
200
Maria
-
4
250
Carla
-
ÁREA DE EXTENSÃO
10
Número
Nome
Elo
175
Bill
-
Campo de Elo por Bloco
ÁREA DE DADOS NO DISCO
Inserir: 130 - Marta
ÍNDICE
Número
Endereço
175
1
250
3
B1
B2
Número
Nome
Elo
1
100
Pedro
-
2
130
Marta
20
3
200
Maria
-
4
250
Carla
-
ÁREA DE EXTENSÃO
Número
Nome
Elo
10
175
Bill
-
20
150
João
10
Operações
Busca
Inserção
Remoção
Alteração
Leitura exaustiva
Reorganização
Busca
Sequencial
–
Busca na área de dados e na área de extensão
simultaneamente
Aleatória
–
Busca pelo índice até localizar o bloco do registro
desejado e se o registro não está na área de
dados, verificar a área de extensão
Inserção
Deve-se buscar pelo índice para determinar
o local onde o novo registro deve ser
inserido e fazer a inserção de acordo com a
organização utilizada
–
–
Elo por registro: na lista encadeada de extensão
de seu sucessor
Elo por bloco: ordenando os registros e enviando
para área de extensão os de maior valor de
chave do bloco
Remoção e Alteração
Remoção
–
–
Deve-se localizar o registro
Marcá-lo como excluído para posterior liberação
de espaço alocado pelo mesmo (reorganização)
Alteração
–
–
–
Localiza o registro
Se a chave de ordenação não for alterada, é feita
diretamente
Caso contrário, o registro é marcado como
excluído e inserido novamente após a
atualização
Leitura Exaustiva
Para todos os registros em ordem, a leitura
exaustiva pode ser realizada sobre a área de
dados lembrando de apresentar na ordem os
registros da área de extensão, acessíveis a
partir do campo de elo da área principal
Reorganização
Feita através da leitura exaustiva dos
registros
Transferência dos registros para uma nova
área principal de dados
Registros marcados como excluídos são
ignorados, liberando-se toda a área de
extensão
Após a transferência dos registros para a
nova área principal de dados, um novo
índice deve ser criado
Reorganização
Necessária devido à degradação de
performance provocada por:
–
–
Grande número de acesso à área de extensão
Desconsideração dos registros marcados como
excluídos
Normalmente, ela é indicada quando o
arquivo não está sendo utilizado e/ou 75%
da área de extensão estiver ocupada