Cálculo de Custos de Operações
I/O – Arquivos Ordenados
AULA 6
Profa. Sandra de Amo
GBC053 – BCC
Estudaremos nesta aula
 Estimativa de custos de I/O para operações
de:





Scan no arquivo
Inserção de tuplas em arquivos ordenados
Remoção de tuplas em arquivos ordenados
Busca em arquivos ordenados pelo atributochave de busca
Busca em arquivos ordenados por atributos
diferentes do atributo-chave de busca
Arquivos Ordenados : SCAN
 Cada página deve ser transferida do disco
 Tempo de transferência = D
 Cada página deve ser processada no buffer (R
registros são processados)

Tempo de processamento = RC
 Custo total por página = D + RC
 Custo total da operação SCAN = B(D+RC)
Atenção
 Nas operações de busca em arquivos ordenados, vamos supor
que:
 O arquivo está ordenado por um atributo A
 A busca é feita pelo atributo A
 O atributo A pode ou não ser chave da relação onde está sendo
feita a busca
 Caso a busca seja feita por um atributo diferente de A, o custo é
o mesmo de um SCAN
Arquivos Ordenados : Busca
Seleção A = a
A : atributo chave (da relação)
Atenção: Chave = chave da relação !!
Arquivo é ordenado pela chave da relação.
1)
2)
Busca binária no arquivo
Cada passo = uma operação de input + 1 registro processado no
buffer
• Custo de cada operação de Input = D
• Custo para processar todas as páginas necessárias na busca
binária até encontrar a página onde está o registro procurado =
D(log2B)
3) Uma vez encontrada a página onde está o registro, fazer busca binária
na página
Custo = C(log2R)
Custo total = D (log2B) + C (log2R)
Arquivos Ordenados : Busca
Seleção A = a
A : atributo não-chave (da relação)
Os registros satisfazendo a condição são adjacentes
(pois o arquivo é ordenado pelo atributo da seleção )
1) Localizar o primeiro registro satisfazendo a condição
CUSTO = Dlog2B + C log2R
2) Ler todos os registros subsequentes em ordem sequencial
Em média tais registros satisfazendo a condição cabem em uma página.
Em média, o primeiro registro satisfazendo a condição encontra-se no meio da
página.

Custo = D log2B + C log2R + custo de ler o resto

Custo total estimado = D log2B + C log2R + RC/2
Arquivos Ordenados : Busca
Seleção A > a
A : atributo chave (da relação)
1) Localizar o primeiro registro
Custo = Dlog2B + C log2R
2) Ler todos os registros subsequentes em ordem
sequencial
Custo = Dlog2B + C log2R + custo de ler o resto
Custo estimado= Dlog2B + C log2R + B/2(D+RC)
Arquivos Ordenados : Inserção
 Inserção


Suponhamos que o arquivo esteja ordenado pela chave da relação
(A)
Encontrar a posição onde deve ser inserido o registro
(a1, a2, …, an)





Custo de uma busca A = a1, onde A é chave da relação =
D (log2B) + C(log2R)
Inserir registro (em média, encontra-se na metade do arquivo)
Reescrever todos os registros subsequentes da página onde foi
feita a inserção (shift nos demais registros)
Custo = Busca posição + 2*0.5*B(D + RC) =
Custo estimado = D (log2B) + C(log2R)+ B(D+RC)
Arquivos Ordenados : Deleção
 Deleção:
 supondo que o arquivo está ordenado pelo atributo de que
seleciona os registros a serem removidos
 Encontrar a página do primeiro registro satisfazendo a condição de
deleção




Custo = tempo da busca pelo registro
 (depende da condição da operação de deleção: A = a ,
A > a, se A é chave da relação ou não)
Remover o(s) registro(s) das páginas
Escrever a(s) página(s) modificada(s)
Reescrever todos os registros subsequentes aos que foram
removidos, somente nas páginas onde ocorreram remoções
Se for um único registro a ser removido A = a :
 Custo estimado = Busca registro + 2.0.5B(D + RC) =
D (log2B) + C(log2R) + B(D+RC)
Importante :
 Para efeito dos cálculos de custos, estamos
supondo que a condição de seleção é
especificada no atributo pelo qual o arquivo
está ordenado.
 Caso a condição de seleção não seja sobre o
atributo pelo qual o arquivo é ordenado, os
custos são os mesmos que para os arquivos
Heap.
Resumo - Ordenados
Scan
Sel =
chave
Sel =
Nchave
Sel <>
Insert
Delete
Sel =
chave
B(D+RC)
Dlog2B +
Clog2R
Dlog2B +
Clog2R
+
RC/2
Dlog2B +
Clog2R
+
B/2(D+RC)
D(log2B)+
C(log2R)
+
B(D+RC)
D(log2B)+
C(log2R)
+
B(D+RC)
BD
Dlog2B
Dlog2B Dlog2B + Dlog2B+
DB/2
BD
Dlog2B+
BD
Só I/O