GoSuda

Bitmap Animado

By snowmerak
views ...

O que é um Bitmap?

Aqui, um bitmap é um tipo de índice. Se você veio pensando em gráficos, pode voltar.

Conceito Básico

Um bitmap é uma forma de tecnologia de indexação de banco de dados. Ele representa os valores de uma coluna específica como um elemento ou forma de um array ou vetor de bits, onde cada bit indica a existência de um valor particular para essa coluna. Assim, a forma mais básica é atribuir um índice de bit a cada linha e representar a existência como 0 ou 1.

Por exemplo, suponha que temos uma tabela com uma coluna de sexo. Assumamos que esta tabela tem 5 linhas e os valores da coluna de sexo são os seguintes:

  1. Masculino
  2. Feminino
  3. Masculino
  4. Feminino
  5. Outro

Nesse caso, o índice de bitmap para a coluna de sexo pode ser representado da seguinte forma:

  • Masculino: 10100
  • Feminino: 01010
  • Outro: 00001

Onde ele é realmente usado

Portanto, todos devem estar pensando que ele não é usado apenas para representar isso. Para usar o índice de bitmap adequadamente, consideremos o seguinte caso.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Suponhamos que esta tabela tenha 1.000.000 de linhas. E suponhamos que executamos a seguinte consulta:

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Esta consulta busca linhas onde as colunas active e sex são ambas TRUE. A maneira mais rápida de encontrar linhas que satisfazem a condição de que ambas as colunas são TRUE seria usar a operação bitwise AND.

  • Suponha que o índice de bitmap para a coluna active já esteja indexado como 1100110011... (array de bits de 1.000.000), e
  • Suponha que o índice de bitmap para a coluna sex já esteja indexado como 1010101010... (array de bits de 1.000.000).

Então, podemos realizar uma operação bitwise AND nos dois índices de bitmap para encontrar rapidamente as linhas onde ambas as colunas são TRUE. Como é uma operação bitwise simples, podemos obter resultados muito mais rapidamente do que com outras varreduras de índice.

Trade-offs

Embora os índices de bitmap possam ser muito eficientes, eles apresentam alguns trade-offs. Existem muitas outras desvantagens, mas por enquanto, abordaremos apenas uma.

Os índices de bitmap são mais adequados para baixa cardinalidade (ou seja, quando o número de valores possíveis em uma coluna é pequeno). Usar um índice de bitmap em uma coluna de alta cardinalidade pode fazer com que o bitmap se torne muito grande.

Se um índice de bitmap for usado em uma coluna de alta cardinalidade, um bitmap separado precisará ser criado para cada valor único, o que pode exigir muito espaço de armazenamento. Por exemplo, se uma coluna tiver 1.000.000 de valores únicos, 1.000.000 de bitmaps precisarão ser criados, o que pode ser muito ineficiente.

Então, nós

Em vez de bitmaps que surgem de alta cardinalidade, podemos usar algo chamado Roaring Bitmap. O Roaring Bitmap possui várias características, mas sua filosofia e característica fundamentais mais importantes são selecionar dinamicamente o método de armazenamento mais adequado com base na densidade dos dados para maximizar a taxa de compressão e a velocidade de operação.

Conceito Básico do Roaring Bitmap

Indexação em 2 Fases

Para armazenar um único inteiro, o Roaring Bitmap primeiro passa pelas seguintes 2 fases. Embora seja chamada de indexação em 2 fases, pode ser pensada simplesmente como um array bidimensional.

  • Extração dos 16 bits superiores: Os 16 bits superiores do inteiro são extraídos e usados como índice. Isso se torna o índice do array externo em um array bidimensional com um comprimento total de 65536. Este array armazena os endereços dos contêineres, que serão discutidos posteriormente.
  • Extração dos 16 bits inferiores: Os 16 bits inferiores do inteiro são extraídos e usados como a posição dentro do contêiner.

Contêiner

Este contêiner corresponde ao array interno no array bidimensional, como mencionado anteriormente. No entanto, diferentemente dos 16 bits superiores, a estrutura interna deste contêiner varia dependendo da quantidade de dados internos. O Roaring Bitmap suporta os seguintes 3 tipos de contêineres:

  • Array Container: Este contêiner é usado quando poucos dados são armazenados internamente. Especificamente, ele é usado para armazenar 4096 ou menos elementos. Este contêiner é implementado simplesmente como um array de inteiros ordenados. Os elementos podem ser encontrados por busca binária.
  • Bitmap Container: Este contêiner é usado quando muitos dados são armazenados internamente. Especificamente, ele é usado para armazenar mais de 4096 elementos. Este contêiner é implementado como um bitmap de 65536 bits (8192 bytes). Cada bit indica a existência de um inteiro nessa posição.
  • Run Container: Este contêiner é usado para armazenar intervalos contínuos de inteiros. Por exemplo, ele é eficiente para armazenar inteiros contínuos como 1, 2, 3, 4, 5. Este contêiner é implementado como uma lista de pares (valor inicial, comprimento). Se todos os valores existirem? Isso significa que todos os valores do início ao fim existem, então apenas (0, 65536) precisa ser armazenado.

