04_organizacao

Prévia do material em texto

Ramon Gomes Costa, Prof. D.Sc.
Aula Expositiva
Organização de arquivosOrganização de arquivos
Banco de Dados II 2
Plano de Curso
 Organização de arquivos
 Introdução
 Registros de arquivo e operações
 Arquivos de registros desordenados (heap)
 Arquivos de registros ordenados (sequencial)
 Arquivos de registros diretos (hashing)
 Hashing interno
 Hashing externo
 Exercícios. 
Banco de Dados II 3
Introdução
 Bancos de dados são armazenados fisicamente como arquivos de registro.
 Ex.:
 Os bancos de dados do MySQL são armazenados (por padrão) dentro do diretório 
“/var/lib/mysql”. Ao criar um banco de dados (por exemplo: agenda), será criado o 
diretório “/var/lib/mysql/agenda”, contendo os arquivos referentes às tabelas criadas 
para este banco de dados.
 O MySQL utiliza três tipos de arquivo para armazenar as informações sobre os 
Bancos de dados do tipo MyISAM;
 Cada arquivo se inicia com o nome do banco de dados, seguido de sua extensão 
(.frm, .MYD, .MYI), que indica o tipo do arquivo.
 Arquivos de extensão .frm: armazena a estrutura do banco de dados;
 Arquivos de extensão .MYD: armazena os dados povoados;
 Arquivos de extensão .MYI: armazena os índices do banco de dados;
Banco de Dados II 4
Introdução
 A forma como os dados são armazenados e recuperados está implementada em um 
mecanismo de armazenamento do SGBD chamado “Storage Engine”.
 Ex.: Storage Engines do MySQL.
 Caso o mecanismo de armazenamento (storage engine) seja omitido, o tipo padrão 
(aquele que será utilizado) dependerá da versão do MySQL:
 MyISAM – Em versões anteriores ao MySQL 5.5
 InnoDB – A partir da versão MySQL 5.5
 Portanto, a sintaxe abaixo, pode ser armazenada de forma diferente, dependendo da 
versão do SGBD que está sendo utilizado:
CREATE TABLE Agenda (
nome VARCHAR PRIMARY_KEY,
endereco VARCHAR 
);
 Aconselha-se informar o tipo de tabela:
CREATE TABLE Agenda (
nome VARCHAR PRIMARY_KEY,
endereco VARCHAR
) ENGINE = InnoDB;
Banco de Dados II 5
Registros de arquivo e operações
 Registros e tipos de registro
 Os dados costumam ser armazenados na forma de registros. O tipo de dado de um 
campo normalmente é um dos tipos de dado padrão usados na programação. Ex.:
struct funcionario {
char nome[30];
char cpf[9];
int salario;
int cod_cargo;
char departamento[20];
};
struct funcionario tabela_funcionario[100];
 Obs.: Pode-se utilizar ponteiros para itens de dados, tais como campos BLOB (Binary 
Long Object).
 <anexo: alocação de memória>
(Registro usando a linguagem C)
Banco de Dados II 6
Registros de arquivo e operações
 Um arquivo é uma sequência de registros. 
 Geralmente, todos os registros em um arquivo são do mesmo tipo.
 Os arquivos podem ser compostos por:
 Registros de tamanho fixo - se cada registro no arquivo tem exatamente o mesmo 
tamanho (em bytes).
 Registros de tamanho variável - se diferentes registros no arquivo possuem diversos 
tamanhos.
Banco de Dados II 7
Registros de arquivo e operações
 Um arquivo pode ter registros de tamanho variável por vários motivos:
 Registros do arquivo são do mesmo tipo, mas alguns campos têm tamanho variável. 
Ex.: campos que utilizam caractere separador ('\0').
Nome varchar(35)
Banco de Dados II 8
Registros de arquivo e operações
 Um arquivo pode ter registros de tamanho variável por vários motivos:
 Registros do arquivo são do mesmo tipo, mas alguns campos têm tamanho variável. 
