Universidade Federal do Pará

Centro de Ciências Exatas e Naturais

Departamento de Informática

Disciplina: Estrutura de Dados II

Prof.: Sampaio

Arquivo Direto

Por:

Sebastião Farias Júnior Mat.:9908803801

Ricardo Souza Mat.:9908801101

1- Arquivo Direto» Consiste na instalação dos registros em determinados endereços, baseados no valor de uma chave primária, ao contrário do arquivo indexado que utiliza uma estrutura auxiliar(índice) »Utiliza uma função que calcula o endereço de um registro, eliminando a necessidade de um índice»Objetivo principal é o mesmo do arquivo indexado, que é obter acesso aleatório eficiente

Representação de acesso a um arquivo direto.

argumento 1 1100 ANTONIO 34 1700

2 1335 JOSE 27 800

3 1787 ADEMAR 43 2327 4 3255 PEREIRA 25 2005x=‘JOSE’ E=2 5 3553 MARIA 29 1500

x:chave primária

E=f(x)

NÚMERO NOME IDADE SALÁRIO

2 - Cálculo do endereço.

-Funções Determinísticas: associa um único valor da chave de acesso a cada endereço.

-Funções Probabilísticas: geram para cada valor da chave primária um endereço ”tão único quanto possível”.

F(x)=[(x - 900) / 61] +1

Número Endereço Número Endereço1000 2 1400 91050 3 1440 91075 3 1480 101100 4 1600 121300 7 1700 141350 8 1800 15

Número Nome Idade Elo

1000 Jose 25

1050 Fernanda 32 41100 Pamela 27

1075 Anderson 19

1300 Antonio 33

1350 Vanessa 21

1400 Valéria 18

1

2

3

4

5

6

7

8

Tabelas de dispersão.

Métodos:

-Método da divisão.

4

5

6

7

8

Endereço= (chave mod 4)

0

1

3

2

Chave Endereço

-Método da separação.

71 = 00010¦00111

00010 xor

00111

00101 = 5

logo f(x)=5

-Método da multiplicação.

f(x)=71*n

ex.:n=2

0001000111

00010001110=14

logo f(x)=14

-Método da dobra (soma dos pares).

5 6|3 9|0 2

9 4|0 2

4 1

logo f(x)=41

3 - Tratamento de colisões - Aspecto mais importante na organização de arquivos direto.

- Conseqüência do uso de funções não determinísticas.

- Ocorre quando a dois valores diferentes da chave de acesso é atribuídos o mesmo endereço.

- Soluções: endereçamento aberto e encadeado.

Função Coincidindo endereço

4

5

6

7

8

Endereço= (chave mod 4)

0

1

3

2

Chave Endereço

3.1 - Tratamento por endereçamento aberto:

- Ao ocorrer uma colisão em uma operação de inserção, é feita uma busca sobre o arquivo para localização de um endereço livre.

- Métodos de busca: pesquisa seqüencial, pesquisa no bloco, realeatorização.

01

10

00

02

15

10

01

00

02

Chave Endereço

04

15

06

07

0

7

X mod 5

3.2 - Tratamento por encadeamento

- Todos ou parte dos registros que colidem em um endereço gerado são juntados(organizados) em uma lista de encadeada.

- Meios de organização: utilização de encadeamento puro e áreas de extensão.

01

10

03

06

19

00 15

X mod 5

Exterior/Puro

01

10

03

00

05

15

07X mod 5

Interior/Extensão

09

4- Operações:

4.1 - Acesso a um registro

- Acesso serial: uso de uma função de cálculo de endereço que preserva a ordem dos registros pelo valor da chave de acesso.

Exemplo

- Acesso Aleatório: Uso de uma função de cálculo de endereço ao argumento de pesquisa C, obtendo-se o endereço E=F(C).

01

10

03

06

19

00 15

X mod 5

4.2 - Inserção de um registro

-A função de cálculo de endereço (F) é aplicada à chave C do registro a ser inserido, resultando o endereço E=F(C).

- Se houver colisões, utiliza-se um dos métodos de tratamento de colisão citados anteriormente

4.3 - Remoção de um registro

- Acessa o registro que se quer excluir, se

necessário é colocado o valor “excluído” no seu

campo de estado. Caso esteja encadeado em alguma

lista de colisão, pode ser dela removido, ou não.

4.4-Alteração de um registro• Se a alteração não mudar o valor da chave de acesso nem aumentar o comprimento do registro, este é simplesmente lido, alterado e gravado no mesmo endereço

• Caso contrário, o registro é excluído, alterado e novamente inserido, de acordo com a operação de inserção em arquivos diretos

1800 Laura 6500

1100 Antônio 15001800 Laura 7500

2950 Sandra 1100

1

2

3

Argumentode Pesquisa

C=Laura

Número Nome Salário

E=F(C)

E=2

4.5 - Leitura exaustiva - É efetivada pela aplicação sucessiva da operação de acesso a um registro.

4.6 - Reorganização do arquivo

- Efetuada periodicamente por motivos de eficiência de acesso.

- Áreas de extensão: reagrupa os registros de uma mesma lista em posições contíguas da área.

- Encadeamento puro: reagrupamento dos registros de cada lista em posições tão próximas quanto possível.

FIM!