Organização de Arquivos Tipos de Indices Cálculo de Custos de I/O AULA 5 Profa. Sandra de Amo...

Organização de ArquivosTipos de Indices

Cálculo de Custos de I/O

AULA 5 Profa. Sandra de Amo

GBC053 – BCC2013-1

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

Carlos, 44, 2000

José, 40, 2500

João, 35, 3000

Ilmério, 40, 3500

Rodrigo, 40, 3500

Maria, 30, 4000

Sara, 35, 4000

Sabrina, 31, 5000

30

31

35

35

35

40

40

40

44

Registros de dados

Indice Esparso e Agrupado 44

Pedro, 35, 2000

Indice Denso e não-agrupado

André

José

Rodrigo

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

bob

cal

joe

sue

42

31

42

33

80

10

20

75

Indice em Idade

31

33

42

42

10

20

75

80

Indice em Sal

31,80

33,75

42,10

42,20

10,42

20,42

75,3380,31

Indice em (Idade,Sal)

Indice em (Sal,Idade)

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 EstudantesWith Structure = BTREE,

Key = (Idade, Média)

Parte II : Cálculo de Custos de I/OHeap Files

11/04/23 11

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 msecC = Tempo médio para processar um registro

± 1 a 10 microsecCusto = número de acessos ao disco

11/04/23 12

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 < Páginas com os registros selecionados devem ser localizadas e

carregadas Registros devem ser localizados nas páginas

11/04/23 13

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

11/04/23 14

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

11/04/23 15

Heap Files

Scan

Cada página deve ser lida Processar R registros por página Custo = B(D+RC)

11/04/23 16

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 = 0.5B(D + RC)

11/04/23 17

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

11/04/23 18

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 de localizar o registro e trazer a página correspondentepara o buffer pool.

Tempo para alterar o registro

Tempo para escrever a páginano disco

11/04/23 19

Resumo – Heap Files

Scan Sel = chave

Sel = Nchave

Sel <> Insert Delete

selB(RC+D) 0.5

B(RC+D)

B(D+RC) B(D+RC) 2D+C Sel +

+ D + C

BD 0.5BD BD BD 2D Sel+D