GoSuda

Livfulla Bitmaps

By snowmerak
views ...

Vad är Bitmap?

Här är bitmap en typ av index. Om du kom hit och tänkte på grafik kan du trycka på bakåtknappen.

Grundläggande koncept

Bitmap är en form av indexeringsteknik i databaser. Den representerar värdet av en specifik kolumn som ett element eller en form av en bitarray eller vektor, där varje bit indikerar om ett specifikt värde för den kolumnen existerar. Därför är den mest grundläggande formen att tilldela ett bitindex till varje rad och representera existensen som 0 eller 1.

Anta till exempel att vi har en tabell med en kolumn för kön. Låt oss säga att denna tabell har 5 rader, och värdena för könskolumnen är följande:

  1. Man
  2. Kvinna
  3. Man
  4. Kvinna
  5. Annat

I detta fall kan ett bitmap-index för könskolumnen representeras enligt följande:

  • Man: 10100
  • Kvinna: 01010
  • Annat: 00001

Så var används det egentligen?

Alla kommer nog att tänka att det inte bara är till för att representera det där. För att korrekt använda ett bitmap-index, låt oss överväga följande fall.

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

Anta att denna tabell har 1 000 000 rader. Och låt oss säga att vi kör följande fråga.

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

Denna fråga hittar rader där både kolumnerna active och sex är TRUE. Då kan vi använda bit-AND-operationen som det snabbaste sättet att hitta rader som uppfyller villkoret att båda kolumnerna är TRUE.

  • Anta att ett bitmap-index för kolumnen active 1100110011... (en bitarray med 1 000 000 bitar) redan är indexerat, och
  • Anta att ett bitmap-index för kolumnen sex 1010101010... (en bitarray med 1 000 000 bitar) redan är indexerat.

Då kan vi utföra en bit-AND-operation på de två bitmap-indexen för att snabbt hitta rader där båda kolumnerna är TRUE. Eftersom det är en enkel bitoperation kommer resultatet att erhållas mycket snabbare än en annan indexskanning.

Avvägningar

Bitmap-index kan vara mycket effektiva, men det finns några avvägningar. Även om det finns många andra nackdelar, kommer vi att ta upp bara en just nu.

Bitmap-index är mer lämpliga för låg kardinalitet (dvs. när antalet möjliga värden i en kolumn är litet). Att använda ett bitmap-index på en kolumn med hög kardinalitet kan göra bitmapen mycket stor.

Om ett bitmap-index används på en kolumn med hög kardinalitet, måste en separat bitmap skapas för varje unikt värde, vilket kan kräva mycket lagringsutrymme. Om det till exempel finns 1 000 000 unika värden i en kolumn, måste 1 000 000 bitmaps skapas, vilket kan vara mycket ineffektivt.

Så vi

Vi kan använda Roaring Bitmap istället för bitmaps som kommer från hög kardinalitet. Roaring Bitmap har flera egenskaper, men den största bakomliggande filosofin och egenskapen är att "dynamiskt välja den mest lämpliga lagringsmetoden baserat på datatätheten för att maximera både kompressionsförhållandet och operationshastigheten".

Grundläggande koncept för Roaring Bitmap

Tvåstegsindexering

För att lagra ett heltal genomgår Roaring Bitmap först följande två steg. Detta är inte riktigt tvåstegsindexering, utan snarare en tvådimensionell array.

  • Extrahera de övre 16 bitarna: De övre 16 bitarna av heltalet extraheras och används som ett index. Detta blir indexet för den yttre arrayen av en tvådimensionell array med en längd på totalt 65536. Denna array lagrar adressen till den container som kommer att beskrivas senare.
  • Extrahera de nedre 16 bitarna: De nedre 16 bitarna av heltalet extraheras och används som positionen inom containern.

Containrar

Denna container motsvarar den inre arrayen av den tvådimensionella arrayen som just beskrevs. Men till skillnad från de övre 16 bitarna, varierar den interna strukturen hos denna container beroende på hur mycket intern data den innehåller. Roaring Bitmap stöder följande 3 containertyper.

  • Array Container: Denna container används när det finns lite data lagrad internt. Specifikt används den för att lagra upp till 4096 element. Denna container implementeras helt enkelt som en sorterad array av heltal. Element kan hittas genom binär sökning.
  • Bitmap Container: Denna container används när det finns mycket data lagrad internt. Specifikt används den för att lagra fler än 4096 element. Denna container implementeras som en 65536-bitars (8192 byte) bitmap. Varje bit indikerar om heltalet på den positionen existerar.
  • Run Container: Denna container används för att lagra sammanhängande intervall av heltal. Till exempel är den effektiv för att lagra sammanhängande heltal som 1, 2, 3, 4, 5. Denna container implementeras som en lista med (startvärde, längd)-par. Om allt finns? Då betyder det bara att allt finns från början till slut, så vi behöver bara lagra (0, 65536).

