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