GoSuda

Żywa mapa bitowa

By snowmerak
views ...

Czym jest Bitmap?

W tym kontekście Bitmap jest rodzajem indeksu. Jeżeli przyszedłeś tu z myślą o grafice, możesz wrócić.

Podstawowe pojęcia

Bitmap to forma techniki indeksowania w bazach danych. Wartości z określonej kolumny są reprezentowane jako element lub forma tablicy bitów lub wektora, gdzie każdy bit wskazuje, czy określona wartość tej kolumny istnieje. Zatem w najbardziej podstawowej formie, dla każdego wiersza przypisywany jest indeks bitowy, a istnienie wartości jest wyrażane jako 0 lub 1.

Na przykład, załóżmy, że mamy tabelę z kolumną płeć. Ta tabela ma 5 wierszy, a wartości w kolumnie płeć są następujące:

  1. Mężczyzna
  2. Kobieta
  3. Mężczyzna
  4. Kobieta
  5. Inne

W tym przypadku indeks Bitmap dla kolumny płeć może być reprezentowany w następujący sposób:

  • Mężczyzna: 10100
  • Kobieta: 01010
  • Inne: 00001

Więc gdzie jest to naprawdę używane?

Wszyscy zapewne pomyślą, że to nie służy jedynie do reprezentowania tego. Aby prawidłowo użyć indeksu Bitmap, rozważmy następujący przypadek.

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

Załóżmy, że ta tabela ma 1 000 000 wierszy. I załóżmy, że wykonujemy następujące zapytanie.

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

To zapytanie wyszukuje wiersze, w których kolumny active i sex są ustawione na TRUE. Najszybszym sposobem znalezienia wierszy spełniających warunek, że obie kolumny są TRUE, będzie wykorzystanie operacji bitowej AND.

  • Załóżmy, że indeks Bitmap dla kolumny active jest wstępnie indeksowany jako 1100110011... (tablica 1 000 000 bitów),
  • oraz że indeks Bitmap dla kolumny sex jest wstępnie indeksowany jako 1010101010... (tablica 1 000 000 bitów).

Wówczas, wykonując operację bitową AND na tych dwóch indeksach Bitmap, można szybko znaleźć wiersze, w których obie kolumny są TRUE. Ponieważ jest to prosta operacja bitowa, wyniki można uzyskać znacznie szybciej niż w przypadku skanowania innych indeksów.

Trade-off

Indeks Bitmap może być bardzo efektywny, ale wiąże się z pewnymi kompromisami. Istnieje wiele innych wad, ale teraz skupimy się tylko na jednej.

Mianowicie, indeks Bitmap jest bardziej odpowiedni dla niskiej kardynalności (tj. gdy liczba możliwych wartości w kolumnie jest mała). Użycie indeksu Bitmap dla kolumny o wysokiej kardynalności może spowodować, że bitmapa stanie się bardzo duża.

Użycie indeksu Bitmap dla kolumny o wysokiej kardynalności wymaga wygenerowania oddzielnej bitmapy dla każdej unikalnej wartości, co może prowadzić do dużego zapotrzebowania na przestrzeń dyskową. Na przykład, jeśli kolumna ma 1 000 000 unikalnych wartości, trzeba by wygenerować 1 000 000 bitmap, co może być bardzo nieefektywne.

Więc my

Możemy użyć Roaring Bitmap jako alternatywy dla Bitmap w przypadku wysokiej kardynalności. Roaring Bitmap ma kilka charakterystycznych cech, ale jego największa podstawowa filozofia i cecha to dynamiczne wybieranie najbardziej odpowiedniego sposobu przechowywania w zależności od gęstości danych, maksymalizując zarówno współczynnik kompresji, jak i szybkość operacji.

Podstawowe pojęcia Roaring Bitmap

Indeksowanie dwuetapowe

Aby zapisać jedną liczbę całkowitą, Roaring Bitmap najpierw przechodzi przez następujące dwa etapy. Mówiąc o dwuetapowym indeksowaniu, można to po prostu traktować jako tablicę dwuwymiarową.

  • Ekstrakcja 16 bitów wysokiego rzędu: Z liczby całkowitej ekstrahuje się 16 bitów wysokiego rzędu i używa się ich jako indeksu. Jest to indeks zewnętrznej tablicy spośród tablicy dwuwymiarowej o długości 65536. Ta tablica przechowuje adresy kontenerów, o których mowa poniżej.
  • Ekstrakcja 16 bitów niskiego rzędu: Z liczby całkowitej ekstrahuje się 16 bitów niskiego rzędu i używa się ich jako pozycji w kontenerze.

Kontener

Ten kontener odpowiada wewnętrznej tablicy w analogii do tablicy dwuwymiarowej. Jednak w przeciwieństwie do 16 bitów wysokiego rzędu, struktura wewnętrzna tego kontenera różni się w zależności od ilości danych w nim zawartych. Roaring Bitmap obsługuje następujące 3 typy kontenerów:

  • Array Container: Ten kontener jest używany, gdy wewnątrz przechowywanych jest niewiele danych. Konkretnie, jest używany do przechowywania do 4096 elementów. Ten kontener jest zaimplementowany jako prosta posortowana tablica liczb całkowitych. Elementy można znaleźć za pomocą wyszukiwania binarnego.
  • Bitmap Container: Ten kontener jest używany, gdy wewnątrz przechowywanych jest wiele danych. Konkretnie, jest używany do przechowywania ponad 4096 elementów. Ten kontener jest zaimplementowany jako 65536-bitowa (8192-bajtowa) bitmapa. Każdy bit wskazuje, czy liczba całkowita w danej pozycji istnieje.
  • Run Container: Ten kontener jest używany do przechowywania ciągłych zakresów liczb całkowitych. Jest efektywny na przykład przy przechowywaniu ciągłych liczb całkowitych, takich jak 1, 2, 3, 4, 5. Ten kontener jest zaimplementowany jako lista par (wartość początkowa, długość). Jeśli wszystkie są obecne? Oznacza to, że wszystkie są obecne od początku do końca, więc wystarczy zapisać tylko (0, 65536).

