Arquivos Indexados
Vanessa Braganholo
Arquivos de Acesso Direto
Basicamente, duas formas de acesso a um registro:
2
Acesso via cálculo do endereço do registro (hashing)
Acesso via estrutura de dados auxiliar (índice)
Índice
Índice é uma estrutura de dados que serve para localizar registros no arquivo de dados
Cada entrada do índice contém
Valor da chave
Ponteiro para o arquivo de dados
Pode-se pensar então em dois arquivos:
Um de índice
Um de dados
Isso é eficiente?
3
Exemplo de Índice Plano
Arquivo de Índice
CHAVE
PONTEIRO
Arquivo de Dados
COD
NOME
0 3
0 23
JOSE
1 5
2
1 10
MARIO
2 10
1
2 5
ANA
3 15
3
3 15
MARCIA
4 16
5
4 3
JULIO
5 21
6
5 16
BEATRIZ
6 23
4
4
0
6 21
CAMILA
Índice
Se tivermos que percorrer o arquivo de índice sequencialmente para encontrar uma determinada chave, o índice não terá muita utilidade
Pode-se fazer busca um pouco mais eficiente (ex. busca binária), se o arquivo de índice estiver ordenado
Mas mesmo assim isso não é o ideal
Para resolver este problema:
5
os índices não são estruturas sequenciais, e sim hierárquicas os índices não apontam para um registro específico, mas para um bloco de registros (e dentro do bloco é feita busca sequencial) – exige que os registros dentro de um bloco estejam ordenados
Exemplo de Índice Hierárquico
PONT
CHAVE
N
Í
V
E
L
1
PONT
27
PONT
CHAVE
PONT
PONT
21
CHAVE
N
Í
V
E
L
2
PONT
36
COD
NOME
COD
NOME
COD
NOME
COD
NOME
3
MARCIA
21
JOSE
27
JOAO
36
ALICE
15
JULIO
25
MARIO
29
KARLA
39
TATIANA
18
BEATRIZ
26
ANA
33
LARA
45
BRUNO
6
Í
N
D
I
C
E
S
D
A
D
O
S
Hierarquia lembra árvore...
A maioria das estruturas de