GoSuda

Levende bitmap

By snowmerak
views ...

Hvad er Bitmap?

Her er bitmap en type indeks. Hvis du er kommet her og tænker på grafik, kan du trykke på tilbage-knappen.

Grundlæggende koncept

Bitmap er en form for indekseringsteknologi i databaser. Den repræsenterer værdier for en specifik kolonne som et bit-array eller et element eller en form af en vektor, hvor hver bit angiver, om en specifik værdi for den pågældende kolonne eksisterer. Den mest grundlæggende form tildeler derfor et bit-indeks til hver række og udtrykker eksistensen som 0 eller 1.

Lad os for eksempel antage, at der er en tabel med en kønkolonne. Lad os sige, at denne tabel har 5 rækker, og værdierne i kønkolonnen er som følger:

  1. Mand
  2. Kvinde
  3. Mand
  4. Kvinde
  5. Andet

I dette tilfælde kan et bitmap-indeks for kønkolonnen udtrykkes som følger:

  • Mand: 10100
  • Kvinde: 01010
  • Andet: 00001

Så, hvor bruges det egentlig?

Jeg er sikker på, at de fleste af jer tænker, at det ikke blot er til at repræsentere det. For at bruge bitmap-indekser korrekt, lad os overveje følgende tilfælde.

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

Antag, at denne tabel har 1.000.000 rækker. Og lad os antage, at vi udfører følgende forespørgsel.

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

Denne forespørgsel finder rækker, hvor både kolonnerne 'active' og 'sex' er TRUE. Den hurtigste måde at finde rækker, der opfylder betingelsen om, at begge kolonner er TRUE, ville være at bruge en bit AND-operation.

  • Antag, at et bitmap-indeks for 'active'-kolonnen 1100110011... (1.000.000 bit-array) er forindekseret, og
  • Antag, at et bitmap-indeks for 'sex'-kolonnen 1010101010... (1.000.000 bit-array) er forindekseret.

Derefter kan vi udføre en bit AND-operation på de to bitmap-indekser for hurtigt at finde rækker, hvor begge kolonner er TRUE. Da det er en simpel bit-operation, vil resultaterne opnås meget hurtigere end ved andre indeks-scanninger.

Trade-offs

Bitmap-indekser kan være meget effektive, men der er nogle trade-offs. Der er mange andre ulemper, men for nu vil vi kun nævne én.

Nemlig, bitmap-indekser er mere velegnede til lav kardinalitet (dvs. når antallet af mulige værdier i en kolonne er lille). Brug af bitmap-indekser på kolonner med høj kardinalitet kan føre til meget store bitmaps.

Hvis bitmap-indekser bruges på kolonner med høj kardinalitet, kan der være behov for meget lagerplads, da et separat bitmap skal genereres for hver unik værdi. For eksempel, hvis en kolonne har 1.000.000 unikke værdier, skal der genereres 1.000.000 bitmaps, hvilket kan være meget ineffektivt.

Så vi

Kan bruge Roaring Bitmap som erstatning for bitmaps, der stammer fra høj kardinalitet. Roaring Bitmap har forskellige egenskaber, men den største underliggende filosofi og egenskab er at dynamisk vælge den mest passende lagringsmetode baseret på datatætheden for at maksimere både komprimeringsforhold og beregningshastighed.

Grundlæggende koncept for Roaring Bitmap

To-trins indeksering

For at gemme et enkelt heltal gennemgår Roaring Bitmap først følgende to trin. Selvom det kaldes to-trins indeksering, kan du blot tænke på det som et todimensionelt array.

  • Uddrag de øverste 16 bit: De øverste 16 bit af heltallet udtrækkes og bruges som et indeks. Dette bliver indekset for det ydre array i et todimensionelt array med en længde på 65536. Dette array gemmer adresserne til de containere, der vil blive beskrevet senere.
  • Uddrag de nederste 16 bit: De nederste 16 bit af heltallet udtrækkes og bruges som positionen inden for containeren.

Container

Denne container svarer til det indre array i det todimensionale array, som netop blev brugt som analogi. Men i modsætning til de øverste 16 bit varierer den interne struktur af denne container afhængigt af mængden af interne data. Roaring Bitmap understøtter følgende 3 containertyper.

  • Array Container: Denne container bruges, når der er få data gemt internt. Specifikt bruges den til at gemme 4096 eller færre elementer. Denne container er simpelthen implementeret som et sorteret array af heltal. Elementer kan findes ved binær søgning.
  • Bitmap Container: Denne container bruges, når der er mange data gemt internt. Specifikt bruges den til at gemme mere end 4096 elementer. Denne container er implementeret som et bitmap på 65536 bit (8192 bytes). Hver bit angiver, om heltallet på den pågældende position eksisterer.
  • Run Container: Denne container bruges til at gemme kontinuerlige intervaller af heltal. Den er for eksempel effektiv til at gemme kontinuerlige heltal som 1, 2, 3, 4, 5. Denne container er implementeret som en liste af (startværdi, længde)-par. Hvis alle er til stede? Så betyder det, at alt fra start til slut er til stede, så kun (0, 65536) gemmes.