Ex.: campos que utilizam caractere separador ('\0').
Nome varchar(35)
 Registros do arquivo são do mesmo tipo, mas um ou mais campos são multivalorados. 
Ex.: campos que utilizam mapeamento chave/valor.
Table_priv set('Select','Insert','Update','Delete','Create','Drop',...) 
 Registros do arquivo são do mesmo tipo, mas alguns campos são opcionais. Ex.: 
campos que podem não conter valor associado.
Salario int default null
 
 Arquivo contém registros de tipos diferentes (arquivo misto).
Banco de Dados II 9
Registros de arquivo e operações
 Como um bloco é a unidade de transferência de dados entre o disco e a memória, deve-
se ter uma estratégia que otimize a alocação de Registros em Blocos de disco. 
 Seja,
B: tamanho do Bloco (em Bytes),
R: tamanho do Registro de tamanho fixo (em Bytes), e
bfr: fator de blocagem (quantidade de Registros que cabem em um Bloco).
 Para B>R, podemos estabelecer que:
 
 Em geral, R pode não dividir B exatamente. Logo, podemos estabelecer :
bfr=⌊B
R
⌋
espaçonãousado=B−(bfr×R)
Organização de registros não espalhada
Banco de Dados II 10
Registros de arquivo e operações
 Como um bloco é a unidade de transferência de dados entre o disco e a memória, deve-
se ter uma estratégia que otimize a alocação de Registros em Blocos de disco. 
 Para aproveitar espaços não usados, podemos armazenar parte de um registro em 
um bloco e o restante em outro, usando ponteiros caso não seja o próximo bloco no 
disco.
 Seja,
r: número de registros em um arquivo,
bfr: fator de blocagem (número médio de registros por Bloco),
b: número de blocos necessários.
 Podemos estabelecer que:
 
Organização de registros espalhada
b=⌈ r
bfr
⌉
Banco de Dados II 11
Registros de arquivo e operações
 Operações em arquivos costumam ser agrupadas em operações de recuperação e 
de atualização.
 Quando vários registros satisfazem uma condição de pesquisa, o primeiro registro 
(sequência física) é designado como registro atual. Buscas subsequentes localizam o 
próximo registro (cursor).
 Organização de arquivo: organização dos dados em um arquivo de registros, bloco e 
estruturas de acesso.
 Método de acesso: grupo de operações que podem ser aplicadas a um arquivo.
 O objetivo de uma boa organização de arquivo é utilizar um método de acesso para 
localizar o bloco que contém um registro desejado com um número mínimo de 
transferências de bloco.
Banco de Dados II 12
Registros de arquivo e operações
 Operações em arquivos (descrição simplificada)
 Open:
 Prepara arquivo para leitura/escrita;
 Aloca buffer;
 Define ponteiro para o primeiro bloco referente ao arquivo.
 Reset:
 Define o ponteiro para o primeiro bloco referente ao arquivo.
 Close:
 Libera o buffer.
Banco de Dados II 13
Registros de arquivo e operações
 Operações em arquivos (um registro por vez)
 Find:
 Procura registro ( com base em uma condição);
 Transfere bloco;
 Ponteiro aponta para registro;
 FindNext:
 Procura próximo registro (complemento à Find);
 Ponteiro aponta para o registro;
 Read:
 Copia registro do buffer para variável.
Banco de Dados II 14
Registros de arquivo e operações
 Operações em arquivos (um registro por vez)
 Insert:
 Localiza bloco;
 Transfere bloco para o buffer;
 Grava registro no buffer;
 Grava buffer no disco.
 Delete:
 Localiza bloco;
 Transfere bloco para o buffer;
 Exclui registro do buffer;
 Grava buffer no disco.
 Update:
 Localiza bloco;
 Transfere bloco para o buffer;
 Modifica valor de campo;
 Grava buffer no disco.
