Gerenciamento de Arquivos,
Páginas e Registros
AULA 3
Profa. Sandra de Amo
Gerenciamento de Banco de Dados – BCC
ARQUITETURA GERAL
DE UM SGBD
RELACIONAL
11/4/2015
Estudaremos nesta aula:
 Como localizar páginas em um arquivo ?
 Como localizar registros em uma página ?
 Como localizar campos em um registro ?
11/4/2015
3
ORDEM DOS ASSUNTOS TRATADOS
ARQUIVO
Página
Registro
11/4/2015
4
Heap Files
 Heap Files:
Dados não são ordenados
 Dados são organizados sequencialmente a
medida que são inseridos.
 Obter todos os dados do arquivo  varrer registro
por registro a partir do primeiro.
 Operações
 Create, destroy files
 Insert, delete, get a record
 Scan all records

11/4/2015
5
Gerenciar as páginas no heap file
1.Como encontrar determinada página ?
2.Que página possui espaço livre?
Método 1: Lista ligada de páginas
 Método 2: Diretório de páginas

11/4/2015
6
Lista Ligada de Páginas
Tabela Arquivos- End 1a página
Arquivo
EndPag1
Alunos
1033
Hospital 5023
Páginas contendo
Espaço Livre
Header Page
Páginas Cheias
1a página do arquivo
11/4/2015
7
Inserção de novos registros
 Gerenciador de arquivos

Procura na lista de páginas com espaço livre onde
cabe o novo registro

Caso não encontre: aloca nova página na lista
das páginas com espaço livre e insere o registro

Caso a página onde o registro tenha sido inserido
fique cheia, insere esta página na lista de páginas
cheias e atualiza lista de páginas livres
11/4/2015
8
Deleção de páginas
Caso a deleção de um registro de uma página resulte
em uma página vazia:
 Caso 1: Página onde estava o registro deletado estava na lista de
páginas com espaço vago
 Gerenciador de arquivos é acionado
 Página é retirada da lista de páginas vazias: ponteiros que
apontavam para ela e que saiam dela são reajustados.
 Caso 2: Página onde estava o registro deletado estava na lista de
páginas cheias
 Gerenciador de arquivos é acionado
 Página é retirada da lista de páginas cheias: ponteiros que
apontavam para ela e que saiam dela são reajustados.
11/4/2015
9
Desvantagens
 Maioria das páginas estão na lista das páginas
contendo espaço vazio

Registros de tamanho variável

Toda página contém alguns bytes de espaço livre

Inserção de registro requer examinar diversas páginas
para encontrar espaço suficiente
11/4/2015
10
Diretório de Páginas
Tabela Arquivos- End 1a páginaDP
Header
Arquivo Endpg1DP
Page
Alunos
Pg Dados 1
10
40
1033
35
Hospital 5023
Espaço Livre
da Página 1
Pg Dados 2
Pg Dados N
Diretório de Páginas = Lista Ligada
11/4/2015
11
Estudaremos nesta aula:
 Como localizar páginas em um arquivo ?
 Como localizar registros em uma página ?
 Como localizar campos em um registro ?
11/4/2015
12
Como os registros são organizados nas
páginas
rid = identificador do registro (record id)
registro
rid
2 50
Identificador
da página
Número do slot
Página = coleção de slots
Slot = espaço físico preenchido por um
registro
11/4/2015
13
Como registros são organizados
 Registros de Tamanho Fixo : 1a alternativa








11/4/2015
Registros armazenados nos primeiros N slots
N = número de registros
Armazenamento consecutivo
Quando um registro é deletado : o último registro passa a
ocupar o slot liberado
Localização do i-ésimo registro = soma de offsets
Inserção de um novo registro = após o último slot ocupado.
Todos os slots vazios aparecem juntos no final da página
Problema : se há referência externa ao registro
(Ex: solicita-se a localização do rid (3,2))
 rid do registro contém o número do slot
 Como slot muda, o rid também muda
14
Como registros são organizados:
1a alternativa
Slot 1
Slot 2
Slot 3
Slot N
Espaço livre
N
Número de registros
Informações sobre a página :
Número da página, ponteiro para próxima página,…
11/4/2015
15
Como registros são organizados
(2ª alternativa)
 Registros de Tamanho Fixo : 2a alternativa
