Organização de Arquivos
e Indexação
Estruturas de Arquivos

Registros



Forma de organização dos dados
Coleção de campos ou itens relacionados
Tipo de Registro

Coleção de nomes de campos e seus respectivos
tipos de dados
struct Empregado {
char nome[30];
char matricula[6];
int salario;
}
2
Estruturas de Arquivos

Arquivos



Um arquivo é uma seqüência de registros
Quando todos os registros de um arquivo
possuem exatamente o mesmo tamanho em
bytes, o arquivo é dito formado por registros
de tamanho fixo
Se registros diferentes em um arquivo
possuem tamanhos diferentes, o arquivo é
formado por registros de tamanho variável
3
Estruturas de Arquivos

Registros com tamanho variável

Registros de um mesmo tipo de registro




Com um ou mais campos de tamanho variável
Com um ou mais campos multivalorados
Com um ou mais campos opcionais
Registros de diferentes tipos de registro


Arquivos mistos
Exemplos


Registros de alunos com registros de notas
Registros de clientes com registros de pedidos
4
Estruturas de Arquivos
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.
5
Organização de Registros

Divisão de registros em blocos

Bloco



Unidade de transferência de dados entre o disco e
a memória
Geralmente, um bloco possui diversos registros
Fator de blocagem (de divisão em blocos)


B é o tamanho do bloco em bytes
R é o tamanho do registro em bytes
bfr  B R registros
6
Organização de Registros

Divisão de registros em blocos

Espaço não utilizado
B  (bfr  R) bytes

Organização Não-Spanned


Registros de tamanho fixo limitados a apenas um
bloco, onde B >R
Organização Spanned


Registros podem se fragmentar por mais de um bloco
(unidos por ponteiros)
Usada sempre que o registro > bloco
7
Organização de Registros
Figura 13.6
Tipos de organização de registro. (a) Nâo-spanned. (b) Spanned.
8
Alocação de Blocos

Alocação Consecutiva


Alocação Encadeada



Blocos são alocados consecutivamente no
disco
Cada bloco de arquivo contém um ponteiro
para o próximo bloco de arquivo
Facilita expansão, mas torna lenta a leitura do
arquivo inteiro
Clusters

Grupos encadeados de blocos consecutivos
9
Estruturas de Armazenamento

Arquivos de Registros Desordenados





Tipo de organização mais simples e básica
Registros estão posicionados segundo a ordem
pela qual foram inseridos
Novos registros são acrescentados ao final do
arquivo (muito eficiente)
Pesquisa de um registro é seqüencial
(ineficiente)
Chamado arquivo pilha (heap file)

Arquivos seqüenciais
10
Estruturas de Armazenamento

Arquivos de Registros Ordenados




Registros são ordenados fisicamente a partir
dos valores de um campo (campo de
classificação) ou da chave (chave de
classificação)
Novos registros são acrescentados na posição
correta (inclusão é dispendiosa)
Pesquisa pelo campo de classificação é binária
Chamado arquivo ordenado (sorted file)

Arquivos seqüenciais
11
Estruturas de Armazenamento

Hashing




Acesso muito rápido aos registros sob uma
condição de igualdade em um campo (campo
de hash) ou na chave (chave de hash)
Usa função hash que é aplicada no campo de
hash de um registro, gerando o endereço do
bucket (bloco de disco ou cluster de blocos
consecutivos) onde o arquivo está armazenado
A busca dentro do bloco é feita na memória
principal
Chamado arquivo hash (hash file)
12

Hashing
Interno
13
Estruturas de Armazenamento

Hashing Externo
14
15
Índices

Um índice é uma estrutura de acesso
auxiliar usado para aumentar a velocidade
da recuperação de registros na resposta a
certas condições de busca


Independente da estrutura de armazenamento
(não ordenada, ordenada,hashed)
Índice fornecem caminhos de acesso
secundários ou alternativos aos registros
a partir de campos de indexação
previamente definidos
16
Índices

Como encontrar um livro em uma
biblioteca pelo título?

Sem catálogo de títulos


Procurar em todas as estantes
Com catálogo de títulos

Consultar o catálogo de títulos



