Cálculos de Custos I/O-Arquivos Hash
Introdução aos Métodos de Acesso
RESUMO AULA 7
Profa. Sandra de Amo
GBC053 – BCC
2012-2
Lembrando:

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
Resumo - Hash
Scan
Sel =
chave
Sel =
Sel
Nchav <>
Insert Delete
sel
e
1.25B
(D+RC)
1.25BD
H+D+
RC
D
1.25B(D+ 1.25B(D+ H+2D+ C Sel +
RC)
RC)
D + RC
1.25BD 1.25BD
2D
Sel+D
Escolha de uma Boa Organização
Scan
Sel =
chave
Sel =
Sel <>
BD
0.5BD
BD
BD
Ord
BD
Dlog2B
Dlog2B
Dlog2B +
B/2(D+RC)
1.25BD
D
Delete
2D
2D+Sel
Nchave
Heap
Hash
Insert
1.25BD
1.25BD
Dlog2B Dlog2B
+
+
D
D
2D
Sel+D
ISAM - Motivação




Quais os empregados com salário > 2000 ?
Busca binária no arquivo de índice até
encontrar o primeiro salário > 2000
Escaneia o arquivo de índice a partir deste
ponto e lê os registros correspondentes.
Se o arquivo de índice é muito grande : busca
binária pode ser dispendiosa.
Idéia
Criar um segundo arquivo
com um registro para cada
página do arquivo de
indice original


<primeira chave da
página, ponteiro da
página>
Ordenado por chave
Como são os nós internos da estrutura
ISAM ?
Pi = ponteiros que apontam para um núm. de página no nível imediatamente inferior
Ki = valor do atributo chave do índice.
Exemplo: se o atributo chave é idade então Ki é um valor de idade.
P0 K1 P1 K2 P2 K3
...
Pi
K < Ki+1
Valores K da chave nesta página
são < Ki+1
Ki+1 Pi+1 ...
Km Pm
K ≥ Ki+1
Valores K da chave nesta página
são ≥ Ki+1
Organização do índice em árvore
Páginas
auxiliares
que permitem
chegar
rapidamente
a uma folha
Páginas do arquivo de índice
Páginas do Arquivo de Dados
Discussão

ISAM é uma estrutura estática
 Na criação do arquivo
 Páginas primárias (folhas) são alocadas
 20% de cada página é livre para posteriores inserções,
tentando “adiar” ao máximo a criação de páginas
de overflow
 Páginas intermediárias são criadas.
 Manutenção :
 Páginas de overflow são alocadas à medida que as
páginas primárias do índice ficam cheias em
decorrência de inserções.
Esquema Geral do Método ISAM
Páginas
dos arquivos
de indices
(a partir da
2a camada)
Páginas de overflow
Páginas primárias –
as entradas do arquivo de
índice da primeira
camada
Busca na estrutura ISAM
Exemplo: Busca da chave 27
Em cada nível da estrutura:
P0,K1,P1,K2,...,Km,Pm
m chaves e m+1 ponteiros




Se 27 < K1: transfere a busca para a página apontada por P0
Se 27 ≥ Km: transfere a busca para a página apontada por Pm
Caso contrário: varre-se a página para encontrar chaves K1,
K2 tais que Ki ≤ 27 < Ki+1
Transfere a busca para a página apontada por Pi
Exemplo: Busca de um registro de
dados
Busca da chave 27
Raiz
40
20
10* 15*
51
33
20* 27*
33*
37*
40*
46*
63
51*
55*
63*
97*
Inserção de um registro
Inserção de 23*, 48*, 41*, 42*
Raiz
40
20
10* 15*
51
33
20* 27*
23*
Página de Overflow
33*
37*
40*
46*
48*
41*
42*
63
51*
55*
63*
97*
Deleção de um registro
Deleção de 42*, 51*, 97*
Procura 51*
Raiz
Nunca são
alteradas !!
40
20
10* 15*
51
33
20* 27*
23*
Pagina de Overflow
33*
37*
40*
46*
48*
41*
42*
63
51*
55*
63*
97*
Custo para chegar em uma folha

Número de I/O = número de níveis da árvore
 Capacidade de cada página = F =
número de ponteiros saindo de cada página
 Total de páginas primárias = N
 Número de níveis = logF N

Logo Custo I/O para chegar em uma folha = logF N
Comparação de Custos
Custo de uma busca A = a
Arquivo de 1 000 000 registros

10 registros por página de dados : total de páginas = 100 000

100 ponteiros em cada página de índice (99 entradas (chave,pt) +
ponteiro P0)
Arquivo não ordenado por A

Scan = 1000 000/10 = 100000 I/0
Arquivo ordenado por A

Busca binária = log2 100000 = 17 I/0
Arquivo estruturado usando método ISAM






Arquivo de indice usa alternativa 1 (registro do indice = registro de
dados)
Custo = log100 100000 = entre 2 e 3 I/0, pois
1002 < 100000 < 1003