GoSuda

Mappa di bit vivace

By snowmerak views ...

Che cos'è una bitmap?

Qui la bitmap è un tipo di indice. Se sei arrivato pensando alla grafica, puoi tornare indietro.

Concetto di base

La bitmap è una forma di tecnica di indicizzazione dei database. Il valore di una determinata colonna viene rappresentato come un elemento o una forma di un array di bit o di un vettore, e ogni bit indica se un determinato valore della colonna è presente o meno. Quindi, la forma più elementare consiste nell'assegnare un indice di bit a ogni riga ed esprimere la presenza o l'assenza con 0 e 1.

Ad esempio, supponiamo di avere una tabella con una colonna di genere. Supponiamo che questa tabella contenga 5 righe e che i valori della colonna di genere siano i seguenti:

  1. Maschio
  2. Femmina
  3. Maschio
  4. Femmina
  5. Altro

In questo caso, l'indice bitmap per la colonna di genere può essere rappresentato come segue:

  • Maschio: 10100
  • Femmina: 01010
  • Altro: 00001

Dove si usa davvero

Probabilmente tutti penseranno che non serva semplicemente a rappresentare questo. Per utilizzare correttamente l'indice bitmap, consideriamo il seguente 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);

Supponiamo che questa tabella contenga 1.000.000 di righe e che venga eseguita la seguente query.

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

Questa query trova le righe in cui le colonne active e sex sono entrambe TRUE. In tal caso, un modo per trovare nel modo più rapido le righe che soddisfano la condizione che entrambe le colonne siano TRUE è utilizzare l'operazione bit and.

  • Si supponga che l'indice bitmap della colonna active sia già stato indicizzato come 1100110011... (array di 1.000.000 di bit).
  • Si supponga che l'indice bitmap della colonna sex sia già stato indicizzato come 1010101010... (array di 1.000.000 di bit).

In questo modo, eseguendo l'operazione bit and sui due indici bitmap, è possibile trovare rapidamente le righe in cui entrambe le colonne sono TRUE. Trattandosi di una semplice operazione sui bit, il risultato si ottiene molto più rapidamente rispetto ad altre scansioni dell'indice.

Compromessi

Sebbene l'indice bitmap possa essere molto efficiente, presenta alcuni compromessi. Ci sono molti altri svantaggi, ma per ora ne evidenzierò soltanto uno.

Si tratta del fatto che l'indice bitmap è più adatto a una bassa cardinalità (ovvero, quando il numero di valori possibili per una colonna è ridotto). Utilizzando un indice bitmap su una colonna ad alta cardinalità, la bitmap può diventare molto grande.

Utilizzando un indice bitmap su una colonna ad alta cardinalità, è necessario generare una bitmap separata per ciascun valore distinto, il che può richiedere molto spazio di archiviazione. Ad esempio, se una colonna contiene 1.000.000 di valori distinti, occorre generare 1.000.000 di bitmap, e ciò può risultare estremamente inefficiente.

Quindi noi

Per sostituire le bitmap che derivano dalla cardinalità elevata, si può utilizzare una struttura chiamata Roaring Bitmap. Roaring Bitmap presenta diverse caratteristiche, ma il suo principio fondamentale e la sua caratteristica principale sono selezionare dinamicamente il metodo di memorizzazione più adatto in base alla densità dei dati, massimizzando sia il tasso di compressione sia la velocità delle operazioni.

Concetto di base di Roaring Bitmap

Indicizzazione a due livelli

Per memorizzare un intero, Roaring Bitmap attraversa innanzitutto i seguenti due livelli. Pur trattandosi di un'indicizzazione a due livelli, è sufficiente pensarla come un semplice array bidimensionale.

  • Estrazione dei 16 bit superiori: i 16 bit superiori dell'intero vengono estratti e utilizzati come indice. Si tratta dell'indice dell'array esterno di un array bidimensionale di lunghezza complessiva 65536. Questo array memorizza l'indirizzo del contenitore descritto in seguito.
  • Estrazione dei 16 bit inferiori: i 16 bit inferiori dell'intero vengono estratti e utilizzati come posizione all'interno del contenitore.

Contenitore

Questo contenitore corrisponde all'array interno dell'array bidimensionale, come appena paragonato. Tuttavia, a differenza di quello dei 16 bit superiori, la struttura interna di questo contenitore varia in base alla quantità di dati che contiene. Roaring Bitmap supporta i seguenti 3 tipi di contenitore.

  • Array Container: questo contenitore viene utilizzato quando i dati memorizzati al suo interno sono pochi. In particolare, viene utilizzato per memorizzare fino a 4096 elementi. Questo contenitore è implementato come un semplice array di interi ordinato. È possibile trovare un elemento mediante la ricerca binaria.
  • Bitmap Container: questo contenitore viene utilizzato quando i dati memorizzati al suo interno sono numerosi. In particolare, viene utilizzato per memorizzare più di 4096 elementi. Questo contenitore è implementato come una bitmap di 65536 bit (8192 byte). Ogni bit indica se l'intero nella posizione corrispondente è presente o meno.
  • Run Container: questo contenitore viene utilizzato per memorizzare intervalli di interi consecutivi. Ad esempio, è efficiente per memorizzare interi consecutivi come 1, 2, 3, 4, 5. Questo contenitore è implementato come una lista di coppie (valore iniziale, lunghezza). E se sono presenti tutti? Significa semplicemente che sono presenti dall'inizio alla fine, quindi è sufficiente memorizzare un solo (0, 65536).

