GoSuda

Bitmap activ

By snowmerak
views ...

Ce este un Bitmap?

Aici, termenul „bitmap” se referă la un tip de index. Dacă ați venit cu gândul la grafică, vă rugăm să reveniți.

Conceptul Fundamental

Bitmap-ul reprezintă o formă de tehnică de indexare în baze de date. Acesta exprimă valorile unei coloane specifice sub forma unui șir de biți sau ca un element sau o formă a unui vector, unde fiecare bit indică prezența sau absența unei anumite valori în coloana respectivă. Prin urmare, forma cea mai fundamentală constă în alocarea unui index de bit pentru fiecare rând și reprezentarea prezenței sub forma 0 și 1.

De exemplu, să presupunem că avem un tabel cu o coloană pentru sex. Acest tabel conține 5 rânduri, iar valorile coloanei pentru sex sunt următoarele:

  1. Masculin
  2. Feminin
  3. Masculin
  4. Feminin
  5. Altele

În acest caz, indexul bitmap pentru coloana sex ar putea fi reprezentat astfel:

  • Masculin: 10100
  • Feminin: 01010
  • Altele: 00001

Așadar, la ce este utilizat cu adevărat?

Majoritatea oamenilor ar considera că aceasta nu este o simplă reprezentare. Pentru a utiliza corect un index bitmap, să luăm în considerare următorul scenariu.

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 conține 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 coloanele "active" cât și "sex" sunt TRUE. Atunci, cea mai rapidă metodă de a găsi rândurile care îndeplinesc condiția ca ambele coloane să fie TRUE ar fi utilizarea operației bitwise AND.

  • Să presupunem că un index bitmap pentru coloana "active" este pre-indexat ca 1100110011... (un șir de 1.000.000 de biți), și
  • Să presupunem că un index bitmap pentru coloana "sex" este pre-indexat ca 1010101010... (un șir de 1.000.000 de biți).

Atunci, prin efectuarea unei operații bitwise AND pe cei doi indici bitmap, rândurile în care ambele coloane sunt TRUE pot fi găsite rapid. Deoarece este o simplă operație bitwise, rezultatele pot fi obținute mult mai rapid decât printr-o scanare a altor indici.

Compromisuri

Deși indicii bitmap pot fi extrem de eficienți, există câteva compromisuri. Există multe alte dezavantaje, dar deocamdată vom aborda doar unul.

Indicii bitmap sunt mai potriviți pentru cardinalitate scăzută (adică, atunci când numărul de valori posibile într-o coloană este mic). Utilizarea indicilor bitmap pentru coloane cu cardinalitate ridicată poate duce la bitmap-uri foarte mari.

Dacă se utilizează un index bitmap pentru o coloană cu cardinalitate ridicată, este necesară generarea unui bitmap separat pentru fiecare valoare unică, ceea ce poate necesita o cantitate mare de spațiu de stocare. De exemplu, dacă o coloană conține 1.000.000 de valori unice, ar trebui generate 1.000.000 de bitmap-uri, ceea ce poate fi extrem de ineficient.

Așadar, noi

Putem utiliza un Roaring Bitmap ca alternativă la bitmap-urile rezultate din cardinalitatea ridicată. Roaring Bitmap are diverse caracteristici, dar filosofia și caracteristica sa fundamentală principală 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 de operare.

Conceptul Fundamental al Roaring Bitmap

Indexare în 2 Etape

Pentru a stoca un singur număr întreg, Roaring Bitmap parcurge mai întâi următoarele 2 etape. Deși se numește indexare în 2 etape, o puteți considera pur și simplu ca un tablou bidimensional.

  • Extracția celor 16 biți superiori: Cei 16 biți superiori ai numărului întreg sunt extrași și utilizați ca index. Acesta devine indexul tabloului exterior dintr-un tablou bidimensional cu o lungime totală de 65536. Acest tablou stochează adresele containerelor, despre care vom vorbi mai jos.
  • Extracția celor 16 biți inferiori: Cei 16 biți inferiori ai numărului întreg sunt extrași și utilizați ca poziție în cadrul containerului.

Container

