GoSuda

Hartă de biți vibrantă

By snowmerak views ...

Ce este un bitmap?

Aici, bitmap-ul este un tip de index. Dacă ați venit gândindu-vă la grafică, puteți da înapoi.

Concepte de bază

Bitmap-ul este o formă de tehnică de indexare a bazelor de date. Valorile unei coloane specifice sunt reprezentate ca un vector de biți sau ca un element al unui vector de biți, iar fiecare bit indică dacă o anumită valoare a coloanei există sau nu. Astfel, forma cea mai elementară constă în atribuirea unui index de bit fiecărui rând și în reprezentarea existenței prin 0 și 1.

De exemplu, să presupunem că există un tabel cu o coloană de gen. Acest tabel are 5 rânduri, iar valorile coloanei de gen sunt următoarele:

  1. Bărbat
  2. Femeie
  3. Bărbat
  4. Femeie
  5. Altul

În acest caz, indexul bitmap pentru coloana de gen poate fi reprezentat după cum urmează:

  • Bărbat: 10100
  • Femeie: 01010
  • Altul: 00001

Unde se utilizează, de fapt

Probabil că toată lumea consideră că scopul nu este doar reprezentarea acestor date. Pentru a utiliza corect indexul bitmap, să luăm în considerare următorul caz.

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);

Să presupunem că acest tabel are 1.000.000 de rânduri. Și să presupunem că executăm următoarea interogare.

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

Această interogare caută rândurile în care atât coloana active, cât și coloana sex au valoarea TRUE. Atunci, o metodă foarte rapidă de a găsi rândurile care îndeplinesc condiția ca ambele coloane să fie TRUE ar fi utilizarea operației bit and.

  • Indexul bitmap pentru coloana active este deja indexat ca 1100110011... (un vector de 1.000.000 de biți),
  • iar indexul bitmap pentru coloana sex este deja indexat ca 1010101010... (un vector de 1.000.000 de biți).

Atunci, prin efectuarea operației bit and asupra celor doi indecși bitmap, se pot găsi rapid rândurile în care ambele coloane au valoarea TRUE. Deoarece este o simplă operație pe biți, rezultatul poate fi obținut mult mai rapid decât prin alte scanări ale indexului.

Compromisuri

Indexul bitmap poate fi foarte eficient, dar are câteva compromisuri. Există multe alte dezavantaje, însă deocamdată vom aborda doar unul.

Și anume, indexul bitmap este mai potrivit pentru cardinalitate scăzută (adică atunci când numărul de valori posibile ale coloanei este mic). Utilizarea unui index bitmap pe o coloană cu cardinalitate ridicată poate face bitmap-urile foarte mari.

Dacă se utilizează un index bitmap pe o coloană cu cardinalitate ridicată, trebuie generat câte un bitmap separat pentru fiecare valoare unică, ceea ce poate necesita mult spațiu de stocare. De exemplu, dacă o coloană are 1.000.000 de valori unice, trebuie generate 1.000.000 de bitmap-uri, ceea ce poate fi foarte ineficient.

Ce facem noi

Pentru a înlocui bitmap-urile care rezultă din cardinalitatea ridicată, se poate utiliza o structură numită Roaring Bitmap. Roaring Bitmap are multiple caracteristici, dar filosofia și caracteristica sa principală de bază este selectarea dinamică a celei mai potrivite metode de stocare în funcție de densitatea datelor, pentru a maximiza atât rata de compresie, cât și viteza operațiilor.

Concepte de bază ale Roaring Bitmap

Indexare în două niveluri

Pentru a stoca un număr întreg, Roaring Bitmap parcurge mai întâi următorii doi pași. Deși se numește indexare în două niveluri, se poate considera pur și simplu un vector bidimensional.

  • Extragerea celor 16 biți superiori: Se extrag cei 16 biți superiori ai numărului întreg și se folosesc ca index. Este indexul vectorului exterior dintr-un vector bidimensional cu lungimea totală de 65536. Acest vector stochează adresele containerelor descrise mai jos.
  • Extragerea celor 16 biți inferiori: Se extrag cei 16 biți inferiori ai numărului întreg și se folosesc ca poziție în interiorul containerului.

Containere

Acest container corespunde vectorului interior din vectorul bidimensional descris prin analogia de mai sus. Spre deosebire de vectorul de pe cei 16 biți superiori, structura internă a acestui container se modifică în funcție de cantitatea de date pe care o conține. Roaring Bitmap acceptă următoarele 3 tipuri de containere.

  • Array Container: Acest container este utilizat atunci când sunt stocate puține date. Mai exact, este utilizat pentru stocarea a cel mult 4096 de elemente. Acest container este implementat ca un simplu vector de numere întregi sortat. Elementele pot fi găsite prin căutare binară.
  • Bitmap Container: Acest container este utilizat atunci când sunt stocate multe date. Mai exact, este utilizat pentru stocarea a peste 4096 de elemente. Acest container este implementat ca un bitmap de 65536 de biți (8192 de octeți). Fiecare bit indică dacă numărul întreg de la poziția respectivă există sau nu.
  • Run Container: Acest container este utilizat pentru stocarea intervalelor continue de numere întregi. De exemplu, este eficient pentru stocarea unor numere întregi consecutive precum 1, 2, 3, 4, 5. Acest container este implementat ca o listă de perechi (valoare de start, lungime). Dacă toate valorile sunt prezente? Înseamnă că sunt prezente de la început până la sfârșit, deci este suficient să se stocheze o singură pereche (0, 65536).