Fichas em ordem alfabética
Localizar a estante onde se encontra o livro
Pesquisar livro nas prateleiras
17
Índices

Como recuperar os clientes de nome ‘Eduardo’?

Sem índice


Busca seqüencial em todas as linhas da tabela
Com índice no campo ‘nome’

Procurar o valor desejado no índice


Obter um endereço do registro correspondente no arquivo
físico


Valores ordenados no índice, viabilizam busca eficiente
Ponteiro para o bloco de disco que contém o dado desejado
Recuperar o registro

Ler o bloco do disco e recuperar o registro dentro do bloco
18
Tipos de Índices

Índices com chave de busca única






Índice
Índice
Índice
Índice
Índice
primário
clustering
secundário
multinível
multinível dinâmico: B-Trees e B+-Trees
Índices com múltiplas chaves de busca



Índice ordenado em múltiplos atributos
Hashing particionado e grid files
Índices espaciais
19
Tipos de Índices

Índice primário

Especificado sobre a chave de classificação
de um arquivo ordenado de registros


Índice clustering

Especificado sobre o campo de classificação
de um arquivo ordenado de registros


Valores distintos para o campo de classificação
Valores repetidos para o campo de classificação
Índice secundário

Especificado sobre outros campos que não
são os campos ou chave de classificação
20
Tipos de Índices

Densos


Possuem uma entrada no índice para cada
valor do campo de classificação e, portanto,
uma entrada para cada registro do arquivo de
dados
Esparsos (Não-densos)


Possuem entradas no índice para apenas
alguns dos valores do campo de classificação
Os demais são percorridos sequencialmente no
bloco a partir do maior valor que seja menor
ou igual ao campo de classificação
21
Índice primário

Um índice primário é um arquivo ordenado cujos
registros são de tamanho fixo e contêm dois
campos



Existe uma entrada no índice para cada bloco no
disco


Valor da chave de classificação (ordenação)
Apontador para um bloco de disco (endereço do bloco)
Cada entrada contém a chave do primeiro registro
contido no bloco (âncora do bloco)
Índices primários são inerentemente esparsos
22
23
Índice primário

Inclusões e Exclusões



Grande problema para índices primários, pois
precisam manter a ordenação
Alterações causarão a mudança das âncoras
Possível solução



Usar blocos de overflow para evitar o rearranjo na
inclusão
Marcar registros excluídos
Reorganização ocorrerá na reconstrução do índice
24
Índice clustering



Tipo diferente de índice para acelerar a
recuperação quando os registros de um arquivo
são ordenados fisicamente com base em algum
valor que não é chave (não possui valor distinto
para cada registro)
Esse valor é denominado campo de clustering
Precisa existir uma entrada no índice para cada
valor distinto do campo de classificação


O apontador indica o primeiro bloco no qual registros
contendo aquele valor poderão ser encontrados
Índices clustering também são esparsos
25
Figura 14.2 Um índice clustering para o
campo NUM_DEPARTAMENTO, que não é
campo-chave de classificação, de um arquivo
EMPREGADO.
26
Figura 14.3 Um índice clustering com um grupo
(cluster) separado de blocos para cada grupo de
registros que compartilhem o mesmo valor
de campo clustering.
27
Índice Secundário



Um índice secundário provê uma forma
secundária de acesso a um arquivo para o qual
um índice primário já exista
Tanto pode ser referente a uma chave candidata,
quanto a um atributo cujo valor possa se repetir
O índice é um arquivo ordenado com dois
campos



Valor da chave de classificação (ordenação)
Apontador para um bloco de disco (endereço do bloco)
Podem existir diversos índices secundários para o
mesmo arquivo com vários campos de indexação
28
Índice Secundário

Índice para chave secundária (candidata)

Não é possível usar âncoras de bloco, pois o
arquivo não está fisicamente ordenado pela
chave de classificação



Uma entrada no índice para cada registro do
arquivo (índice denso) que pode apontar para o
registro ou bloco
Consome mais espaço em disco e mais tempo de
acesso por causa do maior número de entradas
Caso não existisse o índice secundário, seria
necessário percorrer todo o arquivo
29
Figura 14.4 Um índice secundário denso (com ponteiros de bloco)
em um campo não é chave de classificação de um arquivo.
30
Índice Secundário

