Embed Size (px)
Citation preview
BD I 2015/02 Organização de
Arquivos
Prof. Altigran Soares da Silva IComp/UFAM
Resumo
l Elementos de dados e Campos l Registros l Representação de Endereços de Bloco e de
Registro l Dados e Registros de Tamanho Variável l Modificações em Registros
Elementos de Dados e Campos
Elementos de Dados - Tuplas l Elementos de Dados – Modelo Relacional
CREATE TABLE Product ( pid INT PRIMARY KEY, name CHAR(20), description VARCHAR(200), maker CHAR(10) REFERENCES Company(name))
l Uma tupla é representada por um registro
Elementos de Dados – Objeto l Elementos de Dados – Modelo de Objetos
interface Company { attribute string name; relationship Set<Product> makes
inverse Product::maker; }
l Um objeto é representado com um registro mais um OID (Object Identifier) l Problema: o que fazer com repetições
l Ex: maker
Valores numéricos
l Inteiros: 2 bytes (curto) ou 4 bytes l Ex: 35 é 00000000 00100011
l Real, ponto flutuante l Mantissa de n bits, expoente de m bits
Valores Alfa-numéricos
l Caracteres l Vários esquemas de codificação l Mais popular é o ASCII l Exemplos
l A: 1000001 l a: 1100001 l 5: 0110101 l LF: 0001010
Valores Alfa-Numéricos (2)
l Tamanho fixo – CHAR (n) l Ex: CHAR (8)
l Tamanho variável – VARCHAR (n) l Terminação com “null”
l Ex: VARCHAR (8)
l Tamanho codificado l Ex: VARCHAR (8)
g t a ¤ o ¤ ¤ ¤
g t a o ¤ ¤ ¤ ¤
g t a 4 o ¤ ¤ ¤ ¤
Valores Alfa-Numéricos (3)
L+1 N MySQL
L+2? N? MSSQL
L+4 N+4 PGSQL
N+1 N+1 Livro VARCHAR(n) CHAR(n)
Oracle N L+2?
Outros Tipos
l Boolean l TRUE: 1111 1111 l FALSE: 0000 0000
l Enumeráveis l Ex: VERMELHO → 1, VERDE → 3, AZUL → 2
ROXO → 4
Datas e Tempo
l Datas – Várias opções l Inteiro – nr. de dias desde 1º. de Janeiro de 1900 l 8 caracteres: AAAAMMDD l 7 caracteres: AAAADDD
l Tempo l Inteiro – nr. de segundos desde 00:00:00 l Caracteres: HHMMSSFF
Observações
l Basicamente duas formas de implementação l Itens de tamanho fixo l Itens de tamanho variável
l Em geral, o tamanho é dado no início da representação
l Tipos de dados l Presentes no catálogo – meta dados l Determinam como o padrão de bits deve ser
implementado
Registros
Registros
l Registros l Coleção de de itens de dados
interrelacionados. l Os itens são chamados Campos
l Principais alternativas: l Formato Fixo vs. Formato Variável l Tamanho Fixo vs. Tamanho Variável
Registros de Formato Fixo
l Depende de informação do esquema l Número de campos l Tipo de cada campo l Ordem dentro do registro l Semântica de cada campo
l Esquema na forma de meta-dados l Catálogo ou Dicionário: conjunto dos meta-dados l Armazenado em separado e não com o registro
Exemplo Formato e Tamanho Fixo
l Esquema (1) Mat, inteiro (2) Nome, 10 caracteres
(3) Depart, inteiro l Registros
55 s m i t h 02
83 j o n e s 01
Dados e Registros de Tamanho Variável
Formato Variável
l O próprio registro contêm informação de formato. É auto-descritivo
l Útil para l Registros “esparsos” l Campos passíveis de repetição l Formatos em definição
Exemplo Formato e Tamanho Variável
l Ao invés dos códigos de campo, poderiamos usar strings. l Neste caso elas seriam chamadas TAGS
4 I 5 2 4 S D R O F 46
Nr.
de c
ampo
s Có
digo
de
cam
po
Tipo
(in
teiro
) Có
digo
de
Cam
po
Tipo
(st
ring)
Ta
man
ho d
a st
r.
Campos com repetição
l Opções l Tamanho fixo X Cabeçalho
l Exemplo l Funcionário com um ou mais filhos
3 NFun: José Filho: Maria Filho: Juca
NFun: José Filho: Maria Filho: Juca ¤
Variações – Record Type l Incluir meta-dados no registro
l Ocupam bytes iniciais do registro l Tamanho l “time-stamps”
l Criação, modificação, etc. l Tipo
l Aponta para o esquema do registro no catálogo
5 27 . . . .
Tipo de registro = 5 (ver catálogo)
Tamanho do registro
Formatos Híbridos
l Formatos Híbridos l Uma parte é fixa, outra é variável l Exemplo:
l Todos os funcionários têm matrícula, nome e departamento
l Outros campos variam
25 José Vend 2 apos. Hobby:pesca
Número de campos Que variam
Outros formatos – Exemplos
3 F3 10 F1 5 F2 12 * * *
3 32 5 15 20 F1 F2 F3
Tamanho total
Deslocamentos (offsets)
0 1 2 3 4 5 15 20
Comprimento do próximo campo
NULL - Representação
l NULL pode ser representado como um “valor reservado” l Diferentes representações para diferentes tipos
de dados l Solução ingênua
l Se cabeçalhos forem usados, é possível codificar a ausência do atributo/campo
NULL - Representação
l Se no cabeçalho o campo tem comprimento zero, então ele poderia ser considerado NULL l Problema string de comprimento zero
l Acrescentar um bit para cada campo do cabeçalho que pode assumir NULL
BLOBS l BLOB = Binary Large Objects l Usados para representar:
l Imagens (GIF, JPG); Filmes (MPEG); Áudio; etc. l Armazenamento:
l Seqüências de Blocos l Blocos podem ser contíguos ou encadeados l Podem ser espalhados em vários discos para aumentar a
banda de transferência l Alternativa
l Armazenar os BLOBS em arquivos externos ao BD l Manter um apontador no registro para este arquivo
BLOBS l No BD
l Manutenção das propriedades ACID
l Portabilidade l Controle de Acesso l Melhor gerenciamento l Indexação
l Externo ao BD l Potencialmente mais
eficiente l BD menos carregado l Manipulação externa ao
BD l Se usado para a Web,
cache em separado
Outras técnicas
l Compressão l Dentro do registro l Coleção de registros
l Encriptação
Alocação de Registros em Blocos
Alocando registros em blocos
l (1) Separação de registros l (2) Espalhada vs. Não-espalhada l (3) Agrupamento l (4) Divisão de registros l (5) Sequenciamento l (6) Indireção
Separação de Registros
l Opções l Registros de tamanho fixo l Usar marcadores l Armazenar o comprimento ou offsets dos registos
l Dento de cada registro l No cabeçalho do bloco
R2 R1 R3 l Não espalhada bloco 1 bloco 2 ...
l Espalhada bloco 1 bloco 2
...
R1 R2
R1
R3 R4 R5
R2 R3 (a)
R3 (b) R6 R5 R4 R7
(a)
Alocação Espalhada vs. Não-Espalhada
apontador
Alocação Espalhada vs. Não-Espalhada
l Alocação não espalhada l É muito mais simples l Disperdiça espaço
l Alocação espalhada l Inevitável se tamaho do registro > tamanho do
bloco
Exemplo – Não espalhado l Arquivo
l 106 registros de 2.050 bytes (fixos) l Espaço necessário = 2,05 x 109
l Sistema l Tamanho do bloco = 4096 bytes l Espaço ocupado = 4096 x 106 = 4,10 x 109
l Utilização de 50% l Espaço desperdiçado = 2,05 x 109
bloco 1 bloco 2
2050 bytes livre 2046 2050 bytes livre 2046
R1 R2
Agrupamento l Representação de registros de tipos diferentes no
mesmo bloco l Justificativa: Registros que são frequentemente
acessados em conjunto alocados próximos l Exemplo:
l Conta + Depósitos
Conta C1 DEP D1 DEP D2
Bloco
Agrupamento l Se Q1 é freqüente, o agrupamento é útil l Se Q2 é freqüente, o agrupamento atrapalha
Conta C1 DEP D1 DEP D2
Q1: select NCONTA,CLIENTE,DATA,VALOR from CONTA C, DEPOSITO D where C.NCONTA = D.NCONTA
Q2: select NCONTA,CLIENTE,ENDEREÇO,... from CONTA C
Conta C2 DEP D3 DEP D4
Bloco 1 Bloco 2
Divisão de Registros
l Tipicamente usado para registros de formato híbrido
l Parte fixa em um bloco e parte variável em outro bloco
Bloco deRegistros Fixos
Bloco deRegs. Variáveis
Bloco deRegistros Fixos
R1(a)
R2 (a)
R2(b)
R2(c)
R1(b)
l Ordenação de registros em um arquivo e seus blocos através de uma valor chave
l Arquivos deste tipo são chamados seqüenciais
l Útil sempre que for freqüente o processamento do arquivo na seqüência da chave escolhida
Sequenciamento
Sequenciamento – Opções
R2 R1
R1 R2 ...
Alocação Contígua
Alocação Encadeada
Sequenciamento – Opções
l Área de Overflow
R1 R2 R3 R4 R5
Cabeçalho
R2.1 R1.3 R4.7
Buffers
Endereços Virtuais
l Os SO modernos usam memória virtual l O espaço de endereçamento é maior que a
memória principal l É mantida uma camada de indireção entre
endereços virtuais e endereços reais l A memória principal (física) serve como um cache
dos endereços com mais probabilidade de acesso l Endereços com menos probabilidade de acesso
são armazenados no disco quando a MP enche
Endereços Virtuais (2)
l Blocos transferidos para a memória são chamados de páginas l Acesso a disco: grande latência relativa a taxa de
transferência (throughput) l Tira proveito do princípio da localidade de
referência l Overhead de transferência é amortizado se
considerarmos muitas requisições
Gerência de Buffers (3) l Os SGBDs usam uma estratégia similar à memória
virtual l Buffer: Armazenam blocos de disco na MP l Buffer Pool: Conjunto de buffers
l Gerência de Buffers l Independe do que é feito pelo SO l Pre-carregamento de blocos com probabilidade de uso
futuro l Blocos “pregados” (pinned blocks)
l Blocos essenciais ou frequentemente acessados l Force-Writing
l Forçar a escrita de blocos
Gerência de Buffers (4)
BD
Página: Bloco de Disco
Frane: Espaço Livre
Buffer Pool
Gerência de Buffers (5)
l Quando uma página é requisitada pela 1ª. vez, é colocada num frame livre l pin_count = quantos processos precisam da
página “pregada” l Quando o SGBD escreve na página na
memória, ela é marcada como “suja” l Somente paginas não “pregadas” podem ser
substituídas l Políticas de substituição: LRU, Clock, MRU
Representação de Endereços de Bloco e
de Registro l Como referenciar registros l Várias opções:
l Desde usar o endereço físico até usar indireções
Rx
Indireção
Referência puramente física
l Endereço do Registro = l Endereço do Bloco + Offset no Bloco
l Endereço do bloco = l ID do dispositivo + l Nr. do Cilindro + l Nr. da Trilha + l Nr. do Bloco
Referência totalmente indireta
l Reg ID segue uma codificação de bits qualquer l + Flexibilidade para manipulação: inserção, remoção l - Custo para a manutenção da indireção
Reg ID EndereçoFísico
MAPA
Exemplo: indireção no bloco Cabeçalho
Bloco Espaço Livre
R3
R4
R1 R2
Cabeçalho de Bloco l Informação que descreve o bloco l Disposta no inicio do bloco l Pode conter:
l ID do Arquivo – Identifica a relação ou BD l ID do bloco l Diretório de registros l Apontador para espaço livre l Tipo do bloco – ex. “overflow”, “registro do tipo 4”, etc. l Ponteiro para outros blocos do mesmo tipo l Timestamp
Indireções em Memória l Quando um bloco é trazido para a memória, recebe
um endereço de memória principal l O gerente de buffer usa outra tabela de endereços l Implicação: referências feitas a partir da memória
devem ser refeitas
Endereço em Memória
Endereço Lógico
M1 L1 M2 L2 M3 L3
Referências Transformadas
l Transformação de Referências ou Pointer Swizzling l Processo de substituir referências lógicas ou
físicas por referências de memória l Ainda é necessário acessa a tabela de
tradução, mas as próximas referências são mais rápidas
Referências Transformadas (2)
Disco Bloco 1 Bloco 2
Memória Para a memória
Referência Transformada
Referência Não-transformada
Referências Transformadas (3)
l Automática: l Quando o bloco é lido para a memória, todos os
apontadores que precisam de transformação são transformados
l Sob demanda: l A transformação é feita a primeira vez que a
referência é feita l Sem transformação
l Sempre usar a tabela de tradução de endereços
Referências Transformadas (4)
l Quando os blocos retornam para o disco, a transformação tem de ser desfeita
l Perigo: podem haver referências para estes blocos
l Soluções l “Pregar” (pin) os blocos l Manter uma lista de referência para estes
blocos
Modificações em Registros
Registros: Operações Físicas
l Principais operações que demanda reorganização da estrutura de armazenamento l Remoção l Inserção
l São freqüentes l Demandam mais cuidado quando feitas no
disco
Remoção
l Opções l Remoção física: liberar espaço imediatamente l Remoção lógica: marcar como removido
l Re-uso: pode demandar o encadeamento dos registros marcados como removidos
l Formas de marcar: § Caractere especial § Campo especial § Utilizar um mapa
Remoção: Tradeoffs
l Remoção física: l Qual o custo de mover os registros válidos de tal
forma a liberar o espaço ocupado por registros removidos?
l Remoção lógica: l Quanto de espaço é perdido?
l Registros removidos l Marcas de remoção l Encadeamento dos removidos
Remoção – Indireções
l O que acontece com as referências (apontadores) a um registro quando ele é removido? l Apontadores pendurados (Dangling Pointers)
l Tratamento com Tombstones (Lápides) l Deixar um marca no mapa ou no local onde
estava o registro
Remoção – Indireções (2)
l Tombstones l IDs físicas
Referência
Não pode ser reusado pode ser reusado
Bloco Registro removido
Remoção – Indireções (3)
l Tombstones l Marcar a ausência do registro no mapa de
alocação
ID LOC
7788
mapa
A ID 7788 e a entrada do
mapa não podem ser reusadas
Remoção – Indireções (4)
l Tratamento com IDs l Cada registro armazena um ID l Ao seguir o apontador, verificar se este leva ao
registro correto
377 Reg ID: 377
Remoção – Indireções (5)
l Tratamento com Chaves l Acrescentar um valor de chave ao apontador l Ao seguir o apontador, verificar se este leva à
chave correta
ptr+ chave chave
Inserções l Caso mais simples: arquivo seqüencial
l Inserir novo registro no fim do arquivo l Se houver uma lista de removidos, reaproveitar
espaço l Tratamento especial se os registros são de
tamanho variável l Caso mais complicado: arquivos ordenados
l Deixar espaço disponível na vizinhança da inserção
l Usar área de overflow
Inserções – Questões
l Quanto de espaço livre deve ser deixado por bloco/trilha/cilindro
l O qual freqüente devem ser as reorganização de área de arquivo e de overflow
Organização de Arquivos
Arquivos Não-Ordenados l Chamados de Heap Files l Novos registros inseridos sempre no final do
arquivo. Portanto é bem eficiente l A busca por registros é linear. Isso exige a leitura da
metade dos blocos em média. Isso representa um alto custo.
l A leitura dos registros em uma ordem em particular exige reordenação dos registros. Se o número de registros é grande, a ordenação é em memória secundária (ordenação externa).
Arquivos Ordenados l Chamados Arquivos Seqüenciais. l São mantidos ordenados por um campo de
ordenação. l Inserção tem alto custo.
l Os registros devem ser inseridos na ordem correta. l É comum manter um arquivo auxiliar – chamdo de
overflow ou de transação – somente para receber novas inserções. De tempos em tempos o arquivo principal é reconstruído a partir dele.
l Outra solução é deixar espaço livre nos blocos para futuras inserções
Arquivos Ordenados (2)
l Busca binária pode ser usada para buscar registros pelo campo de ordenação. l Isso requer a carga de log2 blocos l Busca por outro campos é linear
l Varredura (scan) dos registros na ordem do campo de ordenação é bastante eficiente.
Arquivos Ordenados (3) Arquivos Hashing l Os blocos do arquivo são divididos em M buckets de igual
tamanho b0, b1, b2 ....,bM-1 l Tipicamente um bucket corresponde a um bloco ou a número
fixo de blocos l Um dos campos é usado como a chave da função hash l O registro com chave K é armazenado no bucket i=h(K), onde h
é uma função de hashing l Busca usando a chave de hash é muito eficiente. Número de
blocos lidos é O(1). l Colisões ocorrem quando um novo registro deve ser colocado
em um bucket que já esteja cheio. l Pode-se usar um arquivo de overflow l Registros que geram o mesmo código de hash podem ser
encadeados netes arquivo.
Arquivos Hashing (2) Arquivos Hashing (3)
Arquivos Hashing (4) l Para reduzir a ocorrência de overflow deve-se
manter os blocos 70-80% ocupados. l A função de hash h deve distribuir os registros de
forma uniforme entre os buckets l Principais desvantagens:
l Há um número fixo de blocos que podem ser alocados no arquivo de dados.
l Um número grande de registros de overflow degrada a performance
l Acessos ordenados pela chave de hash são muito ineficientes
Modelo de Computação Baseado em E/S
Modelo de Computação Baseada em E/S
l Para algoritmos em memória, a principal preocupação é com tempo de CPU
l Em BDs o tempo é dominado pelos custos de E/S
l Conseqüência: alguns algoritmos precisam ser re-projetos
l Exemplo: ordenação
Exemplo: Ordenação Externa
l Problema: ordenar 1Gb de dados com 1Mb de RAM
l Aplicações em BDs: l Ordenar resultados de consultas (ORDER BY) l Operações de agrupamento l Primeiro passo no método sort-merge para
implementar junções l Remoção de duplicatas l Carga de massa de dados em índices (B+-Tree)
Merge-Sort Externo de 2 vias l Passo 1:
l Ler um bloco, ordená-lo e escrevê-lo l Apenas um buffer é usado
l Passos 2, 3, …, etc.: l Três buffers são usados
Buffers em Memória Principal
Entrada 1
Entrada 2
Saída
Disco Disco
2 6 5 3 1 7 8 4 9 6 2 4 4 3
2 3 6 8 1 4 5 3 4 9 6 2 7 3 4 6 2 4 9 8 7 5 1 3 6 2 5
Passo 0
Passo 1
Arq. Entrada
Seq. 1 bloco
Seq. 2 blocos
Passo 2
Merge-Sort Externo de 2 vias
7 6
6 8 9
5 3
4 4
2
1 2
3
2 3
4 6 6
4 7
8 9
1
5
3
2 9 8
7 4
6 4
2 3
6
3
5 2
1 Seq. 2 blocos
Passo 2
Seq. 4 blocos
Passo 2
Seq. 8 blocos
Disco Memória
Disco Memória
Passo 0
Antes
Depois
. . .
. . .
3
2
8 7
4 9
6
4
8 7
Disco Memória
Disco Memória
Passo 1
Antes
Depois
. . .
.
. .
3
8 7
9
4
4
6 2 9 4
7 8
Disco Memória
Disco Memória
Passo 2
Antes
Depois
2
6 5 3 1
9 8 7 4
6 4 3 2
9
2 3
4 7
8
6 4 1 3
2 5 6
Disco Memória
Disco Memória
Passo 3
Antes
Depois
2
3 2 1
9 8 7 6 4 4 3
5 6
3 2
1 2
4 4
3 5
6 7
6 8 9
9
Merge-Sort Externo de 2 vias l A cada passo ocorrem
l 1 acesso de leitura l 1 acesso de escrita
l Com um arquivo de N blocos temos que o número de passos é:
l Assim o custo total é:
⎡ ⎤ 1log2 += N
⎡ ⎤( )2 12N Nlog +9
3,4 6,2 9,4 8,7 5,6 3,1 2
3,4 5,6 2,6 4,9 7,8 1,3 2
2,3 4,6
4,7 8,9
1,3 5,6 2
2,3 4,4 6,7 8,9
1,2 3,5 6
1,2 2,3 3,4 4,5 6,6 7,8
Merge-Sort Externo Multi-Vias l Para aproveitar melhor a memória, podemos
aumentar o número de buffers processados a cada passo
l Isso é usado para melhorar a performance l Considere
l B: Tamanho do bloco l M: Tamanho da memória disponível l N: Número de registros no arquivo l R: Tamanho de um registro
Merge-Sort Externo Multi-Vias
l Passo 1: l Carregar M bytes na memória e ordenar l Resultado: seqüências de M/R registros
M bytes de memória Disco Disco
. .
. . . .
M/R registros
Merge-Sort Externo Multi-Vias l Passo 2
l Intercalar M/B – 1 seqüências gerando novas seqüências l Resultado: seqüências de M/R (M/B – 1) registros
M bytes de Memória Disco Disco
. .
. . . .
Entrada M/B
Entrada 1
Entrada 2 . . . .
Saída
Merge-Sort Externo Multi-Vias l Passo 3
l Intercalar M/B – 1 seqüências gerando novas seqüências l Resultado: seqüências de M/R (M/B – 1)2 registros
M bytes de Memória Disco Disco
. .
. . . .
Entrada M/B
Entrada 1
Entrada 2 . . . .
Saída
Merge-Sort Externo Multi-Vias l Número de passos:
l Exemplo l B = 4KB, M = 64MB, R = 0,1KB l Passo 1:
l Seqüências de tamanho M/R = 640.000 l Resulta em 640.000 registros ordenados
l Passo 2: l Seqüências maiores por um fator de M/B – 1 = 16.000 l Resulta em 10.240.000.000 = 1010 registros
l Passo 3: l Seqüências maiores por um fator de M/B – 1 = 16.000 l Resulta em 1014 registros
l Quantidade significativa de dados l Pode-se ordenar qualquer coisa em 2 ou 3 passos !
⎡ ⎤⎡ ⎤MNRBM /log1 1/ −+Conclusões
Conclusões
l Existem 10.000.000 de maneiras de organizar os dados no disco
l Qual a melhor? l Fatores a considerar
l Flexibilidade l Complexidade l Utilização de Espaço l Performance
Parâmetros para Análise l Espaço utilizado pelos dados + overhead l Tempo esperado para
l Buscar um registro dado uma chave l Buscar o registro com a próxima chave l Inserir registro l Adicionar registro l Remover registro l Atualizar registro l Ler o arquivo inteiro l Reorganizar o arquivo
