Guia de Índices em Bancos de Dados: Tipos e Estruturas

Índice é uma estrutura (ou arquivo) auxiliar associada a uma tabela (ou coleção de dados). Sua função é acelerar o tempo de acesso às linhas de uma tabela, criando ponteiros para os dados armazenados em colunas específicas.

Índices ordenados: baseiam-se na ordenação de valores, permitem acesso aleatório rápido aos registros de um arquivo.

Índices hash: baseiam-se na distribuição uniforme dos valores por meio de uma faixa de buckets (baldes). O bucket ao qual um valor é atribuído é determinado por uma função, chamada de função hash.

Em quais fatores devemos nos basear para escolher a melhor técnica de índice?

• Tipo de acesso: acessos eficientes
• Tempo de acesso: depende da técnica
• Tempo de inserção: localizar e atualizar
• Tempo de exclusão: localizar e atualizar
• Espaço adicional: espaço vs desempenho

Índice primário: o arquivo e/ou tabela que contém os registros está ordenada sequencialmente pela mesma chave de procura do índice. Em geral, a chave de procura de um índice primário é a chave primária, embora nem sempre isso ocorra.

Índice secundário: são os índices cuja chave de procura está em uma ordem diferente da ordem do arquivo e/ou tabela.

Índices densos: um registro de índice (ou entrada de índice) aparece para cada valor de chave de procura no arquivo/tabela. O registro do índice contém o valor da chave de procura e um ponteiro para o primeiro registro de dados com esse valor.

Índices esparsos: um registro de índice é criado apenas para alguns dos valores do arquivo/tabela. Também em cada registro contém o valor da chave de procura e um ponteiro para o primeiro registro de dados com esse valor.

Árvore binária ou B-Tree (Binary Tree): um índice Árvore-B+ tem a forma de uma árvore balanceada, na qual todos os caminhos a partir da raiz da árvore até uma de suas folhas têm o mesmo comprimento. O desempenho dos índices sequenciais se degrada conforme o arquivo cresce. A tecnologia de índice B-Tree permite buscas muito eficientes mesmo em gigantescas bases de dados. Praticamente todos os bancos de dados SQL baseiam-se nesse padrão de buscas.

Índice hashing estático: baseiam-se na distribuição uniforme dos valores por meio de uma faixa de buckets (baldes). O bucket ao qual um valor é atribuído é determinado por uma função, chamada de função hash. Distribui as chaves armazenadas uniformemente por todos os buckets.

Estouro de bucket (overflows de bucket): quando um registro é inserido e o bucket para o qual o registro deve ser inserido não possui espaço suficiente, ocorre um overflow de bucket ou estouro de bucket. Acontece devido a: Buckets insuficientes: o número de buckets (nb) deve ser escolhido tal que nb > nr/fr, em que nr denota o número total de registros e fr denota o número de registros que caberão em um bucket. A solução é criar buckets de estouro ou buckets de overflow.

Índices primários são a melhor forma de utilizar, pois apontam direto para a tabela.

Índices de hash são a melhor forma de utilizar, pois vão ser apontados direto para aquele bucket em que o valor está armazenado.