Essa abordagem permite que o Roaring Bitmap use a memória de forma muito eficiente e forneça desempenho ideal para várias densidades de dados.

Funcionalidades do Roaring Bitmap

Funcionalidades Básicas

O Roaring Bitmap oferece as seguintes funcionalidades básicas:

  • Inserção: Adiciona um novo inteiro ao bitmap. Durante este processo, um contêiner apropriado pode ser selecionado ou, se necessário, o contêiner pode ser convertido.
  • Exclusão: Remove um inteiro existente do bitmap. Durante este processo, o tratamento apropriado é realizado de acordo com o estado do contêiner.
  • Busca: Verifica se um inteiro específico existe no bitmap. Este processo é executado muito rapidamente.

Operações de Conjunto

O Roaring Bitmap também suporta as seguintes operações de conjunto:

  • União (Union): Cria um novo bitmap que inclui todos os elementos de dois bitmaps.
  • Interseção (Intersection): Cria um novo bitmap que inclui apenas os elementos presentes em ambos os bitmaps.
  • Diferença Simétrica (Symmetric Difference): Cria um novo bitmap que inclui elementos que existem em apenas um dos dois bitmaps.

Essas operações são otimizadas com base no tipo de contêiner do bitmap e são executadas muito rapidamente.

Em Go

Na linguagem Go, você pode usar facilmente o Roaring Bitmap usando o pacote github.com/RoaringBitmap/roaring. Este pacote fornece todas as funcionalidades do Roaring Bitmap e é otimizado para as características da linguagem Go.

Instalação

1go get github.com/RoaringBitmap/roaring/v2

Exemplo de Uso

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Inicializa com 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializa com 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Adiciona 5
14	b2.Add(10) // Adiciona 10
15
16	b2.Remove(12) // Remove 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Como as operações de bitmap modificam o original, use uma cópia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

As principais funcionalidades não mostradas no código de exemplo acima são:

  • Contains(x uint32) bool: Verifica se um valor específico existe no bitmap
  • GetCardinality() uint64: Retorna o número de elementos contidos no bitmap
  • Rank(x uint32) uint64: Retorna o número de elementos menores ou iguais a um valor específico
  • ToBytes() ([]byte, error): Serializa o bitmap para um slice de bytes
  • FromBytes(data []byte) error: Restaura o bitmap de um slice de bytes
  • Clone() *Bitmap: Cria uma cópia do bitmap
  • Clear(): Inicializa o bitmap
  • NextValue(x uint32) int64: Retorna o próximo elemento maior ou igual a x
  • PreviousValue(x uint32) int64: Retorna o próximo elemento menor ou
  • Maximum() uint32: Retorna o maior elemento no bitmap
  • Minimum() uint32: Retorna o menor elemento no bitmap

Essas funcionalidades estão disponíveis. Para detalhes, consulte a documentação oficial.

Observe que o pacote roaring inclui um pacote que suporta uint64, além de uint32. Ele fornece quase a mesma interface, então você pode substituí-los diretamente.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Inicializa com 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializa com 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Adiciona 5
14	b2.Add(10) // Adiciona 10
15
16	b2.Remove(12) // Remove 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Como as operações de bitmap modificam o original, use uma cópia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Conclusão

O Roaring Bitmap é uma ferramenta poderosa para armazenar e manipular eficientemente conjuntos de inteiros de alta cardinalidade. Ao usar o pacote github.com/RoaringBitmap/roaring na linguagem Go, todas as funcionalidades do Roaring Bitmap podem ser facilmente utilizadas. Este pacote maximiza o uso da memória e o desempenho por meio de vários tipos de contêineres e operações otimizadas. O Roaring Bitmap pode ser usado em várias áreas, como indexação de banco de dados, análise de logs e cálculos estatísticos, para implementar um processamento de dados eficiente.

O Roaring Bitmap se destaca particularmente no desempenho com grandes conjuntos de dados e pode ser usado de forma útil em várias aplicações. Combinado com a sintaxe concisa e eficiente da linguagem Go, o Roaring Bitmap oferece uma ferramenta poderosa para os desenvolvedores. Espera-se que mais funcionalidades e otimizações sejam alcançadas com o avanço do Roaring Bitmap.

Por que eu fiz isso? Para indexação por tags e operações rápidas de união em bancos de dados de séries temporais.