3

Acabo de ler o capítulo 29 do livro Visão geral de Data Warehousing e OLAP

Na página 725 o autor fala sobre técnicas de indexação para dar suporte ao acesso de alto desempenho, essa técnica é chamada de bitmap.

Foi assim que surgiu a dúvida e consequentemente a pergunta.

Fonte: Sistemas de Banco de dados 6ª edição, autores: Elmasri, Ramez Navathe, Shamkant B. Ano: 2011 Capítulo 29, página 725.

1
  • A resposta resolveu o que estava em dúvida? Precisa que algo mais seja melhorado? Acha que é possível aceitá-la agora?
    – Maniero
    26/06/2020 às 13:53

1 Resposta 1

4

Na verdade, isso depende da implementação e do objetivo do índice.

Geralmente o objetivo é reduzir o espaço ocupado no índice e com isso dar melhor performance, além de manter uma estrutura semelhante a um array para acesso das chaves, o que também aumenta a performance.

Idealmente um índice desses deveria ser apenas dois valores possíveis, assim 1 único bit é suficiente para cada chave entrada no índice. Isso é muito eficiente.

Se tiver 4 valores possíveis já precisa de 2 bits. Para 256 valores possíveis precisa de 8 bits.

Conforme vai aumentando e vai se aproximando do tamanho da chave de um índice B-tree o ganho de eficiência vai se tornando menor. Em determinado momento a chave será igual ou maior do que se usasse um B-Tree.

Mas tem implementações que precisam 1 bit para cada valor possível. Isso se dá porque cada chave tem uma estrutura completa com 1 bit para cada entrada da tabela, então se tiver 256 valores possíveis existirão 256 chaves, cada uma com um tamanho equivalente ao número de linhas da tabela divido por 8, ou seja 32 bytes para cada entrada, é claramente pior já que uma entrada no índice B-tree dificilmente terá mais que 25 bytes mesmo em uma implementação complexa e que atende uma quantidade absurda de linhas (geralmente será bem menor que isso).

Tem maneiras de comprimir isso, mas o ganho vai depender da distribuição dos valores, e perde-se a capacidade de leitura posicional como se fosse um array, complexidade O(1).

Dependendo da implementação e da distribuição ele ainda pode compensar mesmo em altíssima cardinalidade, por exemplo ter todos os valores únicos.

Outro ganho se dá quando precisa confrontar dois ou mais índices mapeados por bit. Basta a aplicação de álgebra booleana simples em todo o índice e obtém-se o resultado esperado.

Como a consulta é sempre feita de acordo com a posição da linha na tabela é complicado usar para outras classificações e pode não ter ganho direto. Tem otimizações para isso combinando com B-Tree que minimizam esse problema.

O maior ganho desse tipo de índice é quando ele guarda o resultado de uma expressão booleana de uma condição baseada nas colunas. É raro precisar disso para uso em aplicações. Mas o JOIN e outras operações do banco de dados pode beneficiar-se em um índice criado internamente para controlar o que ele deve pegar naquela query baseando-se em resultados de duas ou mais seleções feitas antes. A existência de um índice assim pode otimizar a consulta por ele não ter que gerar o índice na hora. Por outro lado piora a escrita por ter que atualizar mais um índice.

Um bom banco de dados saberá quando usar um índice bitmap mesmo que ele já exista e quando preferir outro caminho.

Coloquei no GitHub para referência futura.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .