ARQUIVOS INDEXADOS
POR CHAVES
SECUNDÁRIAS
1
CONCEITO
Na maioria das organizações de arquivos, dada uma
chave primária, recupera-se um registro. No
processamento com chaves múltiplas, procura-se
recuperar todos os registros, que possuam uma
particular combinação de valores de atributos.
Podem ocorrer vários registros com o mesmo valor
de atributo (chave secundária). Um índice secundário
indica uma lista de registros que possuem um dado
valor de chave secundária. Estes índices permitem a
consulta combinada utilizando interseção e união de
conjuntos de listas.
2
CONCEITO (cont)
Índices secundários permitem rápida
recuperação de registros com certo
valor de atributo. Contudo, índices
ocupam espaços e exigem grande
esforço de atualização. Deve-se
estudar, caso a caso, a conveniência de
adoção de índices secundários.
3
Arquivos com Listas
Considere-se a associação de um
ponteiro a cada chave secundária
indexada. O ponteiro indica o próximo
registro com o mesmo valor de chave
secundária. O arquivo é "atravessado"
por um grande número de listas, teias
ou costuras.
4
Arquivos com Listas (cont.)
O índice para um atributo contém uma
entrada para cada valor desse atributo
que ocorre no arquivo.
Cada entrada do índice funciona como
cabeça da lista, apontando um registro
com esse valor de atributo
5
Composição de Índices
Secundários
Índice
Secundário
Cabeçalho
do Índice
Listas do
Índice
6
Índice
Secundário
Cabeçalho de Índice Secundário
Cabeçalho
do Índice
Atributos do cabeçalho de Índice
Secundário
Listas do
Valor do atributo chave secundária Índice
Comprimento da lista com esse valor de
chave secundária
Endereço do primeiro registro da lista com
esse valor de chave secundária
Endereço do último registro da lista com
esse valor de chave secundária
7
Cabeçalho de Índice Secundário
Registro
Departamento
0
1
2
3
Caixa de nós
Administrativo
Técnico
Comercial
Comprimento Primeiro
Último
da lista
endereço endereço
9
11
7
31
4
5
6
31
29
30
28
8
Cabeçalho de Índice Secundário
Registro
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Departamento
Caixa de nós
Motorista
Programador
Secretária
Escriturário
Diretor
Contador
Almoxarife
Operador
Médico
Vendedora
Engenheiro
Desenhista
Gerente
Publicitário
Contínuo
Analista
Comprimento Primeiro
Último
da lista
endereço endereço
1
1
2
2
2
2
1
1
1
2
3
1
3
2
1
2
44
35
37
40
29
24
20
17
36
34
42
26
23
31
38
22
18
44
35
37
41
30
25
21
17
36
34
43
28
23
33
39
22
19
9
Índice
Secundário
Listas de Índice Secundário
Cabeçalho
do Índice
Composição dos endereços
Listas do
Bucket (obrigatório)
Índice
Slot (desejável)
Arquivo (necessário caso o arquivo
principal tenha trasbordamento em
arquivo separado)
10
Listas de Índice Secundário
(cont.)
Registro
Arquivo
Endereço
Slot
Nome
4
5
6
7
8
1
1
1
1
1
6
0
6
2
5
1
1
2
1
1
Ademar
Afonso
Iara
Edmundo
Cristiano
Departamento
Próx. Anter.
Administrativo 7
Técnico
9
Comercial
14
Administrativo 8
Administrativo 10
1
2
3
4
7
11
Listas de Índice Secundário
(cont.)
Registro
17
18
19
20
21
Arquivo
1
1
1
1
1
Endereço
6
0
6
2
5
Slot
Nome
1
1
2
1
1
Ademar
Afonso
Iara
Edmundo
Cristiano
Profissão
Motorista
Programador
Secretaria
Escriturário
Diretor
Próx.
1
2
34
32
22
Anter.
1
2
3
4
5
12
Exemplo
Um arquivo de produtos de "software"
contendo os atributos fornecedor,
nome do produto, tipo, plataforma de
utilização cuja chave primária é nome
do produto, deve ser indexado pela
chave secundária fornecedor. Solicitase exibir a configuração do arquivo e do
respectivo índice.
13
Índice
Secundário
Exemplo (cont.)
Cabeçalho
do Índice
Índice de fornecedor
Microsoft 1
Oracle
2
Novell
4
IBM
5
Lotus
6
Borland
13
Corel
16
Apple
17
Listas do
Índice
14
Exemplo (cont.)
Arquivo com índices (parte)
Registro
Fornecedor
número
Próximo
Nome
Tipo
fornecedor
Plataforma
original
1
Novell
10
UNIX
SO
Aberta
2
Microsoft
4
DOS
SO
PC
3
Oracle
0
Oracle
SGBD
Aberta
4
Microsoft
7
Foxpro
SGBD
PC
5
IBM
8
Lan
Server
LAN
PC
6
Lotus
12
Lotus
1-2-3
Planilha
eletronica
PC
7
Microsoft
9
Word
Editor de
texto
PC
15
Tipos de Arquivos com Índices Secundários
Arquivos Multilistas
Arquivos Invertidos
16
Arquivos Multilistas
17
Arquivos Multilista
Multilistas
Nos arquivos com índice secundário a
estrutura de índices possui uma entrada para
o índice de uma lista no arquivo principal
Pode-se considerar uma organização na qual
a estrutura de índices contenha uma entrada
para cada í-ésimo registro da lista com o
mesmo valor de atributo. Diz-se que esta
organização é uma organização multilista de
tamanho controlado, i, de lista.
18
Arquivos Multilista (cont.)
Os arquivos nos quais i = infinito são
chamados simplesmente de "multilistas".
Arquivos para os quais i = 1 são chamados
invertidos.
Os arquivos multilistas apresentam como
vantagem a extrema simplicidade da
estrutura de índices e como desvantagem o
processamento lento e a inadequação para a
aceitação de consultas complexas.
19
Arquivos Multilista
Arquivo Principal
Arquivo de índices
Cabeçalho
do Índice
Listas do
Índice
20
Listas de Índice Secundário
Atributos do registro de Listas de Índice
Secundário para Arquivos Multilista
Endereço do próximo registro da lista com
esse valor de chave secundária (no arquivo
principal)
Endereço do registro anterior da lista com
esse valor de chave secundária (no arquivo
principal)
21
Geração de Arquivo Multilista
Arquivos multilistas são criados a partir de arquivos seqüenciais em um
procedimento de seis passos O algoritmo a ser mostrado é creditado a
Lefkowitz e utiliza a seguinte notação :
ED = endereço de disco. Numeração dos registros em relação ao início do
arquivo
CP = chave primária dos registros do arquivo.
CA = chave de acesso. Atributo chave secundária que criou o multilista.
CL = comprimento de lista. Número de registros com o mesmo valor de
chave de acesso.
EC = endereço de cabeça. ED do primeiro registro com um dado valor de
chave de acesso.
INC = itens não chave. Atributos de registro que não influem no
processamento de multilista.
P = ponteiro para o sucessor na multilista da respectiva chave de acesso
22
Geração de Arquivo Multilista (cont.)
Na hipótese de ocorrência de n atributos
para os quais se quer multilistas são criados
4*n+1 arquivos temporários de trabalho, n
arquivos de índices e um arquivo de saída.
A composição de campos do arquivo original
é a seguinte, lembrando que os campos
sombreados são aqueles pelos quais o
arquivo está classificado:
23
Geração de Arquivo Multilista (cont.)
composição de campos do arquivo original
CP CA1 CA2 .... INC1 INC2 ...
composição de campos do arquivo multilista obtido
CP CA1 P1 CA2 P2 .... .... INC1 INC2 ...
24
Geração de Arquivo Multilista (cont.)
Haverá um arquivo de índices para
cada chave de acesso. A composição
de campos dos registros de cada um
deles é a seguinte
CAi ECi CLi
25
Desenvolvimento do algoritmo
Arquivo original :
Arquivo A1 ( 1 arquivo)
CP CA1 CA2 .... INC1 INC2
26
1º passo : Atribuição dos
endereços de disco
Os itens não chave são descartados e
cria-se um atributo endereço de disco
que recebe numeração seqüencial.
Arquivo resultante : A2 ( 1 arquivo)
ED CP CA1 CA2 ....
27
2º passo : Geração das triplas
ED, CP, CA
O arquivo A2 é decomposto em tantos
arquivos quantas são as chaves de acesso.
Cada arquivo obtido conterá o endereço de
disco, a chave primária e uma chave de
acesso.
Arquivos resultantes : A3 ( n arquivos)
ED CP CAi
28
3º passo : Classificação por
chave de acesso
Cada um dos arquivos A3 é classificado
pela chave de acesso correspondente.
Arquivos resultantes :
A4 ( n arquivos)
ED CP CAi
29
4º passo : Geração dos índices
e inserção dos ponteiros
Cada um dos arquivos A4 é processado gerando
dois arquivos : um arquivo de índices, A5, e um
arquivo com endereço de disco, chave primária,
chave de acesso e um ponteiro para o sucessor na
multilista da respectiva chave de acesso.
Arquivos resultantes : A5 ( n arquivos)
CAi ECi CLi
A6 ( n arquivos)
ED CP CAi Pi
30
5º passo : Classificação por
chave primária
Cada um dos arquivos A6 é classificado
pela chave primária.
Arquivos resultantes :
A7 ( n arquivos)
ED CP CAi Pi
31
6º passo : Montagem do arquivo
de saída
O arquivo de entrada A1 e todos os arquivos
A7 sofrem um processo de junção e
descarta-se o endereço de disco. Os
arquivos de índices são os arquivos A5
gerados no 4 0 passo do algoritmo.
Arquivos resultantes : A8 ( 1 arquivo)
CP CA1 P1 CA2 P2 .... .... INC1 INC2 ...
32
Exemplo de Multilista
Considere-se um arquivo tal como o
que se segue, e que se deseja utilizar
como entrada para obtenção de um
arquivo multilista com chaves de
acesso ENDEREÇO e PERÍODO.
Pede-se esboçar a aplicação do
algoritmo
de
Lefkowitz,
sendo
NÚMERO a chave primária
33
Exemplo de Multilista
A1
CP
INC
CA1
CA2
NÚMERO
NOME
ENDEREÇO
PERÍODO
15
João
MG
1
18
José
SP
3
25
Maria
RJ
3
37
Gérson
MG
3
41
Sandra
SP
1
43
Miguel
MG
1
45
Ana
SP
1
34
1° passo - Atribuição dos ED
A2
CP
ED
CA1
CA2
NÚMERO
***
ENDEREÇO
PERÍODO
15
1
MG
1
18
2
SP
3
25
3
RJ
3
37
4
MG
3
41
5
SP
1
43
6
MG
1
45
7
SP
1
35
2° passo - Geração das triplas CA, ED, CP
A3
(Atributo ENDEREÇO)
CA1
ED
CP
ENDEREÇO
***
NÚMERO
MG
1
15
SP
2
18
RJ
3
25
MG
4
37
SP
5
41
MG
6
43
SP
7
45
36
2° passo - Geração das triplas CA, ED, CP (cont.)
A3
(Atributo PERÍODO)
CA2
ED
CP
PERÍODO
***
NÚMERO
1
1
15
3
2
18
3
3
25
3
4
37
1
5
41
1
6
43
1
7
45
37
3° passo - Classificação pela chave de acesso
A4
(Atributo ENDEREÇO)
CA1
ED
CP
ENDEREÇO
***
NÚMERO
MG
1
15
MG
4
37
MG
6
43
RJ
3
25
SP
2
18
SP
5
41
SP
7
45
38
3° passo - Classificação pela chave de acesso (cont.)
A4
(Atributo PERÍODO)
CA2
ED
PERÍODO
CP
NÚMERO
1
1
15
1
5
41
1
6
43
1
7
45
3
2
18
3
3
25
3
4
37
39
4° passo - Geração dos índices e dos arquivos
A5
(Atributo ENDEREÇO)
CA1
EC
CL
ENDEREÇO
***
***
MG
1
3
RJ
3
1
SP
2
3
40
4° passo - Geração dos índices e dos arquivos
(cont. índices)
A5
(Atributo PERÍODO)
CA2
EC
CL
PERÍODO
***
***
1
1
4
3
2
3
41
4° passo - Geração dos índices e dos arquivos
(cont. arquivos)
A6
(Atributo ENDEREÇO)
CA1
ED
CP
P1
ENDEREÇO
***
NÚMERO
***
MG
1
15
4
MG
4
37
6
MG
6
43
0
RJ
3
25
0
SP
2
18
5
SP
5
41
7
SP
7
45
0
42
4° passo - Geração dos índices e dos arquivos
(cont. arquivos 2)
A6
(Atributo PERÍODO)
CA2
ED
CP
P2
PERÍODO
***
NÚMERO
***
1
1
15
5
1
5
41
6
1
6
43
7
1
7
45
0
3
2
18
3
3
3
25
4
3
4
37
0
43
5° passo - Classificação por chave primária
A7
(Atributo ENDEREÇO)
CA1
ED
CP
P1
ENDEREÇO
***
NÚMERO
***
MG
1
15
4
SP
2
18
5
RJ
3
25
0
MG
4
37
6
SP
5
41
7
MG
6
43
0
SP
7
45
0
44
5° passo - Classificação por chave primária (cont.)
A7
(Atributo PERÍODO)
CA2
ED
CP
P2
PERÍODO
***
NÚMERO
***
1
1
15
5
3
2
18
3
3
3
25
4
3
4
37
0
1
5
41
6
1
6
43
7
1
7
45
0
45
6° passo - Junção de A1 e de todos os A7
A8
CP
CA1
CA2
INC
P1
P2
NÚMERO
ENDEREÇO
PERÍODO
NOME
(p/
ENDEREÇO)
(p/
PERÍODO)
15
MG
1
João
4
5
18
SP
3
José
5
3
25
RJ
3
Maria
0
4
37
MG
3
Gérson
6
0
41
SP
1
Sandra
7
6
43
MG
1
Miguel
0
7
45
SP
1
Ana
0
0
46
Arquivos Invertidos
47
Listas de Índice Secundário
Atributos do registro de Listas de Índice
Secundário para Arquivos Invertidos
Endereço do registro da lista com esse valor de
chave secundária (no arquivo principal)
Valor da chave primária do registro apontado no
arquivo principal (par poder classificar a lista)
Endereço do próximo registro da lista com esse
valor de chave secundária (no arquivo de listas)
Endereço do registro anterior da lista com esse
valor de chave secundária (no arquivo de listas)
48
Arquivos Invertidos
Arquivo Principal
Arquivo de índices
Cabeçalho
do Índice
Listas do
Índice
49
Arquivos Multilista
Arquivo Principal
Arquivo de índices
Cabeçalho
do Índice
Listas do
Índice
50
Arquivos Invertidos
Arquivo Principal
Arquivo de índices
Cabeçalho
do Índice
Listas do
Índice
51
Arquivos invertidos
Arquivos Invertidos
A organização invertida é baseada na mudança de papéis entre registro e
atributos. Pode-se considerar que o arquivo é uma função que, dado um
endereço, retorna os atributos do registro contido naquele endereço.
arquivo(endereço)  (atributo,valor), (atributo,valor), (atributo,valor),
...
Os arquivos de índice representam a inversa dessa função pois, dado um par
<atributo, valor do atributo>, recupera-se uma lista de endereços de registros
com o valor especificado do atributo, ou
arquivo(atributo,valor)  endereço, endereço, ....
Um arquivo de índices que identifica cada registro com um dado valor de
atributo é considerado um arquivo invertido pois funciona como a inversa da
função "Arquivo Principal". A cada um dos valores de chave de acesso presente
no arquivo é associada uma lista de identificação ou lista invertida.
Na organização invertida, a cada valor de chave de acesso está associado não
apenas um registro e sim um conjunto de registros que possui aquele valor de
chave.
52
Inversões e Listas Invertidas
O conjunto de listas invertidas associadas a um
determinado atributo é chamado de inversão por
aquele atributo. Um arquivo pode ter uma ou mais
inversões. O número de listas invertidas em cada
inversão é igual ao número de diferentes valores
daquele atributo existente no arquivo.
O arquivo de índices contém inversões, cada
inversão contém diversas listas invertidas, cada lista
invertida contém um "header" (que identifica o valor
do atributo correspondente a esta lista e o
comprimento da lista) e a lista dos endereços de
registros que contém este valor de atributo
53
Grau de Inversão
Chama-se grau de inversão de um arquivo a porcentagem de
atributos indexados por inversão. Um arquivo com todos os
atributos indexados tem 100% de grau de inversão.
Os sistema de informação comerciais são sistemas de
recuperação de referências (ou documentos).As referências são
armazenadas junto com palavras chave indicadoras de seu
conteúdo. Os usuários solicitam informações sob a forma de
expressões "booleanas", do tipo :
quais as referências existente sobre "tendinite" and
("teclado" or "terminal").
Praticamente todos esses sistemas utilizam arquivos invertidos.
54
Implementação das inversões
As representações das listas invertidas
são feitas pelos processos
convencionais de representação de
listas, ou seja, por contigüidade, por
encadeamento e por mapa de bits.
55
Implementação das inversões por contigüidade
56
Implementação das inversões por encadeamento
57
Representação por Mapa de Bits
Mapas de bits são arrays bidimensionais nos
quais cada linha corresponde a um registro
do arquivo principal e cada coluna
corresponde a um dos valores do atributo
que ocorrem no arquivo principal. Cada mapa
de bits corresponde a um atributo, cada bit 1
indica que o registro correspondente
pertence à lista de registro com o valor de
atributo correspondente à coluna onde se
encontra o bit 1.
58
Representação por Mapa de Bits
59
Mais uma maneira de implementar listas : Grafos
Pode-se economizar espaço em estruturas encadeadas de índices
combinados os elementos da lista que apontam para um
mesmo registro do arquivo principal. Cada registro do arquivo
principal é representado em uma inversão por um simples nó,
que pode pertencer a tantas lista quantos são os atributos
indexados, formando-se assim uma estrutura de grafo. Cada nó
destes grafos conterá :
- um ponteiro para o arquivo principal
- para cada atributo indexado :
um ponteiro para o nó proprietário da lista
um ponteiro para o próximo nó com o mesmo valor de atributo
60
Mais uma maneira de implementar listas : Grafos
61
Mais uma maneira de implementar listas : Grafos
Para exemplificar um nó genérico de
um grafo que represente listas podese utilizar o exemplo de produtos de
"software" do item 7.2. Do arquivo do
exemplo são exibidos os nós que
correspondem aos registros 1, 3 e 4,
como se vê na figura 7.4.
62
Exemplo de Inversões
Exemplo de Inversão de Arquivos
O Arquivo de dados é exibido abaixo
Pede-se apresentar as inversões pelos atributos Departamento e Profissão
Registro Numero Nome
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
1000
1050
2400
1850
1440
3150
2000
1900
2430
2600
1075
1400
2200
2700
1100
1800
3100
2500
1300
2450
1600
1480
2950
1970
1350
1950
1700
Ademar
Afonso
Iara
Edmundo
Cristiano
Tatiana
Gerson
Ênio
Ivan
Miguel
Angela
Claudia
Helena
Ramon
Antônio
Edson
Sônia
Maria
Carlos
Luiz
Diogo
Darci
Sandra
Genaro
César
Flávio
Éber
Profissão
Departamento
Motorista
Programador
Secretária
Escriturário
Diretor
Diretor
Contador
Almoxarife
Operador
Médico
Vendedora
Engenheiro
Engenheiro
Desenhista
Gerente
Escriturário
Vendedora
Secretária
Publicitário
Publicitário
Contínuo
Contador
Analista
Engenheiro
Gerente
Gerente
Analista
Administrativo
Técnico
Comercial
Administrativo
Administrativo
Técnico
Administrativo
Administrativo
Técnico
Administrativo
Comercial
Técnico
Técnico
Técnico
Técnico
Comercial
Comercial
Técnico
Comercial
Comercial
Administrativo
Administrativo
Técnico
Técnico
Comercial
Administrativo
Técnico
Arquivo Endereço Slot
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
0
6
2
5
0
5
3
1
3
4
0
2
5
1
1
6
1
5
0
4
3
3
3
6
4
6
1
1
2
1
1
2
2
1
1
2
1
3
2
3
2
3
3
4
4
4
2
3
4
5
4
3
5
63
Inversão por Departamento usando
encadeamento
Exemplo de Inversão de Arquivos
Inversão por Departamento
Registro Arquivo Endereço Slot
0
1
2
3
9
11
7
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
0
6
2
5
0
5
3
1
3
4
0
2
5
1
1
6
1
5
0
4
3
3
3
6
4
6
1
1
2
1
1
2
2
1
1
2
1
3
2
3
2
3
3
4
4
4
2
3
4
5
4
3
5
Nome
Ademar
Afonso
Iara
Edmundo
Cristiano
Tatiana
Gerson
Ênio
Ivan
Miguel
Angela
Claudia
Helena
Ramon
Antônio
Edson
Sônia
Maria
Carlos
Luiz
Diogo
Darci
Sandra
Genaro
César
Flávio
Éber
Departamento
Próx. Anter.
Caixa de nós 31
Administrativo 4
Técnico
5
Comercial
6
31
29
30
28
Administrativo
Técnico
Comercial
Administrativo
Administrativo
Técnico
Administrativo
Administrativo
Técnico
Administrativo
Comercial
Técnico
Técnico
Técnico
Técnico
Comercial
Comercial
Técnico
Comercial
Comercial
Administrativo
Administrativo
Técnico
Técnico
Comercial
Administrativo
Técnico
1
2
3
4
7
5
8
10
9
11
6
12
15
16
17
14
19
18
20
22
13
24
21
26
23
25
27
7
9
14
8
10
12
11
13
15
24
19
16
17
18
21
20
22
26
23
28
25
29
27
30
3
1
2
64
Exemplo de Inversão de Arquivos
Inversão por Profissão
Registro Arquivo Endereço Slot Nome
Inversão por
Profissão
usando
encadeamento
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
1
2
2
2
2
1
1
1
2
3
1
3
2
1
2
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
0
6
2
5
0
5
3
1
3
4
0
2
5
1
1
6
1
5
0
4
1
1
2
1
1
2
2
1
1
2
1
3
2
3
2
3
3
4
4
4
2
Ademar
Afonso
Iara
Edmundo
Cristiano
Tatiana
Gerson
Ênio
Ivan
Miguel
Angela
Claudia
Helena
Ramon
Antônio
Edson
Sônia
Maria
Carlos
Luiz
Diogo
Profissão
Próx. Anter.
Caixa de nós
Motorista
Programador
Secretária
Escriturário
Diretor
Contador
Almoxarife
Operador
Médico
Vendedora
Engenheiro
Desenhista
Gerente
Publicitário
Contínuo
Analista
44
35
37
40
29
24
20
17
36
34
42
26
23
31
38
22
18
44
35
37
41
30
25
21
17
36
34
43
28
23
33
39
22
19
Motorista
Programador
Secretaria
Escriturário
Diretor
Diretor
Contador
Almoxarife
Operador
Médico
Vendedora
Engenheiro
Engenheiro
Desenhista
Gerente
Escriturário
Vendedora
Secretária
Publicitário
Publicitário
Contínuo
1
2
34
32
22
5
38
7
8
9
33
29
40
12
41
4
10
3
36
14
15
1
2
3
4
5
21
6
7
8
9
10
11
28
12
13
20
27
19
14
35
15
65
Inversão por Profissão usando Mapas de
Bits
Exemplo de Inversão de Arquivos
Secretária
Escriturário
Diretor
Contador
Almoxarife
Operador
Médico
Vendedora
Engenheiro
Desenhista
Gerente
Publicitário
Contínuo
Analista
Registro
1 1
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
Programador
Motorista
Inversão por Profissão usando mapas de bits
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
66
Inversão por Departamento usando
Mapas de Bits
Exemplo de Inversão de Arquivos
Inversão por Departamento usando mapas
Registro Administrativo Técnico Comercial
1
1
0
0
2
0
1
0
3
0
0
1
4
1
0
0
5
1
0
0
6
0
1
0
7
1
0
0
8
1
0
0
9
0
1
0
10
1
0
0
11
0
0
1
12
0
1
0
13
0
1
0
14
0
1
0
15
0
1
0
16
0
0
1
17
0
0
1
18
0
1
0
19
0
0
1
20
0
0
1
21
1
0
0
22
1
0
0
23
0
1
0
24
0
1
0
25
0
0
1
26
1
0
0
27
0
1
0
67
Algoritmo de implementação de Listas Invertidas
O algoritmo do Livro mostra uma implementação de inversão de arquivos na qual se
considera a inversão de um arquivo de acesso direto implementada por encadeamento,
com as seguintes hipóteses:
O arquivo de acesso direto possui área de transbordamento separada;
O número de "buckets" na área primária do arquivo de acesso direto é igual a n_buckets;
O número de "slots" de cada "bucket" na área primária é igual a n_slots;
O tratamento de transbordamento é feito por encadeamento em área secundária;
Os buckets da área secundária só possuem um "slot" cada;
O registro a ser inserido na lista invertida está gravado no "slot" de posição slot_corrente
do bucket de endereço bucket_corrente;
O arquivo de inversões será implementado por listas duplamente encadeadas;
O número de registros do arquivo de inversões é igual a n_regs_inversão;
O número máximo previsto de distintos valores para a chave secundária é
tamanho_header;
O algoritmo de alocação de registros do arquivo de inversões utiliza preferencialmente
registros reaproveitados de exclusões anteriores (mantidos em uma pilha). Não havendo
possibilidade de utilização de registros reaproveitados, são alocados registros ainda não
utilizados mantidos em uma fila.
68