GoSuda

Eloisat bittikartat

By snowmerak
views ...

Mikä on Bitmap?

Tässä yhteydessä bitmap on eräänlainen indeksi. Jos tulit tänne grafiikkaa mielessäsi, voit palata takaisin.

Peruskäsite

Bitmap on eräs tietokannan indeksointitekniikan muoto. Se esittää tietyn sarakkeen arvon bittijonona tai vektorin elementtinä, jossa kukin bitti ilmaisee, onko kyseisen sarakkeen tietty arvo olemassa vai ei. Siksi sen perustavanlaatuisin muoto on allokoida bittindeksi jokaiselle riville ja ilmaista olemassaolo 0:lla tai 1:llä.

Oletetaan esimerkiksi, että meillä on taulukko, jossa on sukupuolisarake. Oletetaan, että tässä taulukossa on viisi riviä ja sukupuolisarakkeen arvot ovat seuraavat:

  1. Mies
  2. Nainen
  3. Mies
  4. Nainen
  5. Muu

Tässä tapauksessa sukupuolisarakkeen bitmap-indeksi voidaan esittää seuraavasti:

  • Mies: 10100
  • Nainen: 01010
  • Muu: 00001

Mihin sitä oikeastaan käytetään?

Luultavasti kaikki ajattelevat, ettei sitä ole tarkoitettu vain tämän esittämiseen. Tarkastellaan seuraavaa tapausta, jotta voimme käyttää bitmap-indeksiä oikein.

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

Oletetaan, että tässä taulukossa on 1 000 000 riviä. Ja oletetaan, että suoritamme seuraavan kyselyn.

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

Tämä kysely etsii rivit, joissa sekä active- että sex-sarakkeet ovat TRUE. Tällöin bit-AND-operaatiota voidaan hyödyntää nopeimpana tapana löytää rivit, jotka täyttävät ehdon, että molemmat sarakkeet ovat TRUE.

  • Oletetaan, että active-sarakkeen bitmap-indeksi on 1100110011... (1 000 000 bitin bittijono) on indeksoitu etukäteen, ja
  • sex-sarakkeen bitmap-indeksi on 1010101010... (1 000 000 bitin bittijono) on indeksoitu etukäteen.

Tällöin voidaan suorittaa bit-AND-operaatio kahdelle bitmap-indeksille, jotta löydetään nopeasti rivit, joissa molemmat sarakkeet ovat TRUE. Koska kyseessä on yksinkertainen bittioperaatio, tulokset saadaan paljon nopeammin kuin muiden indeksiskannausten avulla.

Kompromissit

Bitmap-indeksit voivat olla erittäin tehokkaita, mutta niillä on joitakin kompromisseja. Vaikka niillä on monia muita haittoja, käsittelemme nyt vain yhtä.

Nimittäin, bitmap-indeksit soveltuvat paremmin matalan kardinaliteetin sarakkeisiin (eli sarakkeisiin, joissa mahdollisten arvojen määrä on pieni). Korkean kardinaliteetin sarakkeissa bitmap-indeksin käyttö voi johtaa erittäin suureen bitmapiin.

Jos bitmap-indeksiä käytetään korkean kardinaliteetin sarakkeessa, jokaiselle yksilölliselle arvolle on luotava erillinen bitmap, mikä voi vaatia paljon tallennustilaa. Esimerkiksi, jos sarakkeessa on 1 000 000 yksilöllistä arvoa, on luotava 1 000 000 bitmapia, mikä voi olla erittäin tehotonta.

Siksi me

Korkean kardinaliteetin tuottamien bitmapien korvaamiseksi voidaan käyttää Roaring Bitmapia. Roaring Bitmapilla on useita ominaisuuksia, mutta sen suurin perustavanlaatuinen filosofia ja ominaisuus on valita dynaamisesti sopivin tallennustapa tietojen tiheyden mukaan maksimoidakseen sekä pakkaussuhteen että laskentanopeuden.