Índice para campo que se repete (não-chave)




Opção 1: incluir várias entradas no índice (duplicadas),
uma para cada registro (índice denso)
Opção 2: manter registros de tamanho variável no
índice com um campo multivalorado para armazenar
os ponteiros para cada bloco onde há um registro para
o campo de indexação
Opção 3: manter uma entrada para cada valor distinto,
mas apontar para um bloco contendo ponteiros para
as várias ocorrências do valor no arquivo
A opção 3 é a mais usada!
31
Figura 14.5 Um índice secundário (com ponteiros
de registro), em um campo que não é campo-chave,
implementado em um nível adicional, indireto, de
forma que as entradas de índice sejam de tamanho
fixo e possuam valores de campo únicos.
32
Atualização de Índices

Independente do tipo de índice utilizado,
ele deve ser atualizado sempre que um
registro for inserido ou removido do
arquivo de dados
Inclusão
Exclusão
Localizar o registro
Incluir o registro,
caso não exista
Remover o registro,
caso exista
Atualizar o índice
33
Quando criar índices?

Quando criar um índice


Para acelerar a recuperação dos dados
Para impor exclusividade aos registros


Restrição de chave primária, cria um índice único
Quando não criar um índice


Consome espaço em disco
Acarreta sobrecarga em operações de
atualização (INSERT, UPDATE, DELETE)
34
Quais colunas indexar?





Conhecendo os dados
Determinando a seletividade
Determinando a densidade
Determinando a distribuição de dados
Diretrizes sobre indexação
35
Quais colunas indexar?

Conhecendo os dados





A estrutura física e lógica
As características dos dados
Como os dados são usados
Os tipos de consulta feitos
A freqüência das consultas normalmente feitas
36
Quais colunas indexar?

Determinando a seletividade


Seletividade é o percentual de linhas de uma
tabela retornadas por uma query
Alta seletividade (Bom para usar índices!)

Alta restrição e baixo percentual
Alta seletividade
member_no last_name first_name
1
Randall
Joshua
2
Flood
Kathie
= 10%
SELECT *
FROM member
WHERE member_no > 9001
.
.
.
10000
1000
Número de registros que atendem aos critérios
=
10000
Número total de registros em uma tabela
Anderson
Bill
37
Quais colunas indexar?

Determinando a densidade



Densidade é o percentual de linhas
duplicadas em um índice
Se os dados ou a consulta tem baixa
seletividade, geralmente a densidade é alta
Alta densidade


Um índice com um grande número de duplicatas
Um índice único tem baixa densidade

Prefira criar índices com baixa densidade
38
Quais colunas indexar?

Determinando a densidade
last_name
first_name
Randall
Joshua
.
.
.
Randall
Randall
Cynthia
Tristan
Alta densidade
SELECT *
FROM member
WHERE last_name =
‘Randall’
.
.
Baixa densidade
.
SELECT *
FROM member
WHERE last_name = ‘Ota’
Ota
.
Lani
.
.
39
Quais colunas indexar?

Determinando a distribuição de dados

Usar índices quando há uma distribuição não
homogênea de valores
Distribuição não-homogênea (standard) de valores
Número de
Nomes
A-E
F-J
K-O
Nome
P-U
V-Z
40
Quais colunas indexar?

Diretrizes sobre indexação

Colunas que devem ser indexadas




Chaves primárias e estrangeiras
Colunas pesquisadas para a localização de faixas
Colunas utilizadas em ORDER BY
Colunas agrupadas durante a agregação
41
Quais colunas indexar?

Diretrizes sobre indexação

Colunas que não devem ser indexadas


As que sejam raramente referenciadas em uma
consulta
As que contenham poucos valores únicos (sexo!)



Baixa seletividade
Alta densidade
As que sejam definidas com os tipos de dados
BLOB (binary large objects)
42
Melhores Práticas
Crie índices em colunas que unem tabelas
Use índices para impor exclusividade
Examine os índices e descarte aqueles que não estão
sendo usados
Evite chaves com muitas colunas
Crie índices que ofereçam suporte aos argumentos de pesquisa
43