GoSuda

Mapa de bits vibrante

By snowmerak
views ...

¿Qué es un Bitmap?

El bitmap aquí es un tipo de índice. Si vino pensando en gráficos, puede pulsar el botón de atrás.

Concepto Básico

Un bitmap es una forma de tecnología de indexación de bases de datos. Representa el valor de una columna específica como un arreglo de bits o como un elemento o forma de un vector, donde cada bit indica la presencia o ausencia de un valor específico para esa columna. Por lo tanto, la forma más básica es asignar un índice de bits a cada row y representar su existencia con 0 y 1.

Por ejemplo, supongamos que tenemos una tabla con una columna de género. Supongamos que esta tabla tiene 5 rows, y los valores de la columna de género son los siguientes:

  1. Masculino
  2. Femenino
  3. Masculino
  4. Femenino
  5. Otro

En este caso, el índice bitmap para la columna de género se puede expresar de la siguiente manera:

  • Masculino: 10100
  • Femenino: 01010
  • Otro: 00001

Entonces, ¿dónde se utiliza realmente?

Por lo tanto, todos pensarán que no se trata simplemente de representar eso. Para utilizar correctamente el índice bitmap, consideremos el siguiente 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);

Supongamos que esta tabla tiene 1,000,000 de rows. Y supongamos que ejecutamos la siguiente consulta.

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

Esta consulta busca las rows donde las columnas active y sex son ambas TRUE. Entonces, la forma más rápida de encontrar las rows que cumplen la condición de que ambas columnas sean TRUE será utilizando la operación bit AND.

  • Supongamos que el índice bitmap para la columna active está preindexado como 1100110011... (un arreglo de 1,000,000 de bits), y
  • Supongamos que el índice bitmap para la columna sex está preindexado como 1010101010... (un arreglo de 1,000,000 de bits).

Entonces, al realizar la operación bit AND en los dos índices bitmap, se pueden encontrar rápidamente las rows donde ambas columnas son TRUE. Dado que es una simple operación de bits, el resultado se podrá obtener mucho más rápido que con otros escaneos de índices.

Trade-offs

El índice bitmap puede ser muy eficiente, pero tiene algunos trade-offs. Aunque existen muchas otras desventajas, por ahora solo mencionaremos una.

El índice bitmap es más adecuado para baja cardinalidad (es decir, cuando el número de valores posibles en la columna es pequeño). Si se utiliza un índice bitmap en una columna de alta cardinalidad, el bitmap puede volverse muy grande.

Si se utiliza un índice bitmap en una columna de alta cardinalidad, se debe generar un bitmap separado para cada valor único, lo que puede requerir mucho espacio de almacenamiento. Por ejemplo, si una columna tiene 1,000,000 de valores únicos, se deben generar 1,000,000 de bitmaps, lo que puede ser muy ineficiente.

Entonces nosotros

Para sustituir el bitmap que surge de la alta cardinalidad, se puede utilizar algo llamado Roaring Bitmap. Roaring Bitmap tiene varias características, pero la filosofía y característica fundamental más importante es seleccionar dinámicamente el método de almacenamiento más adecuado según la densidad de los datos para maximizar tanto la tasa de compresión como la velocidad de operación.

Concepto Básico de Roaring Bitmap

Indexación de 2 Fases

Para almacenar un entero, Roaring Bitmap primero pasa por las siguientes 2 fases. Aunque se le llama indexación de 2 fases, simplemente se puede pensar como un arreglo bidimensional.

  • Extracción de los 16 bits superiores: Se extraen los 16 bits superiores del entero y se utilizan como índice. Este se convierte en el índice del arreglo exterior de un arreglo bidimensional con una longitud total de 65536. Este arreglo almacena la dirección del contenedor que se describirá a continuación.
  • Extracción de los 16 bits inferiores: Se extraen los 16 bits inferiores del entero y se utilizan como la posición dentro del contenedor.

Contenedor

Este contenedor corresponde al arreglo interior en la analogía del arreglo bidimensional. Sin embargo, a diferencia de los 16 bits superiores, la estructura interna de este contenedor varía según la cantidad de datos internos. Roaring Bitmap admite los siguientes 3 tipos de contenedores.

  • Array Container: Este contenedor se utiliza cuando hay pocos datos almacenados internamente. Específicamente, se utiliza para almacenar 4096 elementos o menos. Este contenedor está implementado simplemente como un arreglo de enteros ordenados. Los elementos se pueden encontrar mediante búsqueda binaria.
  • Bitmap Container: Este contenedor se utiliza cuando hay muchos datos almacenados internamente. Específicamente, se utiliza para almacenar más de 4096 elementos. Este contenedor está implementado como un bitmap de 65536 bits (8192 bytes). Cada bit indica la presencia o ausencia del entero en esa posición.
  • Run Container: Este contenedor se utiliza para almacenar rangos de enteros consecutivos. Por ejemplo, es eficiente para almacenar enteros consecutivos como 1, 2, 3, 4, 5. Este contenedor está implementado como una lista de pares (valor de inicio, longitud). ¿Y si están todos? Simplemente significa que están todos de principio a fin, por lo que solo se almacena (0, 65536).