Roaring Bitmapin peruskäsite

Kaksivaiheinen indeksointi

Roaring Bitmap käy läpi seuraavat kaksi vaihetta yhden kokonaisluvun tallentamiseksi. Kyseessä on kaksivaiheinen indeksointi, mutta voit ajatella sitä yksinkertaisesti kaksiulotteisena taulukkona.

  • Ylemmän 16 bitin poimiminen: Kokonaisluvun ylemmät 16 bittiä poimitaan ja niitä käytetään indeksinä. Tästä tulee ulomman taulukon indeksi 65536 pitkässä kaksiulotteisessa taulukossa. Tämä taulukko tallentaa myöhemmin käsiteltävien säiliöiden osoitteet.
  • Alemman 16 bitin poimiminen: Kokonaisluvun alemmat 16 bittiä poimitaan ja niitä käytetään sijaintina säiliössä.

Säiliö

Tämä säiliö vastaa juuri verrattua kaksiulotteisen taulukon sisempää taulukkoa. Toisin kuin ylemmän 16 bitin tapauksessa, tämän säiliön sisäinen rakenne vaihtelee sen mukaan, kuinka paljon sisäistä dataa siinä on. Roaring Bitmap tukee seuraavia kolmea säiliötyyppiä:

  • Array Container: Tätä säiliötä käytetään, kun tallennettavaa dataa on vähän. Tarkemmin sanottuna sitä käytetään, kun tallennetaan enintään 4096 elementtiä. Tämä säiliö on toteutettu yksinkertaisesti järjestettynä kokonaislukutaulukkona. Elementit voidaan löytää binäärihaulla.
  • Bitmap Container: Tätä säiliötä käytetään, kun tallennettavaa dataa on paljon. Tarkemmin sanottuna sitä käytetään, kun tallennetaan yli 4096 elementtiä. Tämä säiliö on toteutettu 65536 bitin (8192 tavun) bitmapina. Jokainen bitti ilmaisee, onko kokonaisluku kyseisessä sijainnissa olemassa vai ei.
  • Run Container: Tätä säiliötä käytetään, kun tallennetaan peräkkäisiä kokonaislukualueita. Se on tehokas esimerkiksi tallennettaessa peräkkäisiä kokonaislukuja, kuten 1, 2, 3, 4, 5. Tämä säiliö on toteutettu (aloitusarvo, pituus) -pariluettelona. Jos kaikki ovat olemassa? Se tarkoittaa, että kaikki ovat olemassa alusta loppuun, joten tallennetaan vain yksi (0, 65536).

Tämä lähestymistapa mahdollistaa Roaring Bitmapin erittäin tehokkaan muistin käytön ja optimaalisen suorituskyvyn tarjoamisen erilaisille datatiheyksille.

Roaring Bitmapin toiminnot

Perustoiminnot

Roaring Bitmap tarjoaa seuraavat perustoiminnot:

  • Lisääminen: Lisää uuden kokonaisluvun bitmapiin. Tässä prosessissa valitaan sopiva säiliö tai muunnetaan säiliötä tarvittaessa.
  • Poistaminen: Poistaa olemassa olevan kokonaisluvun bitmapista. Tässä prosessissa myös käsitellään asianmukaisesti säiliön tilan mukaan.
  • Haku: Tarkistaa, onko tietty kokonaisluku olemassa bitmapissa. Tämä prosessi suoritetaan erittäin nopeasti.

Joukko-operaatiot

Roaring Bitmap tukee myös seuraavia joukko-operaatioita:

  • Yhdiste (Union): Luo uuden bitmapin, joka sisältää kaikki kahden bitmapin elementit.
  • Leikkaus (Intersection): Luo uuden bitmapin, joka sisältää vain ne elementit, jotka ovat olemassa molemmissa bitmapeissa.
  • Symmetrinen ero (Symmetric Difference): Luo uuden bitmapin, joka sisältää elementit, jotka ovat olemassa vain toisessa kahdesta bitmapista.

