GoSuda

Lebhaftes Bitmap

By snowmerak
views ...

Was ist eine Bitmap?

Hier ist eine Bitmap eine Art von Index. Wenn Sie mit der Vorstellung von Grafiken hierher gekommen sind, können Sie die Zurücktaste drücken.

Grundlegendes Konzept

Eine Bitmap ist eine Form der Indexierungstechnologie in Datenbanken. Sie stellt den Wert einer bestimmten Spalte als Element oder Form eines Bit-Arrays oder Vektors dar, wobei jedes Bit angibt, ob ein bestimmter Wert in dieser Spalte vorhanden ist. Die grundlegendste Form besteht daher darin, jeder row einen Bit-Index zuzuweisen und die Existenz als 0 oder 1 darzustellen.

Nehmen wir zum Beispiel an, Sie haben eine Tabelle mit einer Geschlechtsspalte. Angenommen, diese Tabelle hat 5 rows und die Werte in der Geschlechtsspalte sind wie folgt:

  1. Männlich
  2. Weiblich
  3. Männlich
  4. Weiblich
  5. Sonstiges

In diesem Fall könnte der Bitmap-Index für die Geschlechtsspalte wie folgt dargestellt werden:

  • Männlich: 10100
  • Weiblich: 01010
  • Sonstiges: 00001

Wo wird sie also wirklich eingesetzt?

Man wird wohl denken, dass dies nicht nur dazu dient, das einfach darzustellen. Um einen Bitmap-Index richtig zu nutzen, betrachten wir den folgenden 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);

Nehmen wir an, diese Tabelle hat 1.000.000 rows. Und nehmen wir an, wir führen die folgende Query aus.

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

Diese Query sucht nach rows, bei denen die Spalten active und sex beide TRUE sind. Die schnellste Methode, um rows zu finden, die die Bedingung erfüllen, dass beide Spalten TRUE sind, wäre die Verwendung einer Bit-AND-Operation.

  • Angenommen, der Bitmap-Index für die Spalte active ist als 1100110011... (1.000.000 Bit-Array) vorindiziert, und
  • der Bitmap-Index für die Spalte sex ist als 1010101010... (1.000.000 Bit-Array) vorindiziert.

Dann können wir durch Ausführen einer Bit-AND-Operation auf die beiden Bitmap-Indizes schnell rows finden, bei denen beide Spalten TRUE sind. Da es sich um eine einfache Bit-Operation handelt, kann das Ergebnis viel schneller erzielt werden als bei anderen Index-Scans.

Trade-offs

Bitmap-Indizes können sehr effizient sein, haben aber einige Trade-offs. Es gibt viele andere Nachteile, aber im Moment werden wir nur einen Punkt hervorheben.

Bitmap-Indizes eignen sich besser für niedrige Kardinalität (d.h. wenn die Anzahl der möglichen Werte in einer Spalte gering ist). Wenn Bitmap-Indizes für Spalten mit hoher Kardinalität verwendet werden, können die Bitmaps sehr groß werden.

Wenn Bitmap-Indizes für Spalten mit hoher Kardinalität verwendet werden, muss für jeden eindeutigen Wert eine separate Bitmap erstellt werden, was viel Speicherplatz erfordern kann. Wenn eine Spalte beispielsweise 1.000.000 eindeutige Werte enthält, müssten 1.000.000 Bitmaps erstellt werden, was sehr ineffizient sein kann.

Was wir also verwenden

Um Bitmaps mit hoher Kardinalität zu ersetzen, können wir Roaring Bitmap verwenden. Roaring Bitmap hat verschiedene Eigenschaften, aber die größte grundlegende Philosophie und Eigenschaft ist, die am besten geeignete Speichermethode dynamisch basierend auf der Datendichte auszuwählen, um sowohl die Komprimierungsrate als auch die Betriebsgeschwindigkeit zu maximieren.

Grundlegendes Konzept von Roaring Bitmap

2-Stufen-Indexierung

Um eine einzelne Ganzzahl zu speichern, durchläuft Roaring Bitmap zunächst die folgenden 2 Stufen. Es heißt 2-Stufen-Indexierung, aber man kann es sich einfach als 2D-Array vorstellen.

  • Extrahieren der oberen 16 Bit: Die oberen 16 Bit der Ganzzahl werden extrahiert und als Index verwendet. Dies wird zum Index des äußeren Arrays in einem 2D-Array mit einer Gesamtlänge von 65536. Dieses Array speichert die Adressen der später zu beschreibenden Container.
  • Extrahieren der unteren 16 Bit: Die unteren 16 Bit der Ganzzahl werden extrahiert und als Position innerhalb des Containers verwendet.

Container

Dieser Container entspricht dem inneren Array des zuvor genannten 2D-Arrays. Im Gegensatz zu den oberen 16 Bit variiert die interne Struktur dieses Containers jedoch je nach der Menge der internen Daten. Roaring Bitmap unterstützt die folgenden 3 Containertypen:

  • Array Container: Dieser Container wird verwendet, wenn wenige Daten intern gespeichert sind. Genauer gesagt, wird er zum Speichern von 4096 oder weniger Elementen verwendet. Dieser Container ist einfach als sortiertes Ganzzahl-Array implementiert. Elemente können durch binäre Suche gefunden werden.
  • Bitmap Container: Dieser Container wird verwendet, wenn viele Daten intern gespeichert sind. Genauer gesagt, wird er zum Speichern von mehr als 4096 Elementen verwendet. Dieser Container ist als Bitmap mit 65536 Bit (8192 Byte) implementiert. Jedes Bit gibt an, ob eine Ganzzahl an dieser Position vorhanden ist.
  • Run Container: Dieser Container wird zum Speichern von Bereichen zusammenhängender Ganzzahlen verwendet. Er ist beispielsweise effizient beim Speichern von zusammenhängenden Ganzzahlen wie 1, 2, 3, 4, 5. Dieser Container ist als Liste von (Startwert, Länge)-Paaren implementiert. Wenn alles vorhanden ist? Das bedeutet einfach, dass alles von Anfang bis Ende vorhanden ist, daher muss nur (0, 65536) gespeichert werden.

