Organização de ArquivosTipos de Indices

Cálculo de Custos de I/O em Arquivos Heap

RESUMO DA AULA 5 Profa. Sandra de Amo

GBC053 – BCC2012-2

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.

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)

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

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

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)

Indices do tipo (chave, rid) baseados em Hash, não podem ser agrupados, pois não podem armazenar as entradas ordenadas pela chave.

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

Indices Densos

Densos : se para cada valor v da chave de busca existe uma entrada (v,rid).

Não-denso = esparso

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)

11/04/23 SBD - Mestrado em Computação 13

Custo de Operações em Arquivos Heap (sequenciais)

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