Aula 1 - Armazenamento de dados, indexação e processamento de consultas

Prévia do material em texto

Armazenamento de Dados
Armazenamento primário: 
Inclui mídias de armazenamento que podem ser operadas diretamente pela CPU, tais como memória principal e memórias cache.
Geralmente fornece acesso rápido aos dados, mas sua capacidade é limitada.
Armazenamento secundário e terciário:
Não podem ser processados diretamente pela CPU.
Inclui discos magnéticos, discos ópticos e fitas.
Maior capacidade, menor custo e acesso mais lento do que os dispositivos de armazenamento primário.
Agenda
1. Armazenamento de dados
2. Estruturas básicas em arquivos
3. Técnicas de Hashing
4. Estruturas de indexação
5. Processamento de Consultas
Técnicas de Hashing
Conceitos:
Campo de hash: o campo que possui a condição de pesquisa.
Chave de hash: quando o campo de hash também é um campo-chave do arquivo.
Função de hash: o valor do campo de hash de um registro deve gerar o endereço do bloco de disco em que o registro está armazenado.
Pode ser de dois tipos: Hashing interno e Hashing externo.
Armazenamento de Dados
Hierarquia de memórias
Armazenamento de Dados
Armazenamento: 
Os dados armazenados no disco são organizados como arquivos de registros.
Organização primárias de arquivos: 
Arquivo de heap (ou arquivo desordenado)
Arquivo sorted (ou arquivo ordenado)
Arquivo hashed (chave de hash)
Organização secundárias de arquivos:
Índices
Figura 1 (a) Um disco de face única com hardware de leitura/escrita.
 (b) Um conjunto de discos com hardware de leitura/escrita.
Armazenamento de Dados
Disco rígido:
Figura 2 Diferentes organizações de setor em disco. (a) Setores formados por 
 um ângulo fixo. (b) Setores que mantêm uma densidade uniforme 
 de gravação.
Armazenamento de Dados
Disco rígido:
Armazenamento de Dados
Disco rígido:
A transferência de dados entre a MP e o disco se dá em unidades de blocos de disco.
O tempo total necessário para localizar e transferir um bloco é a soma do tempo de busca, do atraso rotacional e do tempo de transferência do bloco.
Localizar dados no disco é o maior gargalo em aplicações de BD.
Colocar “informações relacionadas” em blocos contíguos é o objetivo básico de qualquer organização de armazenamento no disco.
Armazenamento de Dados
Fitas magnéticas: 
Acesso sequencial: para acessar o n-ésimo bloco na fita, devemos primeiro percorrer os n-1 blocos precedentes.
O acesso à fita pode ser lento (off-line).
Principal função: backup do BD para evitar disk crash.
Armazenamento de Dados
Buffering de blocos:
Diversos buffers podem ser reservados na MP para acelerar a transferência de blocos de disco para a MP.
Enquanto um buffer estiver sendo lido ou escrito, a CPU pode processar os dados em outro buffer.
Elimina o tempo de busca e o atraso rotacional para a transferência de todos os blocos, exceto o primeiro.
Figura 3 Uso de dois buffers, A e B, para ler o disco.
Figura 13.5 Três formatos de armazenamento de registro. (a) Registro de 
 tamanho fixo com seis campos e tamanho de 71 bytes. (b) Um 
 registro com dois campos de tamanho variável e três campos de 
 tamanho fixo. (c) Um registro de tamanho variável com três tipos de 
 caracteres separadores.
Estruturas básicas em arquivos
Registros:
Estruturas básicas em arquivos
Registros:
Não-spanned: registros não podem atravessar as fronteiras dos blocos (tamanho fixo)
Spanned: registros podem se fragmentar por mais de um bloco (ponteiros)
Fator de blocagem: fb = | B / R |, registros por bloco
Figura 6 Tipos de organização de registro. (a) Não-spanned. (b) Spanned.
Estruturas básicas em arquivos
Arquivos de registros desordenados (heap files)
Os registros são arquivados na ordem em que são inseridos ao final do arquivo.
O último bloco de disco do arquivo é copiado no buffer, o novo registro é acrescentado e o bloco é reescrito no disco.
A pesquisa por um registro, usando qualquer condição, envolve uma pesquisa linear (sequencial) bloco a bloco do arquivo.
Estruturas básicas em arquivos
Arquivos de registros desordenados (heap files)
Para um arquivo com b blocos, isso implica pesquisar (b/2) blocos, em média.
Para excluir um registro, um programa deve primeiro encontrar o seu bloco, copiá-lo em um buffer, excluir o registro do buffer e, finalmente, reescrever o bloco de volta no disco.
A exclusão de um grande número de registros resulta em desperdício de espaço de armazenamento.
Estruturas básicas em arquivos
Arquivos de registros ordenados (sorted files)
Podemos ordenar fisicamente os registros de um arquivo em um disco a partir dos valores de um de seus campos – chamados campos de classificação.
O uso de uma condição de pesquisa baseada num campo chave de classificação resulta em acesso mais rápido quando a técnica de pesquisa binária é usada.
Uma pesquisa binária geralmente acessa log2(b) blocos.
Estruturas básicas em arquivos
Arquivos de registros ordenados: Pesquisa Binária
Estruturas básicas em arquivos
Figura 7 Alguns blocos de um arquivo ordenado (sequencial) de registros 
 de EMPREGADO tendo NOME como campo-chave de classificação.
