Revisão Prova 1

AULA 10 Profa. Sandra de Amo

GBC053 – BCC2013-1

Esquema Geral

DB

Processador de Consultas

Gerenciador de Buffer

Solicita dados para consulta (leitura) ou alterações (escritura)

Buscaaloca

Informa modif

Propaga modif

Disco Memória Principal

Dados precisam estar na memória principal para serem operados.

Unidade de transferência de dados entre disco e memória principal = bloco

Se um único item num bloco é necessário, todo o bloco é transferido

Ler ou escrever um bloco = operação de I/O

Tempo de Acesso = busca + rotação + transferência

Tempos de Acesso

Procura Tempo para mover as cabeças dos discos para a

trilha na qual um bloco desejado está localizado. Rotação

Tempo para que o bloco desejado se posicione sob a cabeça do disco = meia rotação em média; menor do que tempo de busca.

Transferência

Tempo para ler ou escrever no bloco = tempo de rotação do disco sobre o bloco.

Gerenciador de Espaço em Disco

Quais blocos estão em uso ? Que páginas estão em que blocos ? Inserções e supressões de páginas = criação de “buracos”. Páginas são alocadas quando da criação de arquivos. Gerenciamento de espaço livre

1a alternativa Lista de blocos livres. Ponteiro para primeiro bloco livre é estocado num

local do disco. 2a alternativa

Array de 0 e 1 : se o bloco i está livre ou não

Algoritmo de Gerenciamento do Buffer Pool

3 0

Frame no pool

Dirty bit : página suja ou não

Pin-count = número de vezes que a página foi solicitada para consultas ou modificações mas não foi liberada ainda.

Inicialmente :

Dirtybit := 0

Pin-count := 0

Algoritmo de Gerenciamento

Testa se buffer pool contém a página desejada Se não : procura frame com pin-count = 0 Frame com pin-count = 0 : página está liberada por transações

que a utilizavam Caso não encontre frame com pin-count = 0

Espera até que as transações sendo executadas liberem páginas em uso.

Se dirty-bit = 0, escreve página nova no frame. Se dirty-bit = 1 :

escreve página do frame no disco Escreve nova página no frame Incrementa pin-count do frame (já que alguma

transação solicitou a página)

Políticas de Substituição de Páginas

Que frames com pin-count = 0 escolher para substituição ?

LRU : Least recently used Lista de ponteiros para frames com pin-count = 0 Ponteiros dos frames são adicionados no fim da

lista MRU : Most recently used

Lista de ponteiros para frames com pin-count = 0 Ponteiros dos frames são adicionados no início da

lista Random

Gerenciamento de arquivos Heap (sequencias)

1.Como encontrar determinada página no arquivo ?

2.Que página possui espaço livre?

Método 1: Lista ligada de páginas Método 2: Diretório de páginas

04/11/23 Bacharelado em Ciência da Computação - 2004 9

04/11/23 Bacharelado em Ciência da Computação - 2004 10

Lista Ligada de Páginas

Arquivo EndPag1

Alunos 1033

Hospital 5023

Tabela Arquivos- End 1a página

Header Page

Páginas contendo Espaço Livre

Páginas Cheias

1a página do arquivo

Diretório de Páginas

Diretório de Páginas = Lista Ligada

10 40

35

Pg Dados 1

Pg Dados 2

Pg Dados N

HeaderPage

Espaço Livreda Página 1

Arquivo Endpg1DP

Alunos 1033

Hospital 5023

Tabela Arquivos- End 1a páginaDP

Focando agora nas páginas !!

2 50

Identificadorda página

Número do slot

registro

rid

Página = coleção de slots

Slot = espaço físico preenchido por umregistro

rid = identificador do registro (record id)

13

Como registros de tamanho FIXO são organizados: 1a alternativa

N

Slot 1

Slot 2

Slot 3

Slot N

Espaço livre

Número de registros

Informações sobre a página :

Número da página, ponteiro para próxima página,…

04/11/23 Bacharelado em Ciência da Computação - 2004 14

Como registros de tamanho fixo são organizados (2ª alternativa) Registros de Tamanho Fixo : 2a alternativa