Acest container corespunde tabloului interior din tabloul bidimensional la care am făcut aluzie anterior. Totuși, spre deosebire de cei 16 biți superiori, structura internă a acestui container variază în funcție de cantitatea de date interne. Roaring Bitmap suportă următoarele 3 tipuri de containere:

  • Container de tip Array: Acest container este utilizat atunci când există puține date stocate intern. Mai exact, este utilizat pentru a stoca până la 4096 de elemente. Acest container este implementat pur și simplu ca un tablou de numere întregi sortate. Elementele pot fi găsite prin căutare binară.
  • Container de tip Bitmap: Acest container este utilizat atunci când există multe date stocate intern. Mai exact, este utilizat pentru a stoca peste 4096 de elemente. Acest container este implementat ca un bitmap de 65536 de biți (8192 de octeți). Fiecare bit indică prezența sau absența numărului întreg la poziția respectivă.
  • Container de tip Run: Acest container este utilizat pentru a stoca intervale continue de numere întregi. De exemplu, este eficient pentru stocarea numerelor întregi consecutive precum 1, 2, 3, 4, 5. Acest container este implementat ca o listă de perechi (valoare de început, lungime). Dacă toate sunt prezente? Înseamnă pur și simplu că sunt toate de la început până la sfârșit, deci se stochează doar (0, 65536).

Această abordare permite Roaring Bitmap să utilizeze memoria foarte eficient și să ofere performanțe optime pentru o gamă variată de densități de date.

Funcționalități ale 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 selectează un container adecvat sau, dacă este necesar, containerul este convertit.
  • Ștergere: Elimină un număr întreg existent din bitmap. Și în acest proces, se efectuează o gestionare adecvată în funcție de starea containerului.
  • Căutare: Verifică dacă un anumit număr întreg există în bitmap. Acest proces este executat foarte rapid.

Operații pe Mulțimi

Roaring Bitmap suportă, de asemenea, următoarele operații pe mulțimi:

  • Reuniune (Union): Generează un nou bitmap care conține toate elementele ambelor bitmap-uri.
  • Intersecție (Intersection): Generează un nou bitmap care conține doar elementele prezente în ambele bitmap-uri.
  • Diferență Simetrică (Symmetric Difference): Generează un nou bitmap care conține elementele prezente doar într-unul dintre cele două bitmap-uri.

Aceste operații sunt optimizate în funcție de tipul containerului bitmap-ului și sunt executate foarte rapid.

În Limbajul Go

În limbajul Go, pachetul github.com/RoaringBitmap/roaring poate fi utilizat pentru a valorifica cu ușurință Roaring Bitmap. Acest pachet oferă toate funcționalitățile Roaring Bitmap și este optimizat pentru caracteristicile limbajului Go.

Instalare

1go 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țializat cu 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inițializat 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	// Deoarece operațiile bitmap modifică originalul, utilizați o clonă
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]

Funcționalități cheie care nu sunt prezentate în exemplul de cod de mai sus includ:

  • Contains(x uint32) bool: Verifică dacă o anumită valoare există în bitmap.
  • GetCardinality() uint64: Returnează numărul de elemente conținute în bitmap.
  • Rank(x uint32) uint64: Returnează numărul de elemente mai mici sau egale cu o anumită valoare.
  • ToBytes() ([]byte, error): Serializarea bitmap-ului într-un slice de octeți.
  • FromBytes(data []byte) error: Restaurarea bitmap-ului dintr-un slice de octeți.
  • Clone() *Bitmap: Crearea unei copii a bitmap-ului.
  • Clear(): Inițializarea bitmap-ului.
  • 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.

Aceste funcționalități sunt disponibile. Pentru detalii, vă rugăm să consultați documentația oficială.

De menționat că pachetul roaring include, pe lângă uint32, și un pachet care suportă uint64. Acesta oferă o interfață aproape identică, permițând o înlocuire 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țializat cu 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inițializat 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	// Deoarece operațiile bitmap modifică originalul, utilizați o clonă
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}

Concluzie

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

Roaring Bitmap excelează în special în performanța ridicată pe seturi de date de mari dimensiuni și poate fi utilizat în mod util într-o varietate de aplicații. Combinat cu sintaxa concisă și eficientă a limbajului Go, Roaring Bitmap oferă dezvoltatorilor un instrument puternic. Ne așteptăm la progrese suplimentare și optimizări ale Roaring Bitmap în viitor.

De ce am făcut asta? Pentru indexarea fiecărei etichete și operații rapide de reuniune în bazele de date de serii temporale.