Slot 1
Espaço livre
Slot 2
Slot 3
Slot M
Info sobre página
11/4/2015
1 0 1
1 M
1 2
M
3
Número de Slots
16
Como registros são organizados
Registros de Tamanho Variável
 Não se pode dividir a página num número fixo de
slots
 Quando um novo registro é inserido

Encontrar slot vazio onde o registro cabe exatamente
 Quando um registro é deletado


11/4/2015
Mover registros para preencher o « buraco » criado.
Todo o espaço livre deve ser contíguo.
17
Como registros são organizados
 A fim de poder mover registros na página de
tal modo que seu número de slot não
modifique :



11/4/2015
Cria-se um diretório de slots
Neste diretório, a cada slot está associado um
ponteiro e o tamanho do registro.
Caso o registro mude de lugar, apenas o
ponteiro do slot correspondente muda no
diretório de slots.
18
Diretório de Slots da Página
Ponteiro para o início do
espaço livre na página
1035
200
Número de slots no diretório
(P1, T1)
1
(P2, T2)
2
Pi = ponteiro para o registro 1
Ti = tamanho do registro 1
(P200, T200)
11/4/2015
200
Rid = (np, i)
Ti
19
Organização da Página
Área de dados
Página i
rid = (i,N)
rid = (i,1)
rid = (i,2)
Comprimento = 24
Espaço Livre
Diretório de slots
11/4/2015
20
16
N
2
Bacharelado em Ciência da Computação - 2004
24
N
1
20
Deleção de Registros
Registro rid = (5, 3) com tamanho 50 é deletado
(-1,_)
Entrada 3 no diretório de slots
Slot 3 está vago
Outros registros são reorganizados
Registro (5,4) muda de lugar – seu número de slot 4 não muda !
Entrada 4 no diretório de slot muda =
(Newpointer4,T4)
Entrada inicial do diretório = novo ponteiro para espaço livre
Número de slots no diretório = igual ao anterior.

11/4/2015
Bacharelado em Ciência da Computação - 2004
21
Inserção de Registros
Registro R inserido no início do espaço livre
O endereço E onde será inserido R é obtido no diretório de slots
Diretório de slots é atualizado:




11/4/2015
Procura-se no diretório de slots por alguma entrada (-1,x)
Caso encontre : modifica-se esta entrada
(E, tamanho do registro R)
Caso não encontre : acrescenta um novo slot
N+1 = (E, tamanho do registro R)
Atualiza endereço do início do espaço livre no diretório de
slots
22
Estudaremos nesta aula:
 Como localizar páginas em um arquivo ?
 Como localizar registros em uma página ?
 Como localizar campos em um registro ?
11/4/2015
23
Formatos de Registros




Processador de consultas «vê » os dados como coleção de
registros.
 Catálogo do sistema armazena: Número de campos,
tamanho dos campos, tipos dos campos
Tamanho fixo
 Número de campos fixo
 Cada campo tem o mesmo comprimento em todos os
registros.
Tamanho variável
 Número de campos é fixo
 Alguns campos podem ter tamanhos variáveis em
diferentes registros.
Cada registro guarda seu rid (Np, Nslot).
11/4/2015
24
Como localizar um campo em um
registro de tamanho fixo
O tamanho do campo Ci é o mesmo em todos os registros
C1
L1
B= endereço do registro
C2
L2
C3
C4
L3
L4
Endereço = B + L1 + L2
Ci = campo i
Li = Comprimento do campo i
11/4/2015
25
Como localizar um campo em um
registro de tamanho variável
1a alternativa
C1
$
C2
$
C3
$
C4
$
Registro
2a alternativa
C1
C2
C3
C4
Endereço do final
do registro
11/4/2015
26
Vantagens e Desvantagens
 2a alternativa é melhor:

Acesso direto a cada campo

Maneira clara de se tratar valores nulos –
endereços de início e fim são iguais

Também pode tratar registros de tamanho fixo
11/4/2015
27
Como são modificados os campos
 Modificação de um campo :

Shift nos campos subsequentes
 Campo modificado pode não caber na página
Rid do registro = (Np, Nslot)
11/4/2015
28
Como são modificados os campos
 Registro inteiro pode não caber numa página


registro é quebrado em registros menores
Cada subregistro tem um ponteiro para o
subregistro subsequente
subregistro
11/4/2015
Ponteiro para o próximo subregistro
29
Download

Slides - Sandra de Amo