Cap. 5: Armazenamento de registros e Organização de Arquivos 5.1. Tipos de armazenamento 5.2....

Cap. 5: Armazenamento de registros e Organização de Arquivos

5.1. Tipos de armazenamento

5.2. Dispositivos de armazenamento secundário

5.3. Acesso paralelizado: tecnologia RAID

5.4. Buferização (cache) de blocos

5.5. Alocação de registros de arquivo em disco

5.6. Operações em arquivos

• Organizações de arquivos

5.7. Arquivos não ordenados

5.8. Arquivos ordenados

5.9. Técnicas de “hashing”

5.1. Tipos de Armazenamento

• Memória primária

– Memória principal (DRAM) e cache (RAM)

– acesso muito rápido

– capacidade limitada

– Volátil

• Memória secundária

– Discos magnéticos ou óticos, fitas

– acesso mais lento

– maior capacidade

– Não volátil

Obs: dados em memória secundária não podem ser processados pela UCP (devem ser antes transferidos para a memória primária)

Armazenamento de Bancos de Dados

Por que em memória secundária (discos)?

• Volume de dados armazenados é grande demais para ficar em memória

• Bancos de Dados devem ser persistentes

(a memória primária é volátil)

• Custo de armazenamento/unidade de dados = uma ordem de grandeza (dezenas de vezes) < para discos do que para memória primária.

5.2.Dispositivos de Armazenamento Secundário

Parâmetros característicos de discos magnéticos:

• capacidade = no de superfícies x no de trilhas x setores/trilha x capacidade do setor (alguns megabytes a alguns gigabytes).

• tempo de localização = tempo de busca + retardo rotacional

• tempo de busca (seek time), anunciado pelo fabricante (10 a 60 mseg).

• retardo rotacional ou latência = (1/2) x tempo de rotação (8,33 ms para 3.600 rpm)

• tempo de acesso ao dado = tempo de localização + tempo de transferência de bloco

• tempo de transferência de bloco = B / tr

B = tamanho do bloco

tr = taxa de transferência = capacidade da trilha / tempo de rotação

Hardware de Disco Magnético

trilha

cilindro

spindleatuador

movimento do atuador

braço

cabeças de leitura/gravação

setor(arco de uma trilha}

Superfície, trilha, setor

Discos Magnéticos

• Formatação lógica: blocos de 512 a 4096 bytes.

• Tempo de transferência bem menor que o tempo de busca e o retardo rotacional.

• Tempo total de acesso aos dados da ordem de milisegundos; tempo de processamento na memória principal da ordem de microsegundos.

• Objetivo das estruturas de arquivos:

minimizar o número de acessos a disco

Dispositivos de Armazenamento

Novas tecnologias:

• Discos óticos

– Tipo WORM (Write Once Read Many)

– Exemplo : CD-ROM

Trilha única em alto/baixo relevo (“pits” e “lands”)

– 270.000 setores de 2 KB (527 MB úteis)

– Taxa de transferência 75 setores/seg = 150 KB/seg

• Discos magneto-óticos

– Permitem escrever várias vezes

– Possuem densidade muito maior do que discos magnéticos

– Tendem a substituir os disquetes magnéticos.

5.3. Acesso paralelizado: tecnologia RAID

• RAID = Redundant Array of Independent Disks

• Arquivo particionado nos vários discos

• Particionamento transparente

• Acesso em paralelo

5.4. Buferização (cache) de blocos

• Reduzir acessos a disco

• Possibilita a execução concorrente de tarefas

• E/S de um bloco concorre com processamento de outro bloco

• Dupla buferização:– Possibilita leitura antecipada de blocos contíguos

– Escrita retardada de blocos contíguos

5.5. Alocação de registros de arquivo em disco

Registros, Campos, Tipos de Dados

Registros

• entidades, seus atributos e relacionamentos

• coleção de itens de dados, onde cada item é composto de um ou mais bytes (caracteres) e corresponde a um campo do registro.

Tipo de registro Campo Tipo de dado

type EMPREGADO = record Nome : packed array[1..30] of character;

