Arquivos Estruturados por
Ordenação– Custos I/O
AULA 5
Profa. Sandra de Amo
GBC053 – BCC
Estudaremos nesta aula
 Estimativa de custos de I/O para operações
de:





Scan em arquivos ordenados
Inserção de tuplas em arquivos ordenados
Remoção de tuplas em arquivos ordenados
Busca em arquivos ordenados pelo atributo- chave de busca
Busca em arquivos ordenados por atributos diferentes do
atributo-chave de busca
Arquivos ordenados por um atributo X
 As páginas do arquivo contém diretório de slots




como os arquivos heap.
Este diretório é utilizado para localizar a posição na
página onde se encontra um registro com rid dado.
O endereço do início do espaço vazio só é utilizado
para saber quantos bytes de espaço livre existe na
página.
A inserção de um novo registro não é feita
utilizando o diretório de páginas, pois o registro deve
ser inserido em uma posição adequada do arquivo,
respeitando a ordenação.
A remoção de um registro é feita exatamente
como no caso de arquivo heap.
Exemplo: inserção de um registro
Diretório de slots da página
Página 5
(500,165) (450,50)
Registros:
Rid (5,1) : (...., 2, ....)
Rid (5,2) : (...., 4,....)
Rid (5,3) : (...., 9, ....)
Rid (5,4) : (...., 13,....)
Rid (5,5) : (...., 16,....)
(250,200) (100,150) (0,100)
5
665
Passos para a inserção do registro
Suponha que se quer inserir o registro
(...., 12 ,....) de tamanho 300
1.
Busca binária no arquivo, pelo atributo X, para determinar a
página onde deverá ser inserido. No caso esta página será a
página 5.
2.
Através das informações contidas no diretório de slots, determina
se existe espaço nesta página para o novo registro. Supondo
que o tamanho de uma página é 1000 bytes, como o espaço livre
começa em 665, tem-se 335 bytes de espaço livre na página.
3.
Busca binária na página para saber a posição em que deverá
ser inserido o registro. No caso a inserção será após o registro
de rid (5,3) cujo conteúdo é (..., 9, ...).
4.
Os registros subsequentes são transladados de 300 bytes à
direita para dar lugar para o novo registro.
Qual o rid do novo registro ?
Verifica no diretório de slots se há algum slot com
conteúdo (-1,_). Se houver, este será o slot
associado ao novo registro.
2. Se não houver: cria-se um novo slot que será
associado ao novo registro.
3. Atualiza o diretório de slots.
1.
Situação após a inserção.
Novo registro de tamanho 300
Espaço vazio (35 bytes)
Diretório de slots da página
Página 5
(450,300) (800,165) (750,50) (250,200) (100,150) (0,100)
Registros:
Slot 6 Slot 5 Slot 4
Slot 3 Slot 2 Slot 1
Rid (5,1) : (...., 2, ....)
Rid (5,2) : (...., 4,....)
Rid (5,3) : (...., 9, ....)
Rid (5,4) : (...., 13,....)
Rid (5,5) : (...., 16,....)
Novo registro
Rid (5,6) : (...., 12,....)
6
965
O que acontece quando não há espaço suficiente
na página 5 para o novo registro ?
 Determina-se quantos e quais registros (a partir do
último na página) devem ser passados para a
próxima página para dar lugar para o novo registro.
 Insere-se tais registros na próxima página
 Atualiza-se o diretório de slots da página 5, após a
remoção dos registros que passaram para a outra
página.
 Insere-se o novo registro na página 5 conforme já
descrito e atualiza-se o diretório de slots da página 5
após esta inserção.
ESTIMATIVAS DE CUSTOS
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 + 0.5*BD + 0.5BRC + 0.5BD =
Custo estimado = D (log2B) + C(log2R)+ BD+ 0.5BRC
Gravação das páginas modificadas
Carrega as páginas a serem modificadas
Altera os registros subsequentes
Arquivos Ordenados : Deleção
 Deleção:
 supondo que o arquivo está ordenado pelo atributo que seleciona
os registros a serem removidos
 Encontrar as páginas satisfazendo a condição de deleção




Custo = tempo da busca pelo 1o registro + busca dos demais
 (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.
Se for um único registro a ser removido A = a :
 Custo estimado = Busca registro + altera subsequentes + grava
páginas alteradas = D (log2B) + C(log2R) + 0.5B(D + RC) + 0.5BD
D (log2B) + C(log2R) + BD+ 0.5B*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)
+BD+
0.5BRC)
D(log2B)+
C(log2R)
+BD+
0.5BRC
BD
Dlog2B
Dlog2B Dlog2B + Dlog2B+
DB/2
BD
Dlog2B+
BD
Só I/O