GoSuda

Bitmapuri vibrante

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 apăsa butonul de înapoi.

Conceptul fundamental

Un bitmap este o formă de tehnologie de indexare a bazelor de date. Valoarea unei anumite coloane este reprezentată ca un ș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 pentru coloana respectivă. Astfel, forma cea mai fundamentală este de a atribui un index de bit fiecărui rând și de a exprima prezența sau absența ca 0 și 1.

De exemplu, să presupunem că există un tabel cu o coloană pentru sex. Să presupunem că acest tabel are 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 poate fi reprezentat astfel:

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

Așadar, unde se utilizează cu adevărat?

Prin urmare, toată lumea va crede că nu este doar pentru a reprezenta asta. Pentru a utiliza corect un index 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ă se execută următoarea interogare.

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

Această interogare caută rânduri în care ambele coloane active și sex sunt TRUE. Atunci, cea mai rapidă modalitate 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ă indexul bitmap pentru coloana active este pre-indexat ca 1100110011... (un șir de biți de 1.000.000 de biți), și
  • Să presupunem că indexul bitmap pentru coloana sex este pre-indexat ca 1010101010... (un șir de biți de 1.000.000 de biți).

Atunci, prin efectuarea operației bitwise AND pe cei doi indici bitmap, rândurile în care ambele coloane sunt TRUE pot fi găsite rapid. Deoarece este o operație bitwise simplă, rezultatele pot fi obținute mult mai rapid decât cu alte scanări de index.

Compromisuri

Indicii bitmap pot fi foarte eficienți, dar există câteva compromisuri. Deși există multe alte dezavantaje, ne vom concentra acum doar pe unul.

Indexul bitmap este mai potrivit pentru cardinalitate scăzută (adică, atunci când numărul de valori posibile într-o coloană este mic). Utilizarea unui index bitmap pe o coloană cu cardinalitate ridicată poate duce la un bitmap foarte mare.

Dacă se utilizează un index bitmap pe o coloană cu cardinalitate ridicată, este necesar să se creeze un bitmap separat pentru fiecare valoare unică, ceea ce poate necesita un spațiu de stocare considerabil. De exemplu, dacă o coloană are 1.000.000 de valori unice, ar trebui create 1.000.000 de bitmap-uri, ceea ce poate fi extrem de ineficient.

Așadar, noi

Putem utiliza un Roaring Bitmap pentru a înlocui bitmap-urile care provin din cardinalitate ridicată. Roaring Bitmap are mai multe caracteristici, dar cea mai mare filozofie și caracteristică fundamentală 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 o matrice bidimensională.

  • Extragerea 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 matricei exterioare dintr-o matrice bidimensională cu o lungime totală de 65536. Această matrice stochează adresa containerului care va fi descris mai jos.
  • Extragerea 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 matricei interioare din analogia anterioară cu matricea bidimensională. Cu toate acestea, 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.

  • Array Container: Acest container este utilizat atunci când există puține date stocate intern. Mai exact, este utilizat pentru stocarea a până la 4096 de elemente. Acest container este implementat pur și simplu ca o matrice de numere întregi sortate. Elementele pot fi găsite prin căutare binară.
  • Bitmap Container: Acest container este utilizat atunci când există multe date stocate intern. 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ă prezența sau absența numărului întreg la poziția respectivă.
  • Run Container: Acest container este utilizat pentru stocarea intervalelor de numere întregi consecutive. De exemplu, este eficient pentru stocarea numerelor întregi consecutive, cum ar fi 1, 2, 3, 4, 5. Acest container este implementat ca o listă de perechi (valoare de început, lungime). Dacă sunt toate prezente? Înseamnă că sunt toate de la început până la sfârșit, deci trebuie stocat doar (0, 65536).

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

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 la bitmap. În timpul acestui proces, se poate selecta un container adecvat sau se poate converti un container, dacă este necesar.
  • Ștergere: Elimină un număr întreg existent din bitmap. Și în timpul acestui proces, se efectuează o manipulare 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 de set

Roaring Bitmap suportă, de asemenea, următoarele operații de set.

  • Reuniune (Union): Creează un nou bitmap care conține toate elementele din două bitmap-uri.
  • Intersecție (Intersection): Creează un nou bitmap care conține numai elementele prezente în ambele bitmap-uri.
  • Diferență simetrică (Symmetric Difference): Creează 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, puteți utiliza cu ușurință Roaring Bitmap folosind pachetul github.com/RoaringBitmap/roaring. 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	// Operațiile bitmap modifică originalul, așa că folosiț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: Reconstruirea bitmap-ului dintr-un slice de octeți
  • Clone() *Bitmap: Crearea unei clone 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
  • Maximum() uint32: Returnează cel mai mare element din bitmap
  • Minimum() uint32: Returnează cel mai mic element din bitmap

Acestea sunt funcționalități. Pentru detalii, consultați documentația oficială.

De notat că pachetul roaring include pachete care suportă uint64, pe lângă uint32. Acestea oferă aproape aceeași interfață și pot fi utilizate ca înlocuitori direcți.

 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	// Operațiile bitmap modifică originalul, așa că folosiț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 de cardinalitate ridicată. În limbajul Go, utilizând pachetul github.com/RoaringBitmap/roaring, 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 diverse domenii, cum ar fi indexarea bazelor de date, analiza log-urilor și calculele statistice, pentru a implementa o prelucrare eficientă a datelor.

Roaring Bitmap excelează în performanță, în special în seturi de date mari, și poate fi utilizat util în diverse aplicații. Combinat cu sintaxa concisă și eficientă a limbajului Go, Roaring Bitmap oferă un instrument puternic dezvoltatorilor. Se anticipează că, odată cu evoluția Roaring Bitmap, vor fi implementate mai multe funcționalități și optimizări în viitor.

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