Questo metodo consente a Roaring Bitmap di utilizzare la memoria in modo molto efficiente e di offrire prestazioni ottimali per diverse densità di dati.

Funzionalità di Roaring Bitmap

Funzionalità di base

Roaring Bitmap offre le seguenti funzionalità di base.

  • Inserimento: aggiunge un nuovo intero alla bitmap. In questo processo è possibile selezionare il contenitore appropriato oppure convertire il contenitore quando necessario.
  • Eliminazione: rimuove un intero esistente dalla bitmap. Anche in questo processo viene eseguita un'elaborazione appropriata in base allo stato del contenitore.
  • Ricerca: verifica se un determinato intero è presente nella bitmap. Questo processo viene eseguito in modo molto rapido.

Operazioni insiemistiche

Roaring Bitmap supporta inoltre le seguenti operazioni insiemistiche.

  • Unione (Union): crea una nuova bitmap che contiene tutti gli elementi di due bitmap.
  • Intersezione (Intersection): crea una nuova bitmap che contiene solo gli elementi presenti in entrambe le bitmap.
  • Differenza simmetrica (Symmetric Difference): crea una nuova bitmap che contiene gli elementi presenti in una sola delle due bitmap.

Queste operazioni sono ottimizzate in base al tipo di contenitore della bitmap e vengono eseguite in modo molto rapido.

In Go

In Go è possibile utilizzare facilmente Roaring Bitmap tramite il pacchetto github.com/RoaringBitmap/roaring. Questo pacchetto fornisce tutte le funzionalità di Roaring Bitmap ed è ottimizzato in base alle caratteristiche di Go.

Installazione

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

Esempio d'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)     // inizializzazione con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // inizializzazione con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // aggiunta di 5
14	b2.Add(10) // aggiunta di 10
15
16	b2.Remove(12) // rimozione di 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// le operazioni sulla bitmap modificano l'originale, quindi si usa 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]

Tra le altre funzionalità principali non presenti nell'esempio di codice sopra si trovano:

  • Contains(x uint32) bool: verifica se un determinato valore è presente nella bitmap
  • GetCardinality() uint64: restituisce il numero di elementi contenuti nella bitmap
  • Rank(x uint32) uint64: restituisce il numero di elementi minori o uguali a un determinato valore
  • ToBytes() ([]byte, error): serializza la bitmap in uno slice di byte
  • FromBytes(data []byte) error: ripristina la bitmap da uno slice di byte
  • Clone() *Bitmap: crea una copia della bitmap
  • Clear(): inizializza la bitmap
  • NextValue(x uint32) int64: restituisce il successivo elemento maggiore o uguale a x
  • PreviousValue(x uint32) int64: restituisce il precedente elemento minore o uguale a x
  • Maximum() uint32: restituisce l'elemento più grande della bitmap
  • Minimum() uint32: restituisce l'elemento più piccolo della bitmap

Queste sono le funzionalità disponibili. Per maggiori dettagli, consulta la documentazione ufficiale.

Va inoltre precisato che il pacchetto roaring include al suo interno un pacchetto che supporta non solo uint32 ma anche uint64. Poiché fornisce un'interfaccia quasi identica, può essere sostituito direttamente.

 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)     // inizializzazione con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // inizializzazione con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // aggiunta di 5
14	b2.Add(10) // aggiunta di 10
15
16	b2.Remove(12) // rimozione di 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// le operazioni sulla bitmap modificano l'originale, quindi si usa 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}

Conclusioni

Roaring Bitmap è uno strumento potente per memorizzare e manipolare in modo efficiente insiemi di interi ad alta cardinalità. Utilizzando il pacchetto github.com/RoaringBitmap/roaring in Go, è possibile sfruttare facilmente tutte le funzionalità di Roaring Bitmap. Questo pacchetto massimizza l'utilizzo della memoria e le prestazioni grazie a diversi tipi di contenitore e a operazioni ottimizzate. Roaring Bitmap può essere impiegato in vari ambiti, come l'indicizzazione dei database, l'analisi dei log e il calcolo statistico, per realizzare un'elaborazione dei dati efficiente.

Roaring Bitmap offre prestazioni elevate soprattutto con insiemi di dati di grandi dimensioni e può essere utilizzato con profitto in molte applicazioni. Combinato con la sintassi concisa ed efficiente di Go, Roaring Bitmap fornisce agli sviluppatori uno strumento potente. In futuro, con lo sviluppo di Roaring Bitmap, sono attesi ulteriori funzionalità e miglioramenti.

Perché ho fatto questo? Per l'indicizzazione di ciascun tag e per le rapide operazioni di unione in un database di serie temporali.