Este enfoque permite que Roaring Bitmap utilice la memoria de manera muy eficiente y ofrezca un rendimiento óptimo para diversas densidades de datos.

Funcionalidad de Roaring Bitmap

Funcionalidades Básicas

Roaring Bitmap proporciona las siguientes funcionalidades básicas.

  • Inserción: Agrega un nuevo entero al bitmap. En este proceso, se puede seleccionar el contenedor apropiado o transformar el contenedor según sea necesario.
  • Eliminación: Elimina un entero existente del bitmap. En este proceso, se realiza el tratamiento apropiado según el estado del contenedor.
  • Búsqueda: Verifica la existencia de un entero específico en el bitmap. Este proceso se realiza muy rápidamente.

Operaciones de Conjunto

Roaring Bitmap también admite las siguientes operaciones de conjunto.

  • Unión (Union): Crea un nuevo bitmap que incluye todos los elementos de ambos bitmaps.
  • Intersección (Intersection): Crea un nuevo bitmap que incluye solo los elementos presentes en ambos bitmaps.
  • Diferencia Simétrica (Symmetric Difference): Crea un nuevo bitmap que incluye los elementos que están presentes solo en uno de los dos bitmaps.

Estas operaciones están optimizadas según el tipo de contenedor del bitmap y se realizan muy rápidamente.

En el Lenguaje Go

En el lenguaje Go, se puede utilizar fácilmente Roaring Bitmap usando el paquete github.com/RoaringBitmap/roaring. Este paquete proporciona todas las funcionalidades de Roaring Bitmap y está optimizado para las características del lenguaje Go.

Instalación

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

Ejemplo 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)     // Inicializado con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializado con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Añadir 5
14	b2.Add(10) // Añadir 10
15
16	b2.Remove(12) // Eliminar 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// La operación bitmap modifica el original, por lo que se utiliza una copia
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]

Las principales funcionalidades que no se muestran en el código de ejemplo anterior son:

  • Contains(x uint32) bool: Verifica si un valor específico existe en el bitmap
  • GetCardinality() uint64: Devuelve el número de elementos incluidos en el bitmap
  • Rank(x uint32) uint64: Devuelve el número de elementos menores o iguales a un valor específico
  • ToBytes() ([]byte, error): Serializa el bitmap en un slice de bytes
  • FromBytes(data []byte) error: Restaura el bitmap a partir de un slice de bytes
  • Clone() *Bitmap: Crea un clon del bitmap
  • Clear(): Inicializa el bitmap
  • NextValue(x uint32) int64: Devuelve el siguiente elemento mayor o igual a x
  • PreviousValue(x uint32) int64: Devuelve el elemento menor o
  • Maximum() uint32: Devuelve el elemento más grande en el bitmap
  • Minimum() uint32: Devuelve el elemento más pequeño en el bitmap

Estas funcionalidades están disponibles. Consulte la documentación oficial para obtener más detalles.

Cabe señalar que el paquete roaring incluye un paquete que admite uint64 además de uint32 internamente. Dado que proporciona casi la misma interfaz, se puede intercambiar y utilizar inmediatamente.

 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)     // Inicializado con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializado con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Añadir 5
14	b2.Add(10) // Añadir 10
15
16	b2.Remove(12) // Eliminar 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// La operación bitmap modifica el original, por lo que se utiliza una copia
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}

Conclusión

Roaring Bitmap es una herramienta poderosa que puede almacenar y manipular eficientemente conjuntos de enteros de alta cardinalidad. Al utilizar el paquete github.com/RoaringBitmap/roaring en el lenguaje Go, se pueden aprovechar fácilmente todas las funcionalidades de Roaring Bitmap. Este paquete maximiza el uso de la memoria y el rendimiento a través de diversos tipos de contenedores y operaciones optimizadas. Roaring Bitmap puede utilizarse en diversos campos, como la indexación de bases de datos, el análisis de registros y el cálculo estadístico, para lograr un procesamiento de datos eficiente.

Roaring Bitmap ofrece un alto rendimiento, especialmente en conjuntos de datos a gran escala, y puede utilizarse de manera útil en diversas aplicaciones. Combinado con la sintaxis concisa y eficiente del lenguaje Go, Roaring Bitmap proporciona una herramienta poderosa a los desarrolladores. Se espera que, junto con la evolución de Roaring Bitmap, se logren más funcionalidades y optimizaciones en el futuro.

¿Por qué hice esto? Para la indexación por etiqueta y la rápida operación de unión en bases de datos de series temporales.