Denna metod gör det möjligt för Roaring Bitmap att använda minne mycket effektivt och att ge optimal prestanda för olika datatätheter.

Funktioner hos Roaring Bitmap

Grundläggande funktioner

Roaring Bitmap tillhandahåller följande grundläggande funktioner.

  • Infoga: Lägger till ett nytt heltal till bitmapen. Under denna process kan en lämplig container väljas eller en container omvandlas vid behov.
  • Radera: Tar bort ett befintligt heltal från bitmapen. Även under denna process utförs lämplig bearbetning beroende på containerns tillstånd.
  • Sök: Kontrollerar om ett specifikt heltal finns i bitmapen. Denna process utförs mycket snabbt.

Mängdoperationer

Roaring Bitmap stöder också följande mängdoperationer.

  • Union (förening): Skapar en ny bitmap som innehåller alla element från två bitmaps.
  • Intersection (snitt): Skapar en ny bitmap som endast innehåller element som finns i båda bitmaps.
  • Symmetric Difference (symmetrisk skillnad): Skapar en ny bitmap som innehåller element som endast finns i en av de två bitmaps.

Dessa operationer optimeras beroende på bitmapens containertyp och utförs mycket snabbt.

I Go-språket

I Go-språket kan du enkelt använda Roaring Bitmap med paketet github.com/RoaringBitmap/roaring. Detta paket tillhandahåller alla funktioner i Roaring Bitmap och är optimerat för Go-språkets egenskaper.

Installation

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

Användningsexempel

 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)     // Initialiseras med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiseras med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lägg till 5
14	b2.Add(10) // Lägg till 10
15
16	b2.Remove(12) // Ta bort 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Eftersom bitmap-operationer ändrar originalet, använd 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]

Viktiga funktioner som inte visas i ovanstående exempelkod är:

  • Contains(x uint32) bool: Kontrollerar om ett specifikt värde finns i bitmapen
  • GetCardinality() uint64: Returnerar antalet element i bitmapen
  • Rank(x uint32) uint64: Returnerar antalet element mindre än eller lika med ett specifikt värde
  • ToBytes() ([]byte, error): Serialiserar bitmapen till en byte-slice
  • FromBytes(data []byte) error: Återställer bitmapen från en byte-slice
  • Clone() *Bitmap: Skapar en klon av bitmapen
  • Clear(): Initierar bitmapen
  • NextValue(x uint32) int64: Returnerar nästa element som är större än eller lika med x
  • PreviousValue(x uint32) int64: Returnerar nästa element som är mindre än x
  • Maximum() uint32: Returnerar det största elementet i bitmapen
  • Minimum() uint32: Returnerar det minsta elementet i bitmapen

Dessa funktioner finns tillgängliga. För mer information, se den officiella dokumentationen.

Observera att roaring-paketet innehåller ett paket som stöder uint64, förutom uint32. Eftersom de tillhandahåller nästan samma gränssnitt kan de bytas ut direkt.

 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)     // Initialiseras med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiseras med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lägg till 5
14	b2.Add(10) // Lägg till 10
15
16	b2.Remove(12) // Ta bort 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Eftersom bitmap-operationer ändrar originalet, använd 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}

Avslutningsvis

Roaring Bitmap är ett kraftfullt verktyg för att effektivt lagra och manipulera uppsättningar av heltal med hög kardinalitet. Med paketet github.com/RoaringBitmap/roaring i Go-språket kan du enkelt använda alla funktioner i Roaring Bitmap. Detta paket maximerar minnesanvändning och prestanda genom olika containertyper och optimerade operationer. Genom att använda Roaring Bitmap kan effektiv databehandling implementeras inom olika områden som databasindexering, logganalys och statistiska beräkningar.

Roaring Bitmap presterar särskilt bra med stora datamängder och kan användas effektivt i en mängd olika applikationer. I kombination med Go-språkets koncisa och effektiva syntax ger Roaring Bitmap utvecklare ett kraftfullt verktyg. Vi förväntar oss att Roaring Bitmap kommer att utvecklas ytterligare med fler funktioner och optimeringar i framtiden.

Varför gjorde jag detta? För indexering av varje tagg och snabba union-operationer i en tidsseriedatabas.