Banco de Dados II 15
Registros de arquivo e operações
 Operações em arquivos
 Scan:
 Find, FindeNext e Read.
 FindAll:
 Localiza todos os registros (que satisfazem uma condição).
 Find n:
 Procura registro (com base em uma condição);
 Transfere n registros para o buffer;
 Ponteiro aponta para primeiro registro.
 Find ordered:
 Localiza todos os registros (ordena-os)
 Reorganize:
 Inicia processo de reorganização
Banco de Dados II 16
(Organização de arquivos)
 Até aqui estudamos como registros são representados em uma estrutura dearquivos.
 Relação (tabela) = Arquivo(s) (conjunto de registros)
 Tuplas (linhas) = registros.
 Porém, dado um conjunto de registros, como organizá-los em um ou mais arquivos?
 Algumas opções de organização de arquivos incluem:
 heap: nenhuma ordenação;
 sequencial: ordenados por uma chave de busca;
 hashing: utiliza função hash calculada sobre algum atributo do registro.
Banco de Dados II 17
Arquivos de registros desordenados
 Heap:
 Armazenamento: Registros são arquivados na ordem de inserção.
 Inserção (é eficiente): 
 o último bloco do arquivo é copiado para o buffer → o registro é acrescentado → o 
bloco é regravado no disco.
 Endereço do último bloco é mantido no cabeçalho do arquivo.
 Busca (ineficiente): Pesquisa linear. 
 Normalmente, a heap é utilizada em conjunto com caminhos de acesso adicionais.
Banco de Dados II 18
Arquivos de registros desordenados
 Heap:
 Remoção: 
 (i) Encontrar o bloco → copiá-lo para o buffer → excluir Registro do buffer → gravar o 
bloco no disco.
 Deixa espaço livre no bloco (dead-spaces), resultando em espaços de armazenamento 
desperdiçados.
 (ii) Encontrar o bloco → copiá-lo para o buffer → marcar Registro como excluído no 
buffer → gravar o bloco no disco.
 Utiliza um Byte para definir o Registro como válido ou inválido.
R
eo
rg
an
iz
aç
ão
 p
er
ió
di
ca
Reorganize
Banco de Dados II 19
Arquivos de registros desordenados
 Heap:
 Modificação:
 Registro de tamanho fixo: Encontrar o bloco → copiá-lo para o buffer → modificar 
Registro no buffer → gravar o bloco no disco.
 Registro de tamanho variável: Encontrar o bloco → copiá-lo para o buffer → ? → 
gravar o bloco no disco.
 Se Registro atual <= Registro antigo: modificá-lo no buffer;
 Se Registro atual > Registro antigo: inserir um novo Registro e excluí-lo do buffer.
 Acesso:
 Usando bloco não espalhado e alocação contígua, é simples: seja,
 i: posição do Registro no arquivo.
 bfr: fator de blocagem (quantidade de Registros que cabem em um Bloco).
 j: posição do bloco na sequencia de blocos.
 k: posição do Registros dentro do bloco j.
 Podemos estabelecer que:
j=⌊ i
bfr
⌋; k=i%bfr
Banco de Dados II 20
Arquivos de registros ordenados
 Sequencial:
 Armazenamento: Registros são fisicamente ordenados com base em um campo de 
ordenação.
 Registros são ordenados em blocos e armazenados em cilindros contíguos para 
minimizar o tempo de busca.
Banco de Dados II 21
Arquivos de registros ordenados
 Sequencial:
 Vantagens sobre a heap:
 Leitura dos registros na ordem dos valores da chave de ordenação.
 Geralmente, o próximo registro na ordem da chave está no mesmo bloco.
 Melhor desempenho em busca baseada em um campo chave, em alguns casos.
 Inserção (ineficiente):
 Registros devem ser mantidos ordenados.
 Encontrar Bloco → copiá-lo para o buffer → criar espaço entre Registros → inserir 