Info sobre página

Espaço livreSlot 1

Slot 2

Slot 3

Slot M

M Número de Slots

1 2 3 M

1 0 1 1

04/11/23 Bacharelado em Ciência da Computação - 2004 15

Como registros de tamanho variável são organizados – Diretório de Slots da Página

200 Número de slots no diretório

1035 Ponteiro para o início do espaço livre na página

(P1, T1)

(P2, T2)

(P200, T200)

1

2

200

Pi = ponteiro para o registro 1

Ti = tamanho do registro 1

Rid = (np, i)

Ti

04/11/23 Bacharelado em Ciência da Computação - 2004 16

Organização da Página

Página i

Espaço Livre

Área de dados

rid = (i,1)

N24

Comprimento = 24rid = (i,2)

rid = (i,N)

20 16Diretório de slots

12N

Focando agora nos registros !!

C1 C4C3C2

L2 L3 L4L1

B= endereço do registro Endereço = B + L1 + L2

Ci = campo i

Li = Comprimento do campo i

O tamanho do campo Ci é o mesmo em todos os registros

04/11/23 Bacharelado em Ciência da Computação - 2004 18

Como localizar um campo em um registro de tamanho variável

$ $ $$C1 C4C3C2

C1 C3 C4C2

1a alternativa

2a alternativa Registro

Endereço do final do registro

Indice: como são os registros ?

Alternativa 1 Entrada = registro inteiro de dados Neste caso, a única vantagem do índice é a forma como é

organizado: ordenado, hash, com método de acesso ou não Alternativa 2

Entrada = (k,rid), k = chave Chave = conjunto de atributos

Alternativa 3 Entrada = (k, lista de rids) Vantagem: ocupa menos espaço. Uma chave acessa

diversos registros no arquivo de dados Desvantagem: registro de tamanho variável

Como organizar as entradas do índice ?

Entrada = registro

Entradas podem ser ordenadas Entradas podem ser organizadas por Hash

Exemplo de Indice

Paulo, 44, 2000

Pedro, 35, 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

2000

2000

2000

2500

3000

3500

4000

3500

4000

5000

Registros de dadosEntradas : organizadasde forma ordenada

Exemplo de Indice organizado por Hash

Paulo, 44, 2000

Pedro, 35, 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

2000

2000

2000

2500

5000

3000

3500

3500

4000

Registros de dadosEntradas

H

4000

H(sal) = 01

H(sal) = 11

H(sal) = 00

Exemplo de Indice Agrupado

Paulo, 44, 2000

Pedro, 35, 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

2000

2000

2000

2500

3000

3500

4000

3500

4000

5000

Registros de dadosEntradas

Exemplo de Indice não agrupado

Paulo, 44, 2000

Pedro, 35, 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

2000

2000

2000

2500

5000

3000

3500

3500

4000

Registros de dadosEntradas

H

4000

H(sal) = 01

H(sal) = 11

H(sal) = 00

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

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)

Organização de arquivos

Sequencial Ordenado Hash Usando Métodos de Acesso para melhorar

performance Indices: Arquivos AUXILIARES ISAM, B+Tree, Hash

Custos de Operações – Arquivos Heap (sequencial)

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

Custos de Operações – Arquivos Ordenados

Custos de Operações: Arquivos Ordenados

Scan Sel =

chave

Sel =

Nchave

Sel <> Insert Delete

Sel = chave

B(D+RC) (log2B)(D+C) +

Clog2R

(log2B)(D+C) +

Clog2R +

+

RC/2

(log2B)(D+C)+

Clog2R +

B/2(D+RC)

(log2B)(D+C) + (log2R)(C) + (D+RC/2)

(log2B)(D+C) + (log2R)(C) + (D+RC/2)

BD Dlog2B Dlog2B Dlog2B + DB/2

Dlog2B+D

Dlog2B+D

Custos de Operações – Arquivos Hashed

Scan Sel = chave

Sel = Nchave

Sel <> Insert Delete

sel1.25B (D+RC)

H + D + RC

1.25B(D+RC)