CPF : packed array [1..11] of character;

Salário : integer;

Profissão : integer;

Departamento : packed array[1..20] of character;

end;

Arquivos, Registros de Tamanho Fixo e Variável

Um arquivo é uma seqüência de registros.

Usualmente, arquivos com registros de tamanho fixo (facilitam o armazenamento e o acesso).

Arquivos com registros de tamanho variável

• campos com tamanho variável;

• campos com múltiplos valores;

• campos opcionais;

• registros de diferentes tipos.

Registros de tamanho variável podem ser representados como registros de tamanho fixo, porém com desperdício de espaço.

Algumas Formas de Armazenamento de Registros

Nome CPF

Salário Profissão

Departamento

1 31 42 46 50 69

Maria Silva 12345678900 xxxx xxxx Pessoal caracter separador

1 13 24 28 32 39

Nome=Maria Silva CPF=12345678900 Departamento=Pessoal

1 18 34 54

= separador de nome de campo / valor

separador de campo

separador de registro

registro de tamanho fixo

registros com campos de tamanho variável

Blocagem de Registros

Fator de Blocagem

bfr = B / R registros por bloco,

onde B é o tamanho do bloco e R o tamanho do registro em bytes. Exemplo : bfr = 512 / 69 = 7

Espaço não usado em cada bloco

(B - bfr x R) bytes. Exemplo : 512 - 7 x 69 = 29

Razões para blocagem de registros:

• reduz o número de operações de transferência de dados entre memórias secundária e primária;

• reduz o número de intervalos entre blocos (“interblock gaps”), aumentando, em conseqüência o uso do espaço do disco.

Organização Espalhada e Não Espalhada

registro 1 registro 2 registro 3

registro 4 registro 5 registro 6

registro 1 registro 2 registro 3 registro 4 p

reg. 4 pregistro 5 registro 6 registro 7

bloco i

bloco i+1

bloco i+1

bloco i

organização não espalhada (“unspanned”)(usual para registros de tamanho fixo)

organização espalhada (“spanned”)

OBS: Quando o tamanho do registro é maior que o tamanho do bloco ( R > B), a organização espalhada é obrigatória.

Alocação de Blocos de Arquivo em Disco

Alocação contígua:

• blocos de arquivos em blocos consecutivos de disco;

• leitura do arquivo inteiro muito rápida, mas expansão difícil.

Alocação encadeada:

• cada bloco de arquivo contém um ponteiro para o próximo bloco de arquivo;

• fácil expansão, mas leitura do arquivo inteiro muito lenta.

Combinações das duas técnicas:

• Alocação de “clusters” de blocos de discos consecutivos, também chamados segmentos ou “extents”, que são então encadeados.

• Alocação indexada, onde um ou mais blocos de índice contêm ponteiros para os blocos de arquivos.

Descritores de Arquivo

Conteúdo do descritor de arquivo (“header”):

• endereços no disco dos blocos de arquivo;

• descrições do formato de registro

– tamanhos de campos;

– ordem dos campos dentro de registros de tamanho fixo não espalhados;

– códigos de tipos de campos, caracteres separadores, códigos de tipos de registros para registros de tamanho variável;

• outras informações complementares.

5.6. Operações em arquivos

Operações registro a registro

• Find (ou Locate)

• Read (ou Get)

• FindNext

• Delete

• Modify

• Insert

Operações em Arquivos

Operações sobre conjuntos:

• FindAll

• FindOrdered

• Reorganize

Operações de controle:

• Open

• Close

Organizações de Arquivos

Organização de arquivo

Estrutura dos dados de um arquivo em registros, blocos e estruturas de acesso.

Método de acesso

grupo de programas que permite a aplicação das operações no arquivo.

Objetivo de uma boa organização de arquivo

executar tão eficientemente quanto possível as operações mais freqüentes.

5.6. Arquivos de Registros não Ordenados

Organização mais simples e básica, inserções de novos registros no fim do arquivo.

Usada quando não se sabe exatamente como os dados serão usados no futuro.

Vantagem:

