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
Página 5Diretório de slots da página
6655(0,100)(100,150)(250,200)(450,50)(500,165)
Registros:Rid (5,1) : (...., 2, ....)Rid (5,2) : (...., 4,....)Rid (5,3) : (...., 9, ....)Rid (5,4) : (...., 13,....)Rid (5,5) : (...., 16,....)
Passos para a inserção do registro
Suponha que se quer inserir o registro (...., 12 ,....) de tamanho 3001. 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 ?
1. 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.
Situação após a inserção.
Página 5Diretório de slots da página
9656(0,100)(100,150)(250,200)(750,50)(800,165)
Registros:Rid (5,1) : (...., 2, ....)Rid (5,2) : (...., 4,....)Rid (5,3) : (...., 9, ....)Rid (5,4) : (...., 13,....)Rid (5,5) : (...., 16,....)Rid (5,6) : (...., 12,....)
(450,300)
Slot 1Slot 2Slot 3Slot 4Slot 5Slot 6
Novo registro de tamanho 300
Espaço vazio (35 bytes)
Novo registro
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) Busca binária no arquivo 2) 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áginaCusto = C(log2R)
Custo total = D (log2B) + C (log2R)
Arquivos Ordenados : BuscaSeleçã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 + DB/2
Dlog2B+BD
Dlog2B+
BD
Só I/O