novo Registro → gravar bloco no disco.
 Opção 1: manter espaços vagos em blocos / dividir bloco quando cheio.
 Opção 2: manter heap temporária (arquivo de overflow). 
 Reorganização periódica.
 Busca (eficiente, se usa o campo de ordenação): pesquisa binária.
 Pode ser feita em blocos, ao invés de Registros.
 Algoritmo 17.1.
Banco de Dados II 22
Arquivos de registros ordenados
 Sequencial:
 Busca
Banco de Dados II 23
Arquivos de registros ordenados
 Sequencial:
 Remoção: Ineficiente para manter os Registros contíguos. 
 marcador de exclusão pode ser usado.
 Modificação: semelhante a heap, mas:
 Se a busca pelo Registro for pelo:
 Campo de ordenação: pesquisa binária.
 Outro campo: pesquisa linear
 Se a modificação for em um campo de ordenação, o Registro pode ser modificado 
fisicamente.
 Acesso: geralmente feito em conjunto com índices primários ou índices clusterizados.
Banco de Dados II 24
Arquivos de registros diretos
 Arquivos de Hash:
 Armazenamento: Registros são fisicamente armazenados com base no hashing 
(acesso eficiente usando função de transformação), condição de pesquisa sobre um 
campo de hash.
 Função hash (h(k)): função aplicada ao valor de um campo de hash de um um 
Registro, que gera o endereço de bloco de disco (acesso direto).
<paradoxo do aniversário>
<Tratamento de colisões>
Banco de Dados II 25
Arquivos de registros diretos
uint64_t ArrayDesc::getChunkNumber(Coordinates const& pos) const
{
    Dimensions const& dims = _dimensions;
    uint64_t no = 0;
    // The goal here is to produce a good hash function without using array dimension sizes.
    for (size_t i = 0, n = pos.size(); i < n; i++)
    {
       // 1013 is prime number close to 1024. 1024*1024 is assumed to be optimal chunk size for 2­d array.
        no = (no * 1013) ^ ((pos[i] ­ dims[i].getStart()) / dims[i].getChunkInterval());
    }
    return no;
}
 Arquivos de Hash:
 Ex.: SciDB
 Função hash para escolha de nó em um cluster
Banco de Dados II 26
Hashing interno
 Arquivos de Hash Interno: arquivos de hash que cabem na memória principal.
 Array de Registros (de tamanho M).
 Ex.:
 Ex. de função hash comum: h(k) = k mod M, onde
 h(k) nos dá um valor usado para o endereço do Registro.
Banco de Dados II 27
Hashing interno
 Funções hash não garantem (em sua maioria), que valores distintos terão endereços 
de hash distintos.
 Colisão: valores de campo mapeados para um mesmo endereço.
 Resolução de colisão: processo de escolha de um novo endereço para tratar o 
problema da colisão.
 Métodos mais comuns para tratamento de colisão:
 Encadeamento
 Endereçamento aberto (open addressing)
 Hashing múltiplo.
 Para cada um dos casos, haverá uma forma diferente para a busca, inserção, 
remoção, modificação e acesso baseado no hashing.
Banco de Dados II 28
Hashing interno
 Encadeamento: lista de endereços de overflow para cada endereço resultante do 
mapeamento usando a função hash.
 O array é interpretado como vários locais de overflow.
 Cada Registro tem um ponteiro para outro Registro.
Banco de Dados II 29
Hashing interno
 Endereçamento aberto: verifica posição subsequente para inserir Registro.
 Partindo da posição ocupada, verificar a posição subsequente em ordem, até que uma 
posição não usada seja encontrada.
Banco de Dados II 30
Hashing externo
 Hashing Externo: hashing para arquivos de disco.
 Bucket: espaço de armazenamento (relativo), referente a um bloco (absoluto) de 
disco (bloco ou cluster de blocos).
Banco de Dados II 31
Hashing externo
 Arquivos de Hash Externo: arquivos de hash que devem ser alocados em disco.
 O hashing oferece o acesso mais rápido possível para recuperar um registro com 