• Inserção muito eficiente

Desvantagens:

• Busca muito ineficiente (pesquisa seqüencial).

• Deleções causam desperdício de espaço, obrigando a freqüentes reorganizações.

Arquivo relativo: organização não ordenada de registros de comprimento fixo usando blocos não espalhados e alocação contígua, onde o acesso a um registro é feito pela sua posição no arquivo.

5.7.Arquivos de Registros Ordenados

Registros fisicamente ordenados em disco

• campo de ordenação, chave de ordenação do arquivo.

Vantagens:

• Leitura dos registros na ordem dos valores do campo de ordenação extremamente eficiente.

• Achar o registro seguinte na ordem do campo de ordenação usualmente não requer um acesso adicional a bloco.

• Busca baseada no campo de ordenação mais eficiente (pesquisa binária).

Desvantagens:

• Inserção e deleção de registros custosas

• Modificação do valor do campo de ordenação requer deleção e inserção.

Registros do Arquivo de Empregados:campo de ordenação Name

Algumas Opções de Implementação de Inserção e Deleção

• Deleção : usar marcadores de deleção (“deletion bits”) e reorganizar o arquivo periodicamente.

• Inserção :

Arquivo principal ou mestre ordenado.

Arquivo de overflow ou de transações não ordenado.

Novos registros são inseridos no final do arquivo de transações.

Pesquisa binária no arquivo mestre, pesquisa seqüencial no arquivo de transações

Durante reorganização periódica, os dois arquivos são combinados.

• Vantagens? Desvantagens?

5.9.Técnicas de ‘Hashing”

Hashing : Randomização, Aleatorização, Dispersão

h(C)

espaço dos valoresespaço dos endereços

função de hashing

(ex: CPF1.000.000.000

possíveis valores)

(ex: os três últimos dígitos do CPF1.000 posições)

Hashing InternoEstrutura de dados interna a um programa usada para acessar pequenos arquivos temporários com base no valor de um único campo.

Implementação usual : array de registros

CPF Nome Profissão Salário

123456000 456123001234156002

567890998089765999

000001002

998999

... ... ... ...Exemplo:

h(CPF) = CPF mod 1000

Funções de Hashing

Característica desejável: distribuição uniforme, isto é, uma chave qualquer C tem igual chance de “hashear” para qualquer posição.

Algumas funções usuais:

mod (mais usada em geral)

meio do quadrado (usada em tabelas de símbolos)

desdobramento (“folding”)

análise de dígitos

etc.

[V. Lum, P. Yuen, M. Dodd. Key to Address Transform Techniques: a Fundamental Performance Study on Large Existing Formatted Files, Communications of the ACM, 14(4), April 1971]

Tratamento de Colisões

Endereçamento aberto ou linear:

A partir da posição de colisão, procurar uma posição subseqüente vaga.

Encadeamento:

Manter uma lista encadeada de registros de overflow para cada posição no espaço de endereços.

Hashing múltiplo:

Aplicar uma segunda função de hashing quando ocorrer uma colisão. Se ocorrer nova colisão, aplicar endereçamento aberto ou nova função de hashing.

Hashing ExternoHashing para arquivos em disco, registros armazenados em blocos de disco.

Cada bloco ou grupo de blocos é chamado de “bucket”.

Cada “bucket” contém vários “slots”.

0

1

2

M-2

M-1

númerodo bucket

endereço do bloco

Mapeamento de “buckets” em blocos de disco

Buckets de Overflow

340460

ponteiro

321761 91

ponteiro

22 72522

ponteiro

399 89

ponteiro

bucket 0

bucket 1

bucket 2

bucket 9

...

981

182

ponteiro

ponteiro ponteiro

652 ponteiro

ponteiro ponteiro

...

buckets principais

buckets de overflow

Os ponteiros são para registros dentro dos buckets de overflow

Técnicas de Hashing com Expansão Dinâmica de Arquivos

Grande problema dos esquemas de hashing estático: o espaço de endereços é fixo. O tratamento por área de overflow tende a diminuir a eficiência na pesquisa.