Această abordare permite ca Roaring Bitmap să utilizeze memoria foarte eficient și să ofere performanțe optime pentru diferite densități ale datelor.

Funcționalitățile Roaring Bitmap

Funcționalități de bază

Roaring Bitmap oferă următoarele funcționalități de bază.

  • Inserare: Adaugă un nou număr întreg în bitmap. În acest proces, se poate selecta containerul potrivit sau se poate converti containerul, dacă este necesar.
  • Ștergere: Elimină un număr întreg existent din bitmap. Și în acest proces se efectuează tratamentul adecvat în funcție de starea containerului.
  • Căutare: Verifică dacă un anumit număr întreg există în bitmap. Acest proces se realizează foarte rapid.

Operații de mulțime

Roaring Bitmap acceptă, de asemenea, următoarele operații de mulțime.

  • Reuniune (Union): Creează un nou bitmap care conține toate elementele celor două bitmap-uri.
  • Intersecție (Intersection): Creează un nou bitmap care conține doar elementele existente în ambele bitmap-uri.
  • Diferență simetrică (Symmetric Difference): Creează un nou bitmap care conține elementele care există doar în unul dintre cele două bitmap-uri.

Aceste operații sunt optimizate în funcție de tipul containerelor bitmap-ului și se efectuează foarte rapid.

În limbajul Go

În limbajul Go, pachetul github.com/RoaringBitmap/roaring permite utilizarea ușoară a Roaring Bitmap. Acest pachet oferă toate funcționalitățile Roaring Bitmap și este optimizat pentru caracteristicile limbajului Go.

Instalare

1# Instalează pachetul roaring versiunea 2
2go get github.com/RoaringBitmap/roaring/v2

Exemplu de utilizare

 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)     // Inițializare cu 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inițializare cu 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Adaugă 5
14	b2.Add(10) // Adaugă 10
15
16	b2.Remove(12) // Elimină 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Operațiile pe bitmap modifică originalul, deci se folosește o copie
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]

Alte funcționalități importante care nu apar în exemplul de cod de mai sus sunt:

  • Contains(x uint32) bool: Verifică dacă o valoare specifică există în bitmap
  • GetCardinality() uint64: Returnează numărul de elemente incluse în bitmap
  • Rank(x uint32) uint64: Returnează numărul de elemente mai mici sau egale cu o valoare specificată
  • ToBytes() ([]byte, error): Serializează bitmap-ul într-un slice de octeți
  • FromBytes(data []byte) error: Restaurează bitmap-ul dintr-un slice de octeți
  • Clone() *Bitmap: Creează o copie a bitmap-ului
  • Clear(): Inițializează (golește) bitmap-ul
  • NextValue(x uint32) int64: Returnează următorul element mai mare sau egal cu x
  • PreviousValue(x uint32) int64: Returnează elementul anterior mai mic sau egal cu x
  • Maximum() uint32: Returnează cel mai mare element din bitmap
  • Minimum() uint32: Returnează cel mai mic element din bitmap

Acestea sunt câteva dintre funcționalitățile disponibile. Pentru detalii, consultați documentația oficială.

De remarcat că pachetul roaring include, în interior, și un pachet care suportă uint64, pe lângă uint32. Oferă o interfață aproape identică, astfel încât poate fi înlocuit direct.

 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)     // Inițializare cu 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inițializare cu 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Adaugă 5
14	b2.Add(10) // Adaugă 10
15
16	b2.Remove(12) // Elimină 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Operațiile pe bitmap modifică originalul, deci se folosește o copie
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}

Încheiere

Roaring Bitmap este un instrument puternic pentru stocarea și manipularea eficientă a mulțimilor de numere întregi cu cardinalitate ridicată. Utilizând pachetul github.com/RoaringBitmap/roaring în Go, toate funcționalitățile Roaring Bitmap pot fi utilizate cu ușurință. Acest pachet maximizează utilizarea memoriei și performanța prin diverse tipuri de containere și operații optimizate. Roaring Bitmap poate fi utilizat în indexarea bazelor de date, analiza jurnalelor, calculul statisticilor și alte domenii, pentru a implementa prelucrarea eficientă a datelor.

Roaring Bitmap oferă performanțe ridicate mai ales pe seturi de date de mari dimensiuni și poate fi utilizat cu succes în multiple aplicații. Combinat cu sintaxa concisă și eficientă a limbajului Go, Roaring Bitmap oferă dezvoltatorilor un instrument puternic. Se preconizează că, odată cu dezvoltarea Roaring Bitmap, vor apărea și mai multe funcționalități și optimizări.

De ce am făcut asta? Pentru indexarea pe fiecare etichetă (tag) în baze de date de serii temporale și pentru operații rapide de reuniune.