Organização de Arquivos
Tipos de Indices
Cálculo de Custos de I/O
AULA 5
Profa. Sandra de Amo
GBC053 – BCC
Parte I : Indices Densos, Primários,
Compostos,...
Indices Densos
 Densos : se para cada valor v da chave de
busca existe uma entrada (v,rid).
 Não-denso = esparso
Exemplo de Indices denso e não denso
André, 44, 2000
30
Carlos, 44, 2000
31
Ilmério, 40, 3500
35
José
João, 35, 3000
35
Rodrigo
José, 40, 2500
35
Maria, 30, 4000
40
Pedro, 35, 2000
40
Rodrigo, 40, 3500
Sabrina, 31, 5000
40
44
Sara, 35, 4000
44
André
Indice Esparso e Agrupado
Registros de dados
Indice Denso
e não-agrupado
Vantagens e desvantagens
 Esparso tem que ser agrupado
 Vantagens de esparso : arquivo de indice
ocupa menor espaço.
 Desvantagem de esparso : técnicas de
otimização de busca são apropriadas para
indices densos.
Indices Primários e Secundários
 Primários : Chave do índice inclue a chave
primária da relação.

Não há entradas duplicadas (com mesmo
valor da chave)
 Secundários : Não contém chave primária.


Pode conter chave candidata
Pode conter duplicatas ou não
Indices com chaves compostas
Indice em (Idade,Sal)
Indice em Idade
31,80
31
33,75
33
42,10
bob
42
10
42
42,20
cal
31
80
42
joe
42
20
sue
33
75
Indice em Sal
10,42
10
20,42
20
75,33
80,31
75
Indice em (Sal,Idade)
80
Consultas
 Consultas com igualdade

Chave composta (Idade, Sal)
Idade = 10, Sal = 80

Arquivos Hashed só são convenientes para consultas com
igualdade
 Consultas Range

Chave composta (Idade, Sal)



Idade = 10
Idade < 10, Sal > 80
Arquivos Ordenados são convenientes para consultas com
igualdade
Indices em SQL
 CREATE INDEX IndAgeGrau ON Estudantes
With Structure = BTREE,
Key = (Idade, Média)
Parte II : Cálculo de Custos de I/O
Heap Files
Modelo de Custo
Hipóteses
B
= Número de Páginas
R = Número de registros por página
D = Tempo médio para ler ou escrever uma página
no disco
± 25 msec
C = Tempo médio para processar um registro
± 1 a 10 microsec
Custo = número de acessos ao disco
05/11/2015
11
Operações em Arquivos
 Scan : ler todos os registros de um arquivo


Páginas devem localizadas no disco e serem carregadas no Buffer
Pool
Registros devem ser localizados nas páginas
 Busca com seleção =


Páginas com os registros selecionados devem ser localizadas e
carregadas
Registros devem ser localizados nas páginas
 Busca com seleção > ou <


05/11/2015
Páginas com os registros selecionados devem ser localizadas e
carregadas
Registros devem ser localizados nas páginas
12
Operações
 Inserção
 Identificar a página na qual registro deve ser inserido
 Carregar esta página no buffer pool
 Incluir novo registro
 Escrever a página modificada no disco
 Deleção
 Identificar a página contendo o registro
 Carregar esta página no buffer pool
 Modificar a página
 Escrever a página modificada no disco
05/11/2015
13
Lembrando...
 B = Número de Páginas
 R = Número de registros por página
 D = Tempo médio para ler ou escrever uma página no disco


Ler = localizar no disco + carregar
Escrever = localizar posição no disco + transferir
dados para o disco
 C = Tempo médio para processar um registro no buffer
05/11/2015
14
Heap Files
 Scan
 Cada
página deve ser lida
 Processar R registros por página
 Custo = B(D+RC)
05/11/2015
15
Heap Files
 Procura (Sel « = « na chave)





Atenção: Chave primária ou candidata da tabela !!
Encontrou, pára !
Em média, metade do arquivo deve ser
escaneado para se encontrar a página
correspondente ao registro.
Carregar a página
Escanear a página à procura do registro
 Custo
05/11/2015
= 0.5B(D + RC)
16
Heap Files
 Procura (Sel « = « não-chave)
 Todo o arquivo deve ser escaneado
 Tempo = B(D+RC)
 Procura (Sel <)
 Todo o arquivo deve ser escaneado
 Tempo = B(D+RC)
 Inserção
 Registros são inseridos sempre no final do arquivo
 Página final deve ser carregada, modificada e escrita
de volta no disco
 Tempo = 2D + C
05/11/2015
17
Heap Files
 Deleção de um registro




Encontrar a página do registro
Remover o registro da página
Escrever a página modificada
Tempo = Sel + D + C
Tempo para alterar o registro
Tempo de localizar o registro e
trazer a página correspondente
para o buffer pool.
05/11/2015
Tempo para escrever a página
no disco
18
Resumo – Heap Files
Scan
Sel =
Sel =
chave
Nchave
B(RC+D)
0.5
B(RC+D)
B(D+RC)
BD
0.5BD BD
05/11/2015
Sel <> Insert
Delete
sel
B(D+RC)
2D+C
Sel +
+D+C
BD
2D
Sel+D
19