Takie podejście pozwala Roaring Bitmap na bardzo efektywne wykorzystanie pamięci i zapewnienie optymalnej wydajności dla różnych gęstości danych.

Funkcjonalność Roaring Bitmap

Podstawowe funkcje

Roaring Bitmap oferuje następujące podstawowe funkcje:

  • Wstawianie: Dodaje nową liczbę całkowitą do bitmapy. W tym procesie wybierany jest odpowiedni kontener lub, w razie potrzeby, kontener jest konwertowany.
  • Usuwanie: Usuwa istniejącą liczbę całkowitą z bitmapy. Również w tym procesie następuje odpowiednie przetwarzanie w zależności od stanu kontenera.
  • Wyszukiwanie: Sprawdza, czy określona liczba całkowita istnieje w bitmapie. Ten proces jest wykonywany bardzo szybko.

Operacje na zbiorach

Roaring Bitmap obsługuje również następujące operacje na zbiorach:

  • Suma (Union): Tworzy nową bitmapę zawierającą wszystkie elementy z obu bitmap.
  • Przecięcie (Intersection): Tworzy nową bitmapę zawierającą tylko elementy obecne w obu bitmapach.
  • Różnica symetryczna (Symmetric Difference): Tworzy nową bitmapę zawierającą elementy obecne tylko w jednej z dwóch bitmap.

Operacje te są zoptymalizowane pod kątem typu kontenera bitmapy i są wykonywane bardzo szybko.

W języku Go

W języku Go, pakiet github.com/RoaringBitmap/roaring można łatwo wykorzystać do używania Roaring Bitmap. Ten pakiet zapewnia wszystkie funkcje Roaring Bitmap i jest zoptymalizowany pod kątem specyfiki języka Go.

Instalacja

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

Przykład użycia

 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)     // Inicjalizacja z 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicjalizacja z 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Dodaj 5
14	b2.Add(10) // Dodaj 10
15
16	b2.Remove(12) // Usuń 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Operacje na bitmapach modyfikują oryginał, więc użyj kopii
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]

Główne funkcje, które nie zostały przedstawione w powyższym przykładzie kodu, to:

  • Contains(x uint32) bool: Sprawdza, czy określona wartość istnieje w bitmapie
  • GetCardinality() uint64: Zwraca liczbę elementów zawartych w bitmapie
  • Rank(x uint32) uint64: Zwraca liczbę elementów mniejszych lub równych określonej wartości
  • ToBytes() ([]byte, error): Serializuje bitmapę do slice'a bajtów
  • FromBytes(data []byte) error: Przywraca bitmapę ze slice'a bajtów
  • Clone() *Bitmap: Tworzy kopię bitmapy
  • Clear(): Inicjalizuje bitmapę
  • NextValue(x uint32) int64: Zwraca następny element większy lub równy x
  • PreviousValue(x uint32) int64: Zwraca następny element mniejszy lub
  • Maximum() uint32: Zwraca największy element w bitmapie
  • Minimum() uint32: Zwraca najmniejszy element w bitmapie

Te funkcje są dostępne. Aby uzyskać szczegółowe informacje, zapoznaj się z oficjalną dokumentacją.

Należy zauważyć, że pakiet roaring zawiera pakiet obsługujący uint64, a nie tylko uint32. Zapewnia on niemal identyczny interfejs, co pozwala na bezpośrednią zamianę.

 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)     // Inicjalizacja z 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicjalizacja z 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Dodaj 5
14	b2.Add(10) // Dodaj 10
15
16	b2.Remove(12) // Usuń 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Operacje na bitmapach modyfikują oryginał, więc użyj kopii
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}

Podsumowanie

Roaring Bitmap to potężne narzędzie umożliwiające efektywne przechowywanie i manipulowanie zbiorami liczb całkowitych o wysokiej kardynalności. W języku Go, korzystając z pakietu github.com/RoaringBitmap/roaring, można łatwo wykorzystać wszystkie funkcje Roaring Bitmap. Ten pakiet maksymalizuje wykorzystanie pamięci i wydajność poprzez różnorodne typy kontenerów i zoptymalizowane operacje. Roaring Bitmap może być używany w różnych dziedzinach, takich jak indeksowanie baz danych, analiza logów, obliczenia statystyczne, w celu realizacji efektywnego przetwarzania danych.

Roaring Bitmap szczególnie wyróżnia się wysoką wydajnością w dużych zbiorach danych i może być użyteczny w wielu aplikacjach. W połączeniu z zwięzłą i efektywną składnią języka Go, Roaring Bitmap zapewnia programistom potężne narzędzie. Oczekuje się, że wraz z rozwojem Roaring Bitmap pojawią się kolejne funkcje i optymalizacje.

Dlaczego to zrobiłem? Dla indeksowania poszczególnych tagów i szybkich operacji sumy w bazach danych szeregów czasowych.