1.25B(D+RC)

H+2D+ C Sel +

D + RC

1.25BD D 1.25BD 1.25BD 2D Sel+D

Escolha de uma Boa Organização

Scan Sel =

chave

Sel = Nchave

Sel <> Insert Delete

Heap BD 0.5BD BD BD 2D 2D+Sel

Ord BD Dlog2B Dlog2B Dlog2B +

B/2(D+RC)

Dlog2B+

D

Dlog2B+

D

Hash 1.25BD D 1.25BD 1.25BD 2D Sel+D

Método de Acesso – ISAM Organização do índice em árvore

Páginasauxiliaresque permitemchegar rapidamente a uma folha

Páginas do arquivo de índice

Páginas do Arquivo de Dados

Discussão

ISAM é uma estrutura estática Na criação do arquivo

Páginas primárias (folhas) são alocadas 20% de cada página é livre para posteriores

inserções, tentando “adiar” ao máximo a criação de páginas de overflow

Páginas intermediárias são criadas. Manutenção :

Páginas de overflow são alocadas à medida que as páginas primárias do índice ficam cheias em decorrência de inserções.

Esquema Geral do Método ISAM

Páginasdos arquivosde indices(a partir da 2a camada)

Páginas de overflow

Páginas primárias –as entradas do arquivo de índice da primeira camada

Como são os nós internos da estrutura ISAM ?

P0 P1 P2 Pi Pi+1 PmK1 ... ...K2 K3 Ki+1 Km

Pi = ponteiros que apontam para um núm. de página no nível imediatamente inferior

Ki = valor do atributo chave do índice. Exemplo: se o atributo chave é idade então Ki é um valor de idade.

K < Ki+1 K ≥ Ki+1

Valores K da chave nesta página são < Ki+1

Valores K da chave nesta página são ≥ Ki+1

Idéia

Se quero buscar empregado com status > 7: Não é preciso fazer busca binária nas páginas

do arquivo de indice Faz-se a busca binária no segundo arquivo, que

é bem menor do que o primeiro arquivo

2* 5* 7* 12* 14* 17* 19* 22*

14

Exemplo: Busca de um registro de dados

40

Raiz

5120

10* 15* 20* 27* 33* 37* 46*40* 51* 55* 63* 97*

3363

Busca da chave 27

Inserção de um registro

40Raiz

5120

10* 15* 20* 27* 33* 37* 46*40* 51* 55* 63* 97*

3363

Inserção de 23*, 48*, 41*, 42*

23*

Página de Overflow

48* 41*

42*

Deleção de um registro

40Raiz

5120

10* 15* 20* 27* 33* 37* 46*40* 51* 55* 63* 97*

3363

Deleção de 42*, 51*, 97*

23*

Pagina de Overflow

48* 41*

42*

Procura 51*

Nunca sãoalteradas !!

Comparação de CustosCusto de uma busca A = a

Arquivo de 1 000 000 registros 10 registros por página de dados : total de páginas

= 100 000 100 ponteiros em cada página de índice (99

entradas (chave,pt) + ponteiro P0) Arquivo não ordenado por A

Scan = 1000 000/10 = 100000 I/0 Arquivo ordenado por A

Busca binária = log2 100000 = 17 I/0 Arquivo estruturado usando método ISAM

Arquivo de indice usa alternativa 1 (registro do indice = registro de dados)

Custo = log100 100000 = entre 2 e 3 I/0, pois 1002 < 100000 < 1003

Vantagens de ISAM ISAM é estático :

inserções e deleções afetam somente as folhas.

Nós internos não sofrem modificações após uma inserção ou deleção de registros do indice.

Logo, páginas internas podem ser manipuladas por outras transações sem problemas de bloqueios, já que nunca são alteradas.

Desvantagens de ISAM Possibilidade de cadeias de páginas

overflow Páginas overflow geralmente não são

ordenadas, a fim de agilizar inserções. Para aliviar este problema :

Árvore é criada com 20% de cada folha livre Entretanto, uma vez preenchido este espaço,

cadeias de overflow só podem ser eliminadas através de uma total reorganização da estrutura.