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