GoSuda

Vilkas bittikartta

By snowmerak
views ...

Mikä on Bitmap?

Tässä yhteydessä bitmap on eräs indeksointitapa. Jos tulit tänne grafiikkaa ajatellen, voit painaa takaisin-nappia.

Peruskäsite

Bitmap on eräs tietokannan indeksointitekniikan muoto. Se esittää tietyn sarakkeen arvon bittijonona tai vektorin elementtinä tai muotona siten, että jokainen bitti osoittaa, onko kyseisen sarakkeen tietty arvo olemassa. Tämän vuoksi perusmuodossaan kullekin riville allokoidaan bitti-indeksi ja olemassaolo esitetään arvoilla 0 ja 1.

Oletetaan esimerkiksi, että meillä on taulukko, jossa on sukupuolisarake. Oletetaan, että tässä taulukossa on 5 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

Joten mihin sitä todella käytetään

Kaikki varmasti ajattelevat, että se ei ole vain tuon esittämistä varten. Tarkastellaan seuraavaa tapausta, jotta voimme käyttää Bitmap-indeksiä kunnolla.

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-sarakkeiden arvot ovat TRUE. Tällöin bit AND -operaatiota voitaisiin 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 valmiiksi indeksoitu muotoon 1100110011... (1 000 000 bitin bittijono), ja
  • Oletetaan, että sex-sarakkeen Bitmap-indeksi on valmiiksi indeksoitu muotoon 1010101010... (1 000 000 bitin bittijono).

Tällöin suorittamalla bit AND -operaation näille kahdelle Bitmap-indeksille, voidaan nopeasti löytää rivit, joissa molemmat sarakkeet ovat TRUE. Koska kyseessä on yksinkertainen bitti-operaatio, tulos saadaan paljon nopeammin kuin muiden indeksien skannauksessa.

TRADE-OFF

Bitmap-indeksi voi olla erittäin tehokas, mutta siihen liittyy joitakin TRADE-OFFeja. Vaikka muita haittoja on monia, käsittelemme nyt vain yhtä.

Nimittäin Bitmap-indeksi soveltuu paremmin alhaiseen kardinaliteettiin (eli kun sarakkeessa mahdollisten arvojen määrä on pieni). Bitmap-indeksin käyttäminen korkean kardinaliteetin sarakkeessa voi johtaa erittäin suureen Bitmapiin.

Kun Bitmap-indeksiä käytetään korkean kardinaliteetin sarakkeessa, jokaiselle yksilölliselle arvolle on luotava erillinen Bitmap, mikä saattaa 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.

Joten me

Voimme käyttää Roaring Bitmapia korvaamaan korkean kardinaliteetin Bitmapit. Roaring Bitmapilla on useita ominaisuuksia, mutta sen suurin perusfilosofia ja ominaisuus on valita dynaamisesti sopivin tallennustapa datan tiheyden mukaan, maksimoiden sekä pakkaussuhteen että laskentanopeuden.

Roaring Bitmapin peruskäsite

2-vaiheinen indeksointi

Roaring Bitmap käy läpi seuraavat 2 vaihetta yhden kokonaisluvun tallentamiseksi. Vaikka sitä kutsutaan 2-vaiheiseksi indeksoinniksi, se on yksinkertaisesti kaksiulotteinen taulukko.

  • Ylemmän 16 bitin poimiminen: Kokonaisluvun ylempi 16 bittiä poimitaan ja käytetään indeksinä. Tästä tulee ulomman taulukon indeksi 65536 pitkässä kaksiulotteisessa taulukossa. Tämä taulukko tallentaa myöhemmin käsiteltävän säiliön osoitteen.
  • Alemman 16 bitin poimiminen: Kokonaisluvun alempi 16 bittiä poimitaan ja käytetään sijaintina säiliön sisällä.

Säiliö

