BCC-2013-1

Organização de ArquivosIntrodução

AULA 4Profa. Sandra de Amo

GBC053 – BCC2013-1

BCC-2013-1

Estudaremos nesta aula

Part I : Como os dados são organizados dentro dos arquivos

Arquivos de indice O que é um arquivo de índice ? Funcionamento geral

Parte II: Organização: indice ordenado versus hash Tipos principais de arquivos de índices:

agrupados, densos, primários, secundários, compostos, ...

Indices agrupados

BCC-2013-1

Dados, indices, índices, índices, ...

DADOS

Consulta: Me dê o livro Database Systems – Ramakrishnan/Gehrke

Indice

BCC-2013-1

04/11/23 4

Arquivos de Indice

ridA D E F

chave

a d e fa d e fa d e f

(12,1)(18,5)(22,4)

rid A B C D E F G

a b1 c1 d e f g1(12,1)

a b2 c2 d e f g2(18,5)

a b3 c3 d e f g4(22,4)

Arquivo de Indice

Arquivo de DadosEndereços obtidos no diretório de arquivos e no diretório de slots das páginas

BCC-2013-1

04/11/23 5

Dinâmica geral dos Arquivos de Indice Busca no arquivo de indice:

Páginas deste arquivo são organizadas de modo a permitir a localização rápida das entradas com uma dada chave.

Uma vez encontradas rapidamente estas entradas no arquivo de índice, já temos os endereços dos registros de dados associados (seu rid = (N,X)).

O local exato no disco onde se encontra a página de número N é encontrado através do diretório de arquivos do disco: fornece o endereço da header page do arquivo.

O local exato na página N onde se encontra o slot X do registro procurado é obtido através do diretório de slots da página N

BCC-2013-1

Como encontrar um registro num Arquivo A conhecendo o rid do registro?

Rid = (12, 3) Vai no diretório de arquivos no disco e procura o

registro correspondente ao arquivo A, para obter o ponteiro para o primeiro bloco do arquivo.

Calcula o endereço do 12º bloco e posiciona a cabeça de leitura neste endereço.

Transfere o 12º bloco para o buffer pool Processador de consultas consulta o diretório de slot

da página 12 e procura o endereço do registro contido no slot 3, bem como o tamanho (L) do registro contido neste slot.

Vai para este endereço de memória e lê L bytes.

BCC-2013-1

Como encontrar um registro num Arquivo A caso não se conheça o rid do registro?

Vai no diretório de arquivos no disco e procura o registro correspondente ao arquivo A, para obter o ponteiro para o primeiro bloco do arquivo.

Transfere um a um cada bloco do arquivo para o buffer pool.

Cada bloco transferido é escaneado sequencialmente pelo processador de consultas até encontrar o registro procurado.

BCC-2013-1

04/11/23 8

Arquivos de Indice Otimiza a procura de registros em arquivos, pois o arquivo de indice

contém o rid dos registros.

Através do rid encontra-se facilmente os registros de dados completos nos arquivos.

No arquivo de índice, cada registro é da forma (valores_chave,rid) Chave = conjunto de atributos

Se chave contém chave candidata do arquivo, então chave determina unicamente o rid

Caso contrário, uma mesma chave pode acessar diversos rids.

Exemplo : se chave = {Salário}

BCC-2013-1

Como as informações são obtidas rapidamente no arquivo de indice ?

Métodos de Acesso

Técnicas de organização das páginas dos arquivos de índices

B+TreesTabelas Hash

BCC-2013-1

04/11/23 10

Catálogo do Sistema

Metadados

Descrição dos dados e índices

Informações sobre visões

Catálogo = conjunto de relações (arquivos) contendo todas as informações sobre os arquivos sendo utilizados pelo sistema.

BCC-2013-1

04/11/23 11

Catálogo do Sistema Arquivos « Relações », « Atributos », « Restrições », ...

Nome da relação, nome do arquivo , estrutura do arquivo Nomes e tipos dos atributos Nome do índice Restrições de Integridade (chave primária, estrangeira) Guardam inclusive registros correspondentes às relações

« Relações », « Indices », « Atributos », « Visões », ...

Arquivo « Indices »

Nome e estrutura de cada índice Chave de cada índice

Arquivo « Visões » Nome e código

BCC-2013-104/11/23 12

Exemplo

Cat-Atributos

Nome-Atributo Nome-Relação Tipo Posição

Nome-Atributo Cat-Atributos string 1

Nome-Relação Cat-Atributos string 2

Tipo Cat-Atributos string 3

Posição Cat-Atributos string 4

IdE Estudantes string 1

E-mail Estudantes string 2

Idade Estudantes integer 3

IdC Cursos string 1

NomeC Cursos string 2

BCC-2013-1

Resumo: Arquivo de Indice

O que é ? estrutura auxiliar projetada para agilizar

operações de busca, inserção e deleção

Em que consiste ? Uma coleção de registros Uma chave de busca k Cada entrada contém informação suficiente para

localizar registros de dados contendo a chave de busca k.

BCC-2013-1

Vantagens

Tamanho: normalmente é bem menor do que o arquivo de dados

Organização optimizada: pode ser sequencial, ordenado ou hashed

Método de Acesso rápido: pode ser estruturado usando uma b-tree ou hash (estático, dinâmico)

BCC-2013-1

O que armazenar em um índice ?

Registro de Dados =

Chave Rid + Registro do indice = Chave do índice !!

BCC-2013-1

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

BCC-2013-1

Como organizar as entradas do índice ?

Entrada = registro

Entradas podem ser ordenadas Entradas podem ser organizadas por Hash

BCC-2013-1

Organização por Hash Páginas do arquivo de índice são agrupadas por buckets

Bucket é determinado aplicando-se uma função h ao campo de procura

Exemplo: estamos procurando todos os empregados de salário = 5000Como encontrá-los rapidamente ?

Indice organizado por hash no campo SalárioFunção hash: mod 3Onde estão os rids dos empregados com salário = 5000 ?5000 mod 3 = 2 Resposta: bucket 2

Bucket 1 Bucket 2 Bucket 3

BCC-2013-1

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

BCC-2013-1

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

BCC-2013-1

Tipos de indices

Relação entre a maneira como são organizados os dados no índice e no arquivo de dados

Agrupado – não agrupado Densos – esparsos Primários – secundários Simples - compostos

BCC-2013-1

Indices Agrupados

Agrupados : a ordem dos registros é compatível com a ordem das entradas no arquivo de índice.

Se entrada é do tipo (chave, rid) e o índice é agrupado então os registros de dados são ordenados por chave.

Somente um índice agrupado do tipo (chave,rid)

BCC-2013-1

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

BCC-2013-1

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

BCC-2013-1

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

5000

3000

3500

3500

4000

Registros de dadosEntradas

H

4000

H(sal) = 01

H(sal) = 11

H(sal) = 00

BCC-2013-1

Vantagens e desvantagens

Desvantagem : grande overhead para mover registros a fim de preservar a ordem depois de inserções e deleções.

Vantagem : Seleções do tipo = ou <> são altamente otimizadas caso os registros sejam ordenados de acordo com a chave do indice. Rids das entradas apontam para registros contíguos, menos

páginas são manipuladas.