Arquivos Indexados

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