base no campo de hash.
 Embora os registros não sejam (necessariamente) ordenados, a forma com que 
estes são armazenados, podem impor uma ordem (preservação de ordem). 
 Ex.:
 Usar três bits mais à esquerda como função hash para gerar endereços em um bucket.
 Usar uma chave hash inteira como endereço em um bucket.
Banco de Dados II 32
Hashing externo
 Problemas associados ao hashing estático:
 Número fixo de buckets/Registros;
 Número fixo de Registros sem colisão;
 Em arquivos com um número pequeno de Registros, muitos espaços podem ser 
desperdiçados;
 Em arquivos maiores que o espaço alocado em buckets, longa lista de registros 
de overflow é necessária.
Banco de Dados II 33
Hashing externo
 A organização de arquivos de hash dinâmica permite variar o número de buckets 
apenas com a reorganização localizada.
 Busca por Registros: 
 Eficiente, se utiliza um campo de hash.
 Dispendiosa, se um campo diferente do campo de hash for utilizado(como em um 
arquivo desordenado).
 Remoção de Registros:
 Remoção do Registro no bucket;
 Substituição do Registro removido no bucket por um Registro de overflow.
 Remoção do Registro no overflow.
Banco de Dados II 34
Hashing externo
 Modificação de Registros:
 condição de pesquisa: busca <slide anterior>.
 Campo a ser modificado:
 Campo não hash: modificar.
 Campo de hash: função hash deve ser reavaliada para este Registro.
Banco de Dados II 35
Hashing externo
 Hashing extensível
 O hash extensível usa um tipo de diretório dinâmico (tabela hash) para armazenar um 
array de 2d endereços de buckets, onde d é chamado de profundidade global.
 No diretório, cada Registro contém um ponteiro para um bucket.
 Vários Registros da tabela hash podem apontar para um mesmo bucket.
 d' é chamado de profundidade local (do bucket).
Banco de Dados II 36
Hashing externo
 Hashing extensível
 Resolução de overflow (inserção):
 d' < d:
 um novo bucket é criado;
 o valor da profundidade local é incrementado.
 d' = d:
 a profundidade global é incrementada;
 um novo bucket é criado;
 o valor da profundidade local é incrementado.
 <Exemplo, próximo slide>
 Em uma remoção, Registros de dois buckets podem ser aglomerados em um único bucket 
(ex. critério: quando menos da metade do bucket estiver cheio) e o diretório pode reduzir-se à 
metade.
Banco de Dados II 37
Hashing externo
 Hashing extensível
 Inserção: suponha registros de tamanho fixo e organização não-espalhada. A DDL a 
seguir foi adaptada para este exemplo.
  CREATE TABLE FUNCIONARIO (
  Pnome char(30) NOT NULL,
  Minicial char(1) NOT NULL,
  Unome char(50) NOT NULL,
  Cpf tinyint unsigned NOT NULL,
  Datanasc date NOT NULL,
  Endereco char(60) NOT NULL,
  Sexo enum('m','f') NOT NULL,
  Salario int NOT NULL,
  Cpf_supervisor tinyint unsigned NOT NULL,
  Dnr int unsigned NOT NULL
  ) ENGINE=MyISAM;
Banco de Dados II 38
Hashing externo
 Hashing extensível
 Seja B = 0,5 KB = 512 Bytes
 R = Registro de FUNCIONÁRIO = 155 Bytes
 brf = floor(B/R) = 3 registros por bloco
Banco de Dados II 39
Hashing externo
 Hashing extensível
 Inserção: João, Fernando e Alice.
Banco de Dados II 40
Hashing externo
 Hashing extensível
 Inserção: Jennifer e Ronaldo.
Banco de Dados II 41
Hashing externo
 Hashing extensível
 Inserção: Joice, André e Jorge.
Banco de Dados II 42
Ramon Gomes Costa, Prof. D.Sc.
ramongomescosta@gmail.com
Organização de arquivosOrganização de arquivos
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42