Tämä säiliö vastaa juuri vertaamaani kaksiulotteisen taulukon sisempää taulukkoa. Kuitenkin, 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 3 säiliötyyppiä.

  • Array Container: Tätä säiliötä käytetään, kun tallennettu data on vähäistä. Tarkemmin sanottuna sitä käytetään, kun tallennettujen elementtien määrä on enintään 4096. 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 tallennettu data on runsasta. Tarkemmin sanottuna sitä käytetään, kun tallennettujen elementtien määrä ylittää 4096. Tämä säiliö on toteutettu 65536 bitin (8192 tavun) Bitmapina. Jokainen bitti osoittaa, onko kokonaisluku kyseisessä sijainnissa olemassa.
  • Run Container: Tätä säiliötä käytetään tallentamaan peräkkäisiä kokonaislukualueita. Se on tehokas tallennettaessa peräkkäisiä kokonaislukuja, kuten 1, 2, 3, 4, 5. Tämä säiliö on toteutettu listana (aloitusarvo, pituus) -pareja. Jos kaikki ovat olemassa? Se tarkoittaa, että kaikki ovat olemassa alusta loppuun, joten tallennetaan vain yksi pari (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äys: Lisää uuden kokonaisluvun Bitmapiin. Tässä prosessissa valitaan sopiva säiliö tai muutetaan säiliötä tarvittaessa.
  • Poisto: Poistaa olemassa olevan kokonaisluvun Bitmapista. Tässä prosessissa suoritetaan myös asianmukainen käsittely 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 molemmissa Bitmapeissa.
  • Symmetrinen erotus (Symmetric Difference): Luo uuden Bitmapin, joka sisältää elementit, jotka ovat vain toisessa kahdesta Bitmapista.

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

Go-kielessä

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

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ätään 5
14	b2.Add(10) // Lisätään 10
15
16	b2.Remove(12) // Poistetaan 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Koska bitmap-operaatio muuttaa alkuperäistä, käytetään 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]

Tärkeimmät toiminnot, joita yllä olevassa esimerkissä ei ole esitetty, ovat:

  • Contains(x uint32) bool: Tarkistaa, onko tietty arvo 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 (byte slice)
  • FromBytes(data []byte) error: Palauttaa Bitmapin tavuviipaleesta
  • Clone() *Bitmap: Luo kloonin Bitmapista
  • Clear(): Alustaa Bitmapin
  • NextValue(x uint32) int64: Palauttaa seuraavan elementin, joka on suurempi tai yhtä suuri kuin x
  • PreviousValue(x uint32) int64: Palauttaa edellisen elementin, joka on pienempi tai yhtä suuri kuin x
  • Maximum() uint32: Palauttaa suurimman elementin Bitmapissa
  • Minimum() uint32: Palauttaa pienimmän elementin Bitmapissa

Tällaisia toimintoja on saatavilla. Katso tarkemmat tiedot virallisesta dokumentaatiosta.

Huomautuksena, roaring-paketti sisältää paketin, joka tukee uint64:ää uint32:n lisäksi. Koska se tarjoaa lähes saman käyttöliittymän, se voidaan vaihtaa suoraan käyttöön.

 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ätään 5
14	b2.Add(10) // Lisätään 10
15
16	b2.Remove(12) // Poistetaan 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Koska bitmap-operaatio muuttaa alkuperäistä, käytetään 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}

Lopuksi

Roaring Bitmap on tehokas työkalu, jolla voidaan tallentaa ja käsitellä tehokkaasti korkean kardinaliteetin kokonaislukujoukkoja. Go-kielessä käyttämällä github.com/RoaringBitmap/roaring -pakettia, kaikkia Roaring Bitmapin ominaisuuksia 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 datankäsittelyn toteuttamiseen monilla eri aloilla, kuten tietokannan indeksoinnissa, lokianalyysissä ja tilastollisissa laskelmissa.

Roaring Bitmap tarjoaa erityisesti korkean suorituskyvyn suurissa DATASETeissä ja on hyödyllinen erilaisissa sovelluksissa. Yhdistettynä Go-kielen ytimekkääseen ja tehokkaaseen syntaksiin, Roaring Bitmap tarjoaa kehittäjille tehokkaan työkalun. On odotettavissa, että Roaring Bitmapin kehitys jatkuu ja siihen tulee lisää ominaisuuksia ja optimointeja.

Miksi minä tein tämän? Aikasarjatietokannassa kunkin tagin indeksointia ja nopeaa yhdisteoperaatiota varten.