Diese Methode ermöglicht es Roaring Bitmap, den Speicher sehr effizient zu nutzen und optimale Leistung für verschiedene Datendichten zu bieten.

Funktionen von Roaring Bitmap

Grundfunktionen

Roaring Bitmap bietet die folgenden grundlegenden Funktionen:

  • Einfügen: Fügt eine neue Ganzzahl zur Bitmap hinzu. Dabei wird der passende Container ausgewählt oder bei Bedarf der Container konvertiert.
  • Löschen: Entfernt eine vorhandene Ganzzahl aus der Bitmap. Auch hier erfolgt eine entsprechende Verarbeitung je nach Zustand des Containers.
  • Suchen: Überprüft, ob eine bestimmte Ganzzahl in der Bitmap vorhanden ist. Dieser Vorgang wird sehr schnell ausgeführt.

Mengenoperationen

Roaring Bitmap unterstützt auch die folgenden Mengenoperationen:

  • Vereinigung (Union): Erstellt eine neue Bitmap, die alle Elemente beider Bitmaps enthält.
  • Schnittmenge (Intersection): Erstellt eine neue Bitmap, die nur die Elemente enthält, die in beiden Bitmaps vorhanden sind.
  • Symmetrische Differenz (Symmetric Difference): Erstellt eine neue Bitmap, die nur die Elemente enthält, die in genau einer der beiden Bitmaps vorhanden sind.

Diese Operationen sind für die Containertypen der Bitmap optimiert und werden sehr schnell ausgeführt.

In der Sprache Go

In der Sprache Go kann das Paket github.com/RoaringBitmap/roaring verwendet werden, um Roaring Bitmap einfach zu nutzen. Dieses Paket bietet alle Funktionen von Roaring Bitmap und ist an die Besonderheiten der Sprache Go angepasst.

Installation

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

Anwendungsbeispiel

 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)     // Initialisiert mit 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialisiert mit 2, 4, 6, 8, 12
12
13	b1.Add(5)  // 5 hinzufügen
14	b2.Add(10) // 10 hinzufügen
15
16	b2.Remove(12) // 12 entfernen
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Da Bitmap-Operationen das Original ändern, verwenden Sie eine Kopie
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]

Hauptfunktionen, die im obigen Beispielcode nicht vorkommen, sind:

  • Contains(x uint32) bool: Prüft, ob ein bestimmter Wert in der Bitmap vorhanden ist.
  • GetCardinality() uint64: Gibt die Anzahl der in der Bitmap enthaltenen Elemente zurück.
  • Rank(x uint32) uint64: Gibt die Anzahl der Elemente zurück, die kleiner oder gleich einem bestimmten Wert sind.
  • ToBytes() ([]byte, error): Serialisiert die Bitmap in einen Byte-Slice.
  • FromBytes(data []byte) error: Stellt die Bitmap aus einem Byte-Slice wieder her.
  • Clone() *Bitmap: Erstellt eine Kopie der Bitmap.
  • Clear(): Initialisiert die Bitmap.
  • NextValue(x uint32) int64: Gibt das nächste Element zurück, das größer oder gleich x ist.
  • PreviousValue(x uint32) int64: Gibt das vorherige Element zurück, das kleiner oder
  • Maximum() uint32: Gibt das größte Element in der Bitmap zurück.
  • Minimum() uint32: Gibt das kleinste Element in der Bitmap zurück.

Weitere Details finden Sie in der offiziellen Dokumentation.

Beachten Sie, dass das roaring-Paket intern sowohl uint32 als auch uint64 unterstützende Pakete enthält. Da sie fast die gleiche Schnittstelle bieten, können sie direkt ausgetauscht werden.

 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)     // Initialisiert mit 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialisiert mit 2, 4, 6, 8, 12
12
13	b1.Add(5)  // 5 hinzufügen
14	b2.Add(10) // 10 hinzufügen
15
16	b2.Remove(12) // 12 entfernen
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Da Bitmap-Operationen das Original ändern, verwenden Sie eine Kopie
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}

Fazit

Roaring Bitmap ist ein leistungsstarkes Werkzeug zur effizienten Speicherung und Manipulation von Ganzzahlmengen hoher Kardinalität. Mit dem Paket github.com/RoaringBitmap/roaring in der Sprache Go können alle Funktionen von Roaring Bitmap einfach genutzt werden. Dieses Paket maximiert die Speichernutzung und Leistung durch verschiedene Containertypen und optimierte Operationen. Roaring Bitmap kann in verschiedenen Bereichen wie Datenbankindexierung, Log-Analyse und statistischen Berechnungen eingesetzt werden, um eine effiziente Datenverarbeitung zu realisieren.

Roaring Bitmap zeigt insbesondere bei großen Datensätzen eine hohe Leistung und kann in einer Vielzahl von Anwendungen nützlich sein. In Kombination mit der prägnanten und effizienten Syntax der Sprache Go bietet Roaring Bitmap Entwicklern ein leistungsstarkes Werkzeug. Es wird erwartet, dass die Entwicklung von Roaring Bitmap auch in Zukunft weitere Funktionen und Optimierungen mit sich bringen wird.

Warum ich das gemacht habe? Für die Indexierung einzelner Tags und schnelle Vereinigungsoperationen in Zeitreihendatenbanken.