20
Outros Tipos de Índices Arquitetura e Desempenho de Banco de Dados INF01023 - 2011/1 Samuel Salamon - 173255

Outros Tipos de Índices

Embed Size (px)

DESCRIPTION

Outros tipos de índices usados para indexação de arquivos.

Citation preview

Page 1: Outros Tipos de Índices

Outros Tipos de Índices

Arquitetura e Desempenho de Banco de DadosINF01023 - 2011/1

Samuel Salamon - 173255

Page 2: Outros Tipos de Índices

Índices

Existem vários tipos de índices:

• em nível único• multinível• multinível dinâmico• índices em chaves múltiplas

Page 3: Outros Tipos de Índices

Outros Tipos de Índice

    Pode-se usar hashing e outras estruturas de acesso baseadas em hashing como índices:

• hashing estático• hashing dinâmico

Page 4: Outros Tipos de Índices

Outros Tipos de Índice

    Pode-se usar hashing e outras estruturas de acesso baseadas em hashing como índices:

• hashing estático• hashing dinâmico

Page 5: Outros Tipos de Índices

Hashing Estático

Hash é realizar a função h(k) sobre a chave k e transformá-la em um endereço, que é usado para recuperação de dados.

Vantagem:

– Evita o acesso a uma estrutura de índice

Desvantagem:

– Pode causar colisões entre chaves

– Tamanho fixo

Page 6: Outros Tipos de Índices

Hashing Estático

Exemplo:

80 registros de pessoas Chave é o nome de pessoa h(k) → multiplicar os valores ASCII dos 2 primeiros caracteres de k. Considerar os 3 últimos dígitos.

Page 7: Outros Tipos de Índices

Exemplo

J O Ã O

Page 8: Outros Tipos de Índices

Exemplo

J O Ã O

Page 9: Outros Tipos de Índices

Exemplo

J O Ã O

Page 10: Outros Tipos de Índices

Exemplo

J O Ã O

74

Page 11: Outros Tipos de Índices

Exemplo

J O Ã O

7974

Page 12: Outros Tipos de Índices

Exemplo

J O Ã O

7974

74(J) x 79(O) = 5846

Page 13: Outros Tipos de Índices

Exemplo

J O Ã O

7974

74(J) x 79(O) = 5846

Page 14: Outros Tipos de Índices

Problemas

Problemas neste exemplo:

Muitas colisões; Combinações disperdiçadas (ex.: xz, yt...);

Page 15: Outros Tipos de Índices

Outros Tipos de Índice

    Pode-se usar hashing e outras estruturas de acesso baseadas em hashing como índices:

• hashing estático• hashing dinâmico

Page 16: Outros Tipos de Índices

Outros Tipos de Índice

    Pode-se usar hashing e outras estruturas de acesso baseadas em hashing como índices:

• hashing estático• hashing dinâmico

Page 17: Outros Tipos de Índices

Hashing Dinâmico

Função h(k) adaptada para a variação de tamanho no banco de dados. Hashing extensível

Page 18: Outros Tipos de Índices

Hashing Extensível

Divide e une os buckets enquanto o banco cresce/diminui Eficiência de espaço é mantida Função gera valores por intervalos relativamente grandes Buckets criados por demanda

Page 19: Outros Tipos de Índices

Hashing – Estático x Dinâmico

Vantagens do hashing dinâmico:

Desempenho mantido quando o banco aumenta Sobrecarga de espaço mínima Sem necessidade de reservar buckets

Desvantagens: Exclusão é um processo demorado

Page 20: Outros Tipos de Índices

Considerações Finais

A principal diferença entre hashing estático e dinâmico é a capacidade de mudar o tamanho da tabela da hashing dinâmico.

Porém, ambos ainda são suscetíveis às colisões causadas pela escolha da função de hash.