Nämä operaatiot on optimoitu bitmapin säiliötyypin mukaan ja ne suoritetaan erittäin nopeasti.

Go-kielessä

Go-kielessä Roaring Bitmapia voidaan helposti hyödyntää käyttämällä github.com/RoaringBitmap/roaring -pakettia. Tämä paketti tarjoaa kaikki Roaring Bitmapin toiminnot ja on optimoitu Go-kielen ominaisuuksien mukaisesti.

Asennus

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

Käyttöesimerkki

 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)     // Alustetaan arvoilla 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Alustetaan arvoilla 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lisää 5
14	b2.Add(10) // Lisää 10
15
16	b2.Remove(12) // Poista 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Koska bitmap-operaatiot muuttavat alkuperäistä, käytä kloonia
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]

Yllä olevassa esimerkkikoodissa esiintymättömiä tärkeimpiä toimintoja ovat:

  • Contains(x uint32) bool: Tarkistaa, onko tietty arvo olemassa bitmapissa
  • GetCardinality() uint64: Palauttaa bitmapissa olevien elementtien määrän
  • Rank(x uint32) uint64: Palauttaa tiettyä arvoa pienempien tai yhtä suurten elementtien määrän
  • ToBytes() ([]byte, error): Serialisoi bitmapin tavuviipaleeksi
  • FromBytes(data []byte) error: Palauttaa bitmapin tavuviipaleesta
  • Clone() *Bitmap: Luo kloonin bitmapista
  • Clear(): Alustaa bitmapin
  • NextValue(x uint32) int64: Palauttaa seuraavan arvoa x suuremman tai yhtä suuren elementin
  • PreviousValue(x uint32) int64: Palauttaa arvoa x pienemmän tai
  • Maximum() uint32: Palauttaa bitmapin suurimman elementin
  • Minimum() uint32: Palauttaa bitmapin pienimmän elementin

Nämä toiminnot ovat käytettävissä. Lisätietoja löytyy virallisesta dokumentaatiosta.

Huomaa, että roaring-paketti sisältää paketin, joka tukee uint64:ää uint32:n lisäksi. Ne tarjoavat lähes identtisen rajapinnan, joten niitä voidaan käyttää vaihdettavasti.

 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)     // Alustetaan arvoilla 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Alustetaan arvoilla 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lisää 5
14	b2.Add(10) // Lisää 10
15
16	b2.Remove(12) // Poista 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Koska bitmap-operaatiot muuttavat alkuperäistä, käytä kloonia
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}

Yhteenveto

Roaring Bitmap on tehokas työkalu, jolla voidaan tallentaa ja käsitellä tehokkaasti korkean kardinaliteetin kokonaislukujoukkoja. Go-kielessä github.com/RoaringBitmap/roaring -paketin avulla Roaring Bitmapin kaikki toiminnot voidaan hyödyntää helposti. Tämä paketti maksimoi muistin käytön ja suorituskyvyn erilaisten säiliötyyppien ja optimoitujen operaatioiden avulla. Roaring Bitmapia voidaan käyttää tehokkaan tiedonkäsittelyn toteuttamiseen monilla aloilla, kuten tietokantojen indeksoinnissa, lokianalyysissä ja tilastollisissa laskelmissa.

Roaring Bitmap suoriutuu erityisen hyvin suurissa tietokokonaisuuksissa ja voi olla hyödyllinen monissa sovelluksissa. Yhdistettynä Go-kielen ytimekkääseen ja tehokkaaseen syntaksiin, Roaring Bitmap tarjoaa kehittäjille tehokkaan työkalun. Roaring Bitmapin kehityksen myötä odotetaan lisää toimintoja ja optimointeja tulevaisuudessa.

Miksi tein tämän? Aikasarjatietokannoissa indeksoin jokaisen tagin ja nopean yhdisteoperaation vuoksi.