Denne tilgang gør Roaring Bitmap i stand til at bruge hukommelse meget effektivt og give optimal ydeevne for forskellige datatætheder.

Funktioner i Roaring Bitmap

Grundlæggende funktioner

Roaring Bitmap giver følgende grundlæggende funktioner.

  • Indsæt: Tilføjer et nyt heltal til bitmap'en. Under denne proces kan en passende container vælges, eller containeren kan konverteres efter behov.
  • Slet: Fjerner et eksisterende heltal fra bitmap'en. Under denne proces udføres passende behandling i henhold til containerens tilstand.
  • Søg: Kontrollerer, om et specifikt heltal eksisterer i bitmap'en. Denne proces udføres meget hurtigt.

Sætoperationer

Roaring Bitmap understøtter også følgende sætoperationer.

  • Union (forening): Opretter en ny bitmap, der indeholder alle elementer fra to bitmaps.
  • Intersection (fællesmængde): Opretter en ny bitmap, der kun indeholder elementer, der findes i begge bitmaps.
  • Symmetric Difference (symmetrisk forskel): Opretter en ny bitmap, der kun indeholder elementer, der findes i den ene, men ikke den anden af de to bitmaps.

Disse operationer er optimeret i henhold til bitmapens containertype og udføres meget hurtigt.

I Go-sproget

I Go-sproget kan du nemt bruge Roaring Bitmap ved hjælp af github.com/RoaringBitmap/roaring-pakken. Denne pakke giver alle funktioner i Roaring Bitmap og er optimeret til Go-sprogets karakteristika.

Installation

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

Eksempel på brug

 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)     // Initialiseret med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiseret med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tilføj 5
14	b2.Add(10) // Tilføj 10
15
16	b2.Remove(12) // Fjern 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Da bitmap-operationer ændrer originalen, skal du bruge en klon
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]

De vigtigste funktioner, der ikke er vist i ovenstående eksempelkode, er:

  • Contains(x uint32) bool: Kontrollerer, om en specifik værdi eksisterer i bitmap'en.
  • GetCardinality() uint64: Returnerer antallet af elementer i bitmap'en.
  • Rank(x uint32) uint64: Returnerer antallet af elementer, der er mindre end eller lig med en specifik værdi.
  • ToBytes() ([]byte, error): Serialiserer bitmap'en til en byte-slice.
  • FromBytes(data []byte) error: Gendanner bitmap'en fra en byte-slice.
  • Clone() *Bitmap: Opretter en klon af bitmap'en.
  • Clear(): Initialiserer bitmap'en.
  • NextValue(x uint32) int64: Returnerer det næste element, der er større end eller lig med x.
  • PreviousValue(x uint32) int64: Returnerer det næste element, der er mindre end eller lig med x.
  • Maximum() uint32: Returnerer det største element i bitmap'en.
  • Minimum() uint32: Returnerer det mindste element i bitmap'en.

For flere detaljer henvises til den officielle dokumentation.

Bemærk, at roaring-pakken indeholder en pakke, der understøtter uint64 ud over uint32. Den giver næsten den samme grænseflade, så den kan udskiftes direkte.

 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)     // Initialiseret med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiseret med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tilføj 5
14	b2.Add(10) // Tilføj 10
15
16	b2.Remove(12) // Fjern 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Da bitmap-operationer ændrer originalen, skal du bruge en klon
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}

Afslutning

Roaring Bitmap er et kraftfuldt værktøj, der effektivt kan lagre og manipulere sæt af heltal med høj kardinalitet. Ved at bruge github.com/RoaringBitmap/roaring-pakken i Go-sproget kan man nemt udnytte alle funktioner i Roaring Bitmap. Denne pakke maksimerer hukommelsesforbrug og ydeevne gennem forskellige containertyper og optimerede operationer. Roaring Bitmap kan bruges i forskellige områder som databaseindeksering, loganalyse og statistiske beregninger for at implementere effektiv databehandling.

Roaring Bitmap udviser især høj ydeevne i store datasæt og kan bruges nyttigt i forskellige applikationer. Kombineret med Go-sprogets koncise og effektive syntaks giver Roaring Bitmap udviklere et kraftfuldt værktøj. Det forventes, at der vil ske yderligere udvikling og optimering af Roaring Bitmap i fremtiden, med flere funktioner.

Hvorfor gjorde jeg det? For indeksering af tags og hurtige foreningsoperationer i tidsbaserede databaser.