--- id: e80ed40ea024585819cc03207d51db23 author: snowmerak title: Élénk bitkép description: Az adatbázis-bitmap indexek fogalmától a Roaring Bitmap működési elvén át a Go nyelvi alkalmazásig. Nagy méretű adathalmazok hatékony feldolgozásához szükséges bitmap-optimalizálást vizsgálunk. language: hu date: 2025-09-08T13:30:39.840979719Z path: /blog/posts/vibrant-bitmap-z1743872f category: database --- ## Mi is az a bitmap? > Itt a bitmap az indexek egyik fajtája. Ha grafikai értelemben érkezett ide, kérjük, lépjen vissza. ### Alapfogalmak A bitmap az adatbázisok indexelési technikájának egyik formája. Egy adott oszlop értékeit bitvektor vagy bittömb egy elemeként vagy alakjában ábrázolja, ahol minden bit azt jelzi, hogy az adott oszlopban létezik-e a megadott érték. Ennek megfelelően a legegyszerűbb forma az, hogy minden sorhoz bitindexet rendelünk, és a létezést 0 és 1 értékekkel fejezzük ki. Tegyük fel például, hogy van egy olyan tábla, amelyben szerepel a nem oszlop. Legyen a táblában 5 sor, a nem oszlop értékei pedig a következők: 1. Férfi 2. Nő 3. Férfi 4. Nő 5. Egyéb Ebben az esetben a nem oszlopra vonatkozó bitmap index például így ábrázolható: - Férfi: 10100 - Nő: 01010 - Egyéb: 00001 ### Valójában hol használjuk? Valószínűleg sokan úgy gondolják, hogy a fenti ábrázolás nem pusztán erre szolgál. Ahhoz, hogy a bitmap indexet ténylegesen hasznosan alkalmazzuk, tekintsük a következő esetet. ```SQL CREATE TABLE IF NOT EXISTS Users ( id INT PRIMARY KEY, name VARCHAR(100), active BOOLEAN, sex BOOLEAN, age INT ); ``` Tegyük fel, hogy ebben a táblában 1 000 000 sor található, és a következő lekérdezést futtatjuk. ```SQL SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE; ``` Ez a lekérdezés azokat a sorokat keresi, amelyekben mind az active, mind a sex oszlop értéke TRUE. Ilyen esetben a két feltételt a leggyorsabban úgy elégíthetjük ki, ha bit AND műveletet alkalmazunk. - Az active oszlop bitmap indexe előre elkészítve tartalmazza a `1100110011...` bittömböt (1 000 000 bit). - A sex oszlop bitmap indexe előre elkészítve tartalmazza a `1010101010...` bittömböt (1 000 000 bit). Ezután a két bitmap indexen bit AND műveletet végezve gyorsan megtalálhatjuk azokat a sorokat, amelyekben mindkét oszlop értéke TRUE. Mivel ez egyszerű bitművelet, az eredmény sokkal gyorsabban előáll, mint más indexbejárási módszerek esetén. ### Kompromisszumok A bitmap index rendkívül hatékony lehet, ugyanakkor több kompromisszummal jár. Számos hátránya van, de most csak egyet emelnék ki. Ez pedig a kardinalitás kérdése: a bitmap index az alacsony cardinality (vagyis az oszlopban előforduló lehetséges értékek kis száma) esetén a legalkalmasabb. Magas cardinality oszlopon történő használat esetén a bitmap jelentősen megnőhet. Magas cardinality oszlop esetén minden egyedi értékhez külön bitmapet kell létrehozni, ezért a tárigény jelentős lehet. Ha például egy oszlopnak 1 000 000 egyedi értéke van, akkor 1 000 000 bitmapet kell generálni, ami rendkívül nem hatékony lehet. ## Megoldásunk A magas cardinality okozta problémák kiküszöbölésére használhatjuk a Roaring Bitmap nevű szerkezetet. A Roaring Bitmap számos tulajdonsággal rendelkezik, de legfontosabb alapelve és jellemzője: `az adatok sűrűségétől függően dinamikusan választja ki a legmegfelelőbb tárolási módot, így maximalizálja mind a tömörítési arányt, mind a műveletek sebességét`. ### A Roaring Bitmap alapfogalmai #### Kétszintű indexelés A Roaring Bitmap egy egész szám tárolásához először a következő két lépésen megy keresztül. Bár kétszintű indexelésről beszélünk, lényegében elegendő egy kétdimenziós tömbként gondolni rá. - Felső 16 bit kinyerése: Az egész szám felső 16 bitjét kinyerjük, és indexként használjuk. Ez a 65536 hosszúságú kétdimenziós tömb külső tömbjének indexe. Ez a tömb a később ismertetendő konténerek címeit tárolja. - Alsó 16 bit kinyerése: Az egész szám alsó 16 bitjét kinyerjük, és ezt használjuk a konténeren belüli pozícióként. #### Konténerek A konténer a fent említett kétdimenziós tömb belső tömbjének felel meg. Ellentétben a felső 16 bites tömbbel, a konténer belső szerkezete attól függ, hogy mennyi adat található benne. A Roaring Bitmap a következő 3 konténertípust támogatja. - Array Container: Ez a konténer akkor használatos, ha a benne tárolt adatok száma kicsi. Pontosabban, 4096 vagy kevesebb elem tárolása esetén alkalmazzuk. Egyszerűen rendezett egész számok tömbjeként valósul meg, és az elemek bináris kereséssel találhatók meg. - Bitmap Container: Ez a konténer akkor használatos, ha a benne tárolt adatok száma nagy. Pontosabban, 4096-nál több elem tárolása esetén alkalmazzuk. 65536 bites (8192 bájtos) bitmapként valósul meg. Minden bit azt jelzi, hogy az adott pozícióban szereplő egész szám létezik-e. - Run Container: Ez a konténer folytonos egész számtartományok tárolására szolgál. Például az 1, 2, 3, 4, 5 típusú egymást követő számok tárolása esetén hatékony. (Kezdőérték, hossz) párokat tartalmazó listaként valósul meg. Ha minden érték jelen van, vagyis a teljes tartomány megtelt, akkor elegendő egyetlen (0, 65536) párt tárolni. Ezek a módszerek biztosítják, hogy a Roaring Bitmap rendkívül hatékonyan használja a memóriát, és különböző adatsűrűségek mellett is optimális teljesítményt nyújtson. ### A Roaring Bitmap funkciói #### Alapvető funkciók A Roaring Bitmap a következő alapvető funkciókat biztosítja: - Beszúrás: Új egész számot ad hozzá a bitmaphez. Ennek során megfelelő konténert választ, vagy szükség esetén konténert konvertál. - Törlés: Eltávolítja a meglévő egész számot a bitmapből. Ennek során is a konténerek állapotától függően történik a megfelelő kezelés. - Keresés: Ellenőrzi, hogy egy adott egész szám szerepel-e a bitmapben. Ez a művelet nagyon gyorsan végrehajtódik. #### Halmazműveletek A Roaring Bitmap emellett a következő halmazműveleteket támogatja: - Únió (Union): Új bitmapet hoz létre, amely mindkét bitmap összes elemét tartalmazza. - Metszet (Intersection): Új bitmapet hoz létre, amely csak azokat az elemeket tartalmazza, amelyek mindkét bitmapben megtalálhatók. - Szimmetrikus különbség (Symmetric Difference): Új bitmapet hoz létre, amely azokat az elemeket tartalmazza, amelyek a két bitmap közül pontosan az egyikben szerepelnek. Ezek a műveletek a bitmap konténertípusától függően optimalizálva vannak, így rendkívül gyorsan végrehajthatók. ### Go nyelv esetén Go nyelven a `github.com/RoaringBitmap/roaring` csomag segítségével egyszerűen használhatjuk a Roaring Bitmapet. A csomag a Roaring Bitmap összes funkcióját biztosítja, és a Go nyelv sajátosságaihoz igazodva optimalizált. #### Telepítés ```bash go get github.com/RoaringBitmap/roaring/v2 ``` #### Használati példa ```go package main import ( "log" "github.com/RoaringBitmap/roaring/v2" ) func main() { b1 := roaring.BitmapOf(1, 2, 3, 4) // Inicializálás az 1, 2, 3, 4 értékekkel b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializálás a 2, 4, 6, 8, 12 értékekkel b1.Add(5) // 5 hozzáadása b2.Add(10) // 10 hozzáadása b2.Remove(12) // 12 eltávolítása and := roaring.FastAnd(b1, b2) or := roaring.FastOr(b1, b2) // Mivel a bitmap műveletek módosítják az eredeti példányt, másolatot készítünk a használatukhoz xor := b1.Clone() xor.Xor(b2) log.Printf("and result: %v", and.ToArray()) log.Printf("or result: %v", or.ToArray()) log.Printf("xor result: %v", xor.ToArray()) } ``` ```shell 2025/09/08 22:16:27 and result: [2 4] 2025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10] 2025/09/08 22:16:27 xor result: [1 3 5 6 8 10] ``` A fenti példakódban nem szereplő főbb funkciók: - `Contains(x uint32) bool`: Ellenőrzi, hogy egy adott érték szerepel-e a bitmapben - `GetCardinality() uint64`: Visszaadja a bitmapben lévő elemek számát - `Rank(x uint32) uint64`: Visszaadja az x értéknél kisebb vagy egyenlő elemek számát - `ToBytes() ([]byte, error)`: Bájtszeletté szerializálja a bitmapet - `FromBytes(data []byte) error`: Visszaállítja a bitmapet bájtszeletből - `Clone() *Bitmap`: Létrehozza a bitmap másolatát - `Clear()`: Inicializálja (üríti) a bitmapet - `NextValue(x uint32) int64`: Visszaadja az x-nél nagyobb vagy vele egyenlő következő elemet - `PreviousValue(x uint32) int64`: Visszaadja az x-nél kisebb vagy vele egyenlő előző elemet - `Maximum() uint32`: Visszaadja a bitmap legnagyobb elemét - `Minimum() uint32`: Visszaadja a bitmap legkisebb elemét Ezek a funkciók állnak rendelkezésre. Részletekért tekintse meg a [hivatalos dokumentációt](https://pkg.go.dev/github.com/RoaringBitmap/roaring/v2). Megjegyzendő, hogy a roaring csomag a uint32 mellett uint64 típust támogató csomagot is tartalmaz. Ez szinte azonos felülettel rendelkezik, ezért közvetlenül lecserélhető a használata. ```go package main import ( "log" "github.com/RoaringBitmap/roaring/v2/roaring64" ) func main() { b1 := roaring64.BitmapOf(1, 2, 3, 4) // Inicializálás az 1, 2, 3, 4 értékekkel b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializálás a 2, 4, 6, 8, 12 értékekkel b1.Add(5) // 5 hozzáadása b2.Add(10) // 10 hozzáadása b2.Remove(12) // 12 eltávolítása and := roaring64.FastAnd(b1, b2) or := roaring64.FastOr(b1, b2) // Mivel a bitmap műveletek módosítják az eredeti példányt, másolatot készítünk a használatukhoz xor := b1.Clone() xor.Xor(b2) log.Printf("and result: %v", and.ToArray()) log.Printf("or result: %v", or.ToArray()) log.Printf("xor result: %v", xor.ToArray()) } ``` ### Összegzés A Roaring Bitmap nagy kardinalitású egész számhalmazok hatékony tárolására és kezelésére alkalmas erőteljes eszköz. Go nyelven a `github.com/RoaringBitmap/roaring` csomag használatával a Roaring Bitmap összes funkciója egyszerűen elérhetővé válik. A csomag különböző konténertípusai és optimalizált műveletei révén maximalizálja a memóriahasználat hatékonyságát és a teljesítményt. Adatbázis-indexelés, naplóelemzés, statisztikai számítások és más területeken is alkalmazható a Roaring Bitmap a hatékony adatfeldolgozás megvalósításához. A Roaring Bitmap különösen nagy adathalmazok esetén nyújt magas teljesítményt, és számos alkalmazásban hasznos lehet. A Go nyelv tömör és hatékony szintaxisával párosítva a Roaring Bitmap erőteljes eszközt biztosít a fejlesztők számára. A Roaring Bitmap fejlődésével további funkciók és optimalizációk várhatók. > Miért csináltam ezt egyáltalán? Idősoros adatbázisokban az egyes címkék szerinti indexeléshez és a gyors únió műveletekhez.