Índice Hash - Aula 04/11 - Bancos de Dados 2020.2
Introdução ao Armazenamento de Dados em Bancos de Dados
Contexto do Curso
- André apresenta a terceira parte de uma série de vídeos sobre como os bancos de dados armazenam dados no disco, parte de um curso na Unicamp.
- Recomenda assistir aos vídeos anteriores para entender a introdução sobre o armazenamento físico e a organização dos registros.
Estruturas de Índice
- O vídeo foca na estrutura interna dos índices, além da ideia inicial de que um índice é apenas uma lista ordenada.
- Introduz o conceito de índices baseados em hashing, que utilizam funções hash para determinar onde os dados são armazenados.
Funções Hash e Colisões
Funcionamento do Hashing
- Explica como um registro com chave (ex: 1234) é gravado no disco usando uma função hash que determina sua posição.
- Demonstra um exemplo simples onde as duas primeiras cifras da chave definem a posição no disco.
Problemas com Colisões
- Discute o problema das colisões quando dois registros caem na mesma posição, apresentando soluções como listas encadeadas ou busca pela próxima posição disponível.
- Apresenta estratégias para lidar com colisões utilizando blocos físicos, permitindo ler e gravar múltiplos registros simultaneamente.
Buckets e Organização Eficiente
Conceito de Buckets
- Introduz o conceito de "Bucket", onde registros são organizados em blocos maiores ao invés de unidades individuais.
- Explica que, ao usar buckets, colisões resultam em registros caindo no mesmo bloco, facilitando a busca sequencial na memória.
Estratégias Adicionais para Colisões
- Menciona que se muitos registros excederem a capacidade do bucket, outras estratégias devem ser aplicadas para gerenciar essas colisões.
Índices Hash e Estruturas Avançadas
Estrutura do Índice Hash
- Descreve como um índice hash funciona em dois estágios: primeiro calculando uma entrada através da função hash e depois apontando para onde o registro está guardado.
Combinação com Buckets
- Fala sobre a possibilidade de combinar índices hash com buckets, permitindo maior flexibilidade na gestão dos dados.
Exemplificação do Hashing Extensível
Estruturas de Dados e Colisões em Hashing
Funcionamento Básico do Hashing
- O processo de hashing gera uma sequência binária a partir de entradas, onde cada entrada aponta para um "Bucket". Mesmo com colisões, como no caso de "Lucinda" e "Doriana", ambas podem ser armazenadas no mesmo Bucket.
Gerenciamento de Buckets
- Ao adicionar mais registros, pode-se atingir a capacidade máxima de um Bucket. Isso leva à necessidade de estratégias para gerenciar o estouro da capacidade.
Estratégias para Resolução de Colisões
- É possível que duas entradas do índice apontem para o mesmo Bucket. A estratégia envolve desmembrar os Buckets quando eles atingem sua capacidade máxima.
- Quando um Bucket estoura, ele pode ser dividido em dois novos Buckets, permitindo que cada índice aponte para seu próprio espaço.
Níveis Múltiplos em Hashing
- O conceito permite criar índices hash multinível, onde diferentes níveis podem resolver colisões através da estrutura hierárquica dos Buckets.
Uso de Árvores na Estruturação do Hashing
- A ideia é combinar hashing com estruturas em árvore. Um índice binário pode ser organizado em uma árvore, onde diferentes caminhos levam a diferentes Buckets baseados nos bits utilizados.
- Com apenas dois bits, é possível determinar qual Bucket utilizar. Essa abordagem permite granularidade na alocação dos dados.
Vantagens das Estruturas em Árvore
- As árvores permitem adicionar níveis conforme necessário. Se um Bucket atinge sua capacidade máxima, um novo nível pode ser adicionado à árvore para melhor gerenciamento das colisões.
- Essa flexibilidade na estruturação ajuda a lidar eficientemente com colisões e otimiza o armazenamento dos dados.
Conceito de Perfect Hashing