Organização de Arquivos
Tipos de Indices
Cálculo de Custos de I/O em
Arquivos Heap
RESUMO DA AULA 5
Profa. Sandra de Amo
GBC053 – BCC
2012-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 1

Bucket 2
Bucket 3
Bucket é determinado aplicando-se uma função h ao campo de procura
Exemplo: estamos procurando todos os empregados de salário = 5000
Como encontrá-los rapidamente ?
Indice organizado por hash no campo Salário
Função hash: mod 3
Onde estão os rids dos empregados com salário = 5000 ?
5000 mod 3 = 2
Resposta: bucket 2
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
2000
Paulo, 44, 2000
2000
Pedro, 35, 2000
2000
Carlos, 44, 2000
2500
José, 40, 2500
3000
João, 35, 3000
3500
Ilmério, 40, 3500
3500
Rodrigo, 40, 3500
4000
Maria, 30, 4000
4000
Sara, 35, 4000
5000
Sabrina, 31, 5000
Entradas
Registros de dados
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
30
Carlos, 44, 2000
31
Ilmério, 40, 3500
35
José
João, 35, 3000
35
Rodrigo
José, 40, 2500
35
Maria, 30, 4000
40
Pedro, 35, 2000
40
Rodrigo, 40, 3500
Sabrina, 31, 5000
40
44
Sara, 35, 4000
44
André
Indice Esparso e Agrupado
Registros de dados
Indice Denso
e não-agrupado
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
Indice em (Idade,Sal)
Indice em Idade
31,80
31
33,75
33
42,10
bob
42
10
42
42,20
cal
31
80
42
joe
42
20
sue
33
75
Indice em Sal
10,42
10
20,42
20
75,33
80,31
75
Indice em (Sal,Idade)
80
Custo de Operações em Arquivos
Heap (sequenciais)
Scan
Sel =
Sel =
chave
Nchave
B(RC+D)
0.5
B(RC+D)
B(D+RC)
BD
0.5BD BD
05/11/2015
Sel <> Insert
Delete
sel
B(D+RC)
2D+C
Sel +
+D+C
BD
2D
Sel+D
SBD - Mestrado em Computação
13