Algumas técnicas modernas de hashing que permitem a expansão dinâmica dos arquivos.

- Hashing Dinâmico

- Hashing Extensível

- Hashing Linear

BUCKETS COM DADOS

Hashing Dinâmico

nó interno

nó folhaDIRETÓRIO

0

1

BUCKETS COM DADOS

Hashing Dinâmico

nó interno

nó folhaDIRETÓRIO

0

0

1

BUCKETS COM DADOS

1

Hashing Dinâmico

nó interno

nó folhaDIRETÓRIO

0

0

1

BUCKETS COM DADOS

1 0

1

Hashing Dinâmico

nó interno

nó folhaDIRETÓRIO

0

1

0

0

1

1

BUCKETS COM DADOS

0

1

Hashing Dinâmico

nó interno

nó folhaDIRETÓRIO

0

1

0

0

0

0

1

1

1

1

BUCKETS COM DADOS

Hashing Dinâmico

BUCKETS COM DADOS

d’=0

DIRETÓRIO

Hashing Extensível

BUCKETS COM DADOS

d’=1

d’=1

01

DIRETÓRIO

d = 1

Hashing Extensível

BUCKETS COM DADOS

d’=2

d’=1

00011011

DIRETÓRIO

d = 2

d’=2

Hashing Extensível

BUCKETS COM DADOS

d’=2

d’=2

00011011

DIRETÓRIO

d = 2

d’=2

d’=2

Hashing Extensível

BUCKETS COM DADOS

d’=3

d’=3

d’=2

d’=2

d’=2

000001010011100101110111

DIRETÓRIO

d = 3

Hashing Extensível

BUCKETS COM DADOS

d’=3

d’=3

d’=2

d’=2

d’=3

d’=3

000001010011100101110111

DIRETÓRIO

d = 3

Hashing Extensível

Hashing Extensível

• Vantagens– Desempenho não se degrada

– Buckets adicionais alocados quando necessário

– Reorganizações são pequenas (exceto quando diretório é duplicado ou dividido)

• Desvantagem– Necessidade de consulta prévia ao diretório

0

1

10

11

8

13h0 = C mod 2

n (limite inf. p/ h0) = 0

Hashing LinearM (numero de buckets base) = 2

0

1

10

11

8

13

21 overflow

h0 = C mod 2

n = 0

Hashing LinearM = 2

0

1

10

11

8

1321

2

h0 = C mod 2

h1 = C mod 4 (buckets 0 e 2)

n = 1

Hashing Linear

M = 2

0

1

10

11

8

1321

2h0 = C mod 2

h1 = C mod 4 (buckets 0 e 2)

20

16 overflow

n = 1

Hashing Linear

M = 2

0

1

10

11

8

13

2h1 = C mod 4

2016

3

21

n (limite agora p/ h1)= 0

Hashing Linear

M = 4

0

1

10

11

8

13

2

h1 = C mod 4

2016

3

21

12 overflow

n = 0

Hashing Linear

0

1

10

11

8

13

2

h1 = C mod 4

20

16

3

21

4

h2 = C mod 8 (buckets 0 e 4)

12

n = 1

Hashing Linear

0

1

10

11

8

13

2

h1 = C mod 4

20

16

3

21

4

h2 = C mod 8 (buckets 0 e 4)

12

24

5

n = 2

h2 = C mod 8 (buckets 1 e 5)

Hashing LinearM = 4

Hashing Linear

• Vantagens– Expansão e redução dinâmica do número de

buckets

– Não precisa de diretório

– Redistribuição eventual do overflow

• Desvantagem– Overflow ainda necessário

• Obs: possibilidade de divisão ou combinação segundo o fator de carga

Outras Organizações

• Registros Mistos– Agrupamento de registros relacionados

– Contigüidade ou ponteiros físicos X referências lógicas

– Usual em SGBDs objetos (e SGBDs legados)

– Necessidade de identificação do tipo de registro

• Árvores-B

• Qualquer estrutura de dados adaptável a dispositivos de armazenamento persistente de dados