Estruturas básicas em arquivos
Arquivos de registros ordenados (sorted files)
A inclusão e a exclusão de registros são operações dispendiosas para um arquivo ordenado.
Uma opção para tornar a inclusão mais eficiente é manter alguns espaços não utilizados em cada bloco para novos registros.
Um outro método frequentemente utilizado é criar um arquivo desordenado temporário (arquivo de overflow).
Modificar um campo de classificação requer a exclusão do registro antigo, seguinda pela inserção do registro modificado.
Técnicas de Hashing
Hashing interno
Implementado por uma tabela hash, por meio do uso de um vetor de registros.
Índices do vetor deve possuir valor inteiro entre 0 e M-1 posições.
Uma função hash típica: h(K) = K mod M, onde:
K: campo de hash inteiro
M: n° de posições
Para cadeias de caracteres, os códigos numéricos (ASC II) associados aos caracteres podem ser usados na transformação.
Outras funções de hashing podem ser usadas.
Figura 8 Estruturas de dados de hashing interno. (a) Vetor de M posições 
 para uso em hashing interno. (b) Resolução de colisão por meio 
 do encadeamento de registros.
Técnicas de Hashing
Hashing interno
Técnicas de Hashing
Hashing interno
Uma colisão ocorre quando o valor do campo de hash de um registro que está sendo inserido é calculado como um endereço que já contém um registro diferente.
Existem vários métodos para a resolução de colisão:
Endereçamento aberto
Encadeamento
Hashing múltiplo
Estudos de análise mostraram que normalmente é melhor manter uma tabela de hash entre 70 e 90 por cento cheia.
Também pode ser útil escolher um n° primo para M.
Técnicas de Hashing
Hashing externo
Implementado por buckets, cada qual mantendo múltiplos registros.
A função hash mapeia uma chave à um n° de bucket.
Uma tabela mantida no cabeçalho do arquivo converte o número do bucket para o endereço do bloco de disco.
Figura 9 Correspondência entre números de bucket e endereços de blocos de disco.
Figura 10 Tratamento de overflow em buckets por encadeamento.
Técnicas de Hashing
Hashing externo
Estruturas de indexação
Índice primário:
Índice cuja chave especifica a ordem sequencial do arquivo.
Características:
Esparso
Ancoragem de bloco
n° de E/I = n° de blocos no arquivos de dados
Estruturas de indexação
Índice clustering:
Baseado no campo de ordenação não-chave de um arquivo.
É um arquivo ordenado cujos registros contêmdois campos:
O 1º é do mesmo tipo de dado do campo clustering do arquivo de dados.
O 2 º é um ponteiro para um bloco de disco.
Estruturas de indexação
Índice secundário:
Índice cuja chave não é aquela da ordem sequencial do arquivo.
Dois casos:
O campo de indexação é um campo chave (às vezes chamado de chave secundária).
O campo de indexação não é chave.
Índice denso.
Estruturas de indexação
Índice secundário:
Resumo
Estruturas de indexação
Resumo
Estruturas de indexação
Estruturas de indexação
Índice multiníveis:
Num índice multinível a idéia é reduzir a parte do arquivo de índice.
Primeiro Nível - arquivo ordenado com um valor distinto para cada K(i).
Outros Níveis - índice primário sobre o índice do nível anterior e assim sucessivamente até que no último nível o índice ocupe apenas um bloco.
Geralmente utiliza Árvores-B e Árvores B+ por manter a eficiência na inserção ou remoção de dados.
Estruturas de indexação
Índice multiníveis:
Estruturas de indexação
Índices no MySQL:
Sintaxe:
CREATE [UNIQUE | FULLTEXT] INDEX nome_índice 
	[USING BTREE | HASH]
	ON nome_tabela (campo_de_índice, …);
DROP INDEX nome_índice ON nome_tabela;
SHOW INDEX FROM nome_tabela;
Ex: CREATE UNIQUE INDEX indice1 ON Funcionario (Cpf);
Referências
ELMASRI, R.; NAVATHE, S. B. Sistemas de Banco de Dados. 6ª ed., Addison Wesley, 2010.
MySQL – Manual de Referência do MySQL 4.1. Disponível em:
http://downloads.mysql.com/docs/refman-4.1-pt.pdf
Página da disciplina de BDII: http://goo.gl/5WRHnr