Arquivos de Índices e Lista Invertida
Base de Dados Original
RA
NOME
CURSO
DISCIPLINA
1
Antônio T.
Computação MC101 MC102
3
Vera K.
Computação MC902
8
Antônio P.
Civil
MC326 MC420
10
Beatriz Q.
Elétrica
MC101 MC326
5
Caio V.
Mecânica
MC101 MC102 MC920
2
Caio M.
Mecânica
MC202 MC326
4
Tiago B.
Computação MC101
9
Zedna P.
Computação MC202 MC920
7
Mauro M.
Mecânica
MC102 MC202
6
Nilo R.
Elétrica
MC202
Arquivo de índice primário após ordenação
Arquivo original
RA
RA
NOME
CURSO
DISCIPLINA
1
1
Antônio T.
Computação
MC101 MC102
2
3
Vera K.
Computação
MC902
3
8
Antônio P.
Civil
MC326 MC420
4
10
Beatriz Q.
Elétrica
MC101 MC326
5
5
Caio V.
Mecânica
MC101 MC102 MC920
6
2
Caio M.
Mecânica
MC202 MC326
7
4
Tiago B.
Computação
MC101
8
9
Zedna P.
Computação
MC202 MC920
9
7
Mauro M.
Mecânica
MC102 MC202
10
6
Nilo R.
Elétrica
MC202
Arquivo de índice secundário: NOME
Arquivo original
NOME
RA
NOME
CURSO
DISCIPLINA
Antônio P.
1
Antônio T.
Computação
MC101 MC102
Antônio T.
3
Vera K.
Computação
MC902
Beatriz Q.
8
Antônio P.
Civil
MC326 MC420
Caio M.
10
Beatriz Q.
Elétrica
MC101 MC326
Caio V.
5
Caio V.
Mecânica
MC101 MC102 MC920
Mauro M.
2
Caio M.
Mecânica
MC202 MC326
Nilo R.
4
Tiago B.
Computação
MC101
Tiago B.
9
Zedna P.
Computação
MC202 MC920
Vera K.
7
Mauro M.
Mecânica
MC102 MC202
Zedna P.
6
Nilo R.
Elétrica
MC202
Ou ainda:
Arquivo de índice secundário: NOME
NOME
Chave
Primária
RA
1
RA
NOME
CURSO
DISCIPLINA
1
Antônio T.
Computação
MC101 MC102
3
Vera K.
Computação
MC902
8
Antônio P.
Civil
MC326 MC420
10
Beatriz Q.
Elétrica
MC101 MC326
5
Caio V.
Mecânica
MC101 MC102
MC920
Antônio P.
8
Antônio T.
1
Beatriz Q.
10
Caio M.
2
4
Caio V.
5
5
Mauro M.
7
6
Nilo R.
6
7
2
Caio M.
Mecânica
MC202 MC326
Tiago B.
4
8
4
Tiago B.
Computação
MC101
Vera K.
3
9
9
Zedna P.
Computação
MC202 MC920
Zedna P.
9
10
7
Mauro M.
Mecânica
MC102 MC202
6
Nilo R.
Elétrica
MC202
2
3
Modelos de Consultas
-- Quem tem RA = 4 ?
Busca binária no arquivo de chaves primárias:
RA
RA
NOME
CURSO
DISCIPLINA
1
1
Antônio T.
Computação
MC101 MC102
2
3
Vera K.
Computação
MC902
3
8
Antônio P.
Civil
MC326 MC420
4
10
Beatriz Q.
Elétrica
MC101 MC326
5
5
Caio V.
Mecânica
MC101 MC102 MC920
6
2
Caio M.
Mecânica
MC202 MC326
7
4
Tiago B.
Computação
MC101
8
9
Zedna P.
Computação
MC202 MC920
9
7
Mauro M.
Mecânica
MC102 MC202
10
6
Nilo R.
Elétrica
MC202
-- Quem faz Computação?
Busca binária no arquivo de chaves secundárias CURSO + percorrer a lista invertida
Lista invertida
Curso
Civil
Computação
Elétrica
Mecânica
2
7
9
8
0
1
-1
1
3
0
2
8
-1
3
10
-1
4
5
-1
5
2
4
4
1
7
9
6
8
7
5
9
6
3
6
-- Quem está matriculado em MC202 ?
Busca binária no arquivo de chaves secundárias DISCIPLINA + percorrer a lista invertida
Disciplina
MC101
12
MC102
15
MC202
17
MC326
MC420
MC902
MC920
11
4
2
14
0
1
-1
1
1
-1
2
3
-1
3
8
-1
4
8
-1
5
10
0
6
10
3
7
5
5
8
5
1
9
5
-1
10
2
-1
11
2
6
12
4
7
13
9
10
14
9
9
15
7
8
16
7
13
17
6
16
-- Quem faz Computação e está matriculado em MC202 ?
 Busca binária no arquivo de chaves secundárias CURSO + percorrer lista invertida:
Registros com chaves primárias: 9
4
3
1

 Busca binária no arquivo de chaves secundárias MC202 + percorrer lista invertida:
Registros com chaves primárias: 6 7 9 2
Resposta:
9
Registro de chave primária 9
Zedna P.
Computação
MC202 MC920