Estrutura de dados - ?· ALOCAÇÃO DE BLOCOS • A alocação contígua, os blocos de arquivo são…

Embed Size (px)

Text of Estrutura de dados - ?· ALOCAÇÃO DE BLOCOS • A alocação contígua, os blocos de arquivo...

ANLISE E PROJETO DE

BANCO DE DADOSESTRUTURAS E

INDEXAOFELIPE G. TORRES

ARQUIVOS

Um arquivo uma sequncia de registros. Em

muitos casos do mesmo tipo.

Se cada registro no arquivo tem exatamente o

mesmo tamanho (em bytes), o arquivo

considerado composto de registro de tamanho

fixo.

Caso contrrio ele chamado de arquivo

composto por registro de tamanho varivel.

ARQUIVOS

Os arquivos de registro so utilizados em larga

escala para a integrao de sistemas.

Para determinar os bytes em um registro em

particular em cada campo, podemos usar

caracteres separadores (%, #, @,|).

Uma opo prtica tambm atribuir um cdigo

curto de tipo de campo.

TIPOS DE ARQUIVOS

BLOCAGEM DE REGISTROS

Os registros de um arquivo precisam ser

alocados a blocos de disco.

Conceitua-se blocos de disco como uma

unidade de transferncia de dados entre o disco

e a memria.

Se um bloco for maior que um registro, o bloco

poder ter um ou mais registros, porm pode

ocorrer de um arquivo ter um registro muito

extenso, que no caiba em um bloco.

BLOCAGEM DE REGISTROS

Para um arquivo de registro de tamanho fixo,

com tamanho de R bytes, sendo:

Pode-se ento estabelecer o fator de blocagem:

tamanho do bloco R

bfr = [B/R]

BLOCAGEM DE REGISTROS

Em geral, R pode no dividir B exatamente, de

modo que temos algum espao no usado em

cada bloco, igual a:

Para no perder-se esse espao vago nos

blocos, pode-se armazenar um registro

parcialmente em blocos distintos.

B (bfr * R) em bytes

BLOCAGEM DE REGISTROS

Um ponteiro no final do primeiro bloco, aponta para o

bloco que contm o restante. Essa organizao

chamada de espalhada porque os registros podem se

espalhar em mais de um bloco.

BLOCAGEM DE REGISTROS

Para registros de tamanho varivel que usam a

organizao espalhada, cada bloco pode

armazenar um nmero diferente de registros.

Para calcular o nmero de blocos b necessrios

para um arquivo de r registros:

b = [(r / brf)] em blocos

ALOCAO DE BLOCOS

A alocao contgua, os blocos de arquivo so

alocados a blocos de disco consecutivos. Esta

alocao tem a leitura do arquivo inteiro. Este

mtodo dificulta a expanso dos arquivos.

A alocao ligada, cada bloco de arquivo

contm um ponteiro para o prximo bloco de

arquivo. Isso facilita a expanso do arquivo mas

deixa a leitura mais lenta.

TCNICAS DE HASHING

Um tipo de organizao de arquivo principal

baseado no hashing, que oferece acesso muito

rpido. Ela chamada de arquivo de hash.

A condio de pesquisa precisa ser uma

condio de igualdade em um nico campo,

chamado campo de hash ou campo-chave

(chave hash).

TCNICAS DE HASHING

A idia por trs do hashing oferecer uma

funo h, chamada de funo de hash ou

funo de randomizao.

Esta funo aplicada ao valor do campo de

hash de um regitro e gera o endereo do bloco

de disco em que o registro est armazenado.

Uma pesquisa pelo registro no bloco pode ser

executada em um buffer da memria principal.

TCNICAS DE HASHING O hashing tambm utilizado como uma

estrutura de pesquisa interna em um programa

que um grupo de registro seja acessado por

uma chave.

HASHING INTERNO

Normalmente o hashing implementado para

arquivos internos uma tabela hash por meio

do uso de um array de registros.

Ento, temos M slots cujos endereos

correspondem aos ndices de array.

A funo hash que reger a alocao de

valores na tabela dever normalizar os valores

em inteiros variando entre 0 e M-1. Exemplo a :

h(K) = K mod M

DESDOBRAMENTO

Os valores de campo de hash no inteiros podem

ser transformados em inteiros antes que a funo

mod seja aplicada.

Uma tcnica, chamada desdobramento, envolve

aplicar uma funo aritmtica, como a adio, ou

uma funo lgica, como o or exclusivo.

Por exemplo, com um hash de 1000 chaves, uma

chave de seis dgitos 235469 pode ser

desdobrada e armazenada no endereo: (235 +

964) mod 1000 = 199.

DESDOBRAMENTO

PROBLEMA DE COLISES

O problema com a maioria das funes de

hashing que elas no garantem que valores

distintos tero endereos de hash distintos.

O motivo que normalmente o nmero de

valores muito maior que o nmero de

endereos.

Uma coliso ocorre quando o valor do campo

de hash de um registro que est sendo inserido

calculado como um endereo que contm um

registro ocupando-o.

RESOLUO DE COLISES

A ao de localizar outra posio chamado de

resoluo de coliso. Existem vrios mtodos

para resoluo de coliso, incluindo:

Endereamento aberto. Partindo da posio

ocupada especificada pelo endereo de hash, o

programa verifica as posies subsequentes

em ordem, at que uma posio no usada seja

encontrada.

RESOLUO DE COLISES

Encadeamento. Para esse mtodo, vrios

locais de overflow so mantidos, normalmente

estendendo o array com uma srie de posies

de overflow.

RESOLUO DE COLISES

Hashing mltiplo. O algoritmo aplica uma

segunda funo hash se a primeira resultar em

uma coliso.

Se houver outra coliso, o programa utiliza o

endereamento aberto ou aplica uma terceira

funo hash e, depois, usa o endereamento

aberto se necessrio.

ESTRUTURA DE INDEXAO

Alm dos hashes existem outras estruturas de

acesso auxiliares, chamadas de ndices, que

so utilizadas para agilizar a recuperao de

registros em resposta a pesquisas.

As estruturas de ndices so arquivos adicionais

que oferecem caminhos de acesso

secundrios.

Formas alternativas de acessar registros sem

afetar o posicionamento fsico dos arquivos de

dados.

ESTRUTURA DE INDEXAO

Alm dos hashes existem outras estruturas de

acesso auxiliares, chamadas de ndices, que

so utilizadas para agilizar a recuperao de

registros em resposta a pesquisas.

As estruturas de ndices so arquivos adicionais

que oferecem caminhos de acesso

secundrios.

Formas alternativas de acessar registros sem

afetar o posicionamento fsico dos arquivos de

dados.