GoSuda

Жив растер

By snowmerak
views ...

Какво представлява Bitmap?

Тук bitmap е вид индекс. Ако сте дошли с мисълта за графика, можете да натиснете бутона за връщане назад.

Основна концепция

Bitmap е форма на техника за индексиране на база данни. Тя представя стойностите на определена колона като битов масив или елемент или форма на вектор, като всеки бит показва дали определена стойност съществува в тази колона. Следователно, най-основната форма е да се присвои битов индекс на всеки ред и да се представи съществуването му с 0 и 1.

Например, да предположим, че има таблица с колона за пол. Тази таблица има 5 реда и стойностите на колоната за пол са както следва:

  1. Мъж
  2. Жена
  3. Мъж
  4. Жена
  5. Друго

В този случай, bitmap индексът за колоната за пол може да бъде представен по следния начин:

  • Мъж: 10100
  • Жена: 01010
  • Друго: 00001

Къде се използва всъщност

Следователно, всички биха си помислили, че това не е просто за представяне на това. За да използваме правилно bitmap индекса, нека разгледаме следния случай.

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

Да предположим, че тази таблица има 1 000 000 реда. И да предположим, че изпълняваме следната заявка.

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

Тази заявка търси редове, където колоните active и sex са и двете TRUE. Тогава най-бързият начин да се намерят редове, които отговарят на условието и двете колони да са TRUE, би бил да се използва битова AND операция.

  • Да предположим, че bitmap индексът за колоната active е предварително индексиран като 1100110011... (битов масив от 1 000 000 бита),
  • И да предположим, че bitmap индексът за колоната sex е предварително индексиран като 1010101010... (битов масив от 1 000 000 бита).

Тогава, чрез извършване на битова AND операция върху двата bitmap индекса, можем бързо да намерим редовете, където и двете колони са TRUE. Тъй като това е проста битова операция, резултатите могат да бъдат получени много по-бързо, отколкото при други сканирания на индекси.

Компромиси

Bitmap индексите могат да бъдат много ефективни, но имат няколко компромиса. Въпреки че има много други недостатъци, засега ще разгледаме само един.

Bitmap индексите са по-подходящи за ниска кардиналност (т.е. когато броят на възможните стойности в колоната е малък). Използването на bitmap индекси за колони с висока кардиналност може да доведе до много големи bitmap-ове.

Ако се използва bitmap индекс за колона с висока кардиналност, може да се наложи много място за съхранение, тъй като трябва да се генерира отделен bitmap за всяка уникална стойност. Например, ако една колона има 1 000 000 уникални стойности, трябва да се генерират 1 000 000 bitmap-а, което може да бъде много неефективно.

Ето защо ние

Можем да използваме Roaring Bitmap като алтернатива на bitmap-овете, които се получават при висока кардиналност. Roaring Bitmap има няколко характеристики, но най-голямата основна философия и характеристика е динамичното избиране на най-подходящия метод за съхранение според плътността на данните, за да се максимизират както степента на компресия, така и скоростта на операцията.

Основна концепция на Roaring Bitmap

Двустепенно индексиране

За да съхрани едно цяло число, Roaring Bitmap първо преминава през следните 2 стъпки. Въпреки че се нарича двустепенно индексиране, можете просто да го разглеждате като двуизмерен масив.

  • Извличане на горните 16 бита: Извличат се горните 16 бита на цялото число и се използват като индекс. Това става индексът на външния масив от двуизмерен масив с обща дължина 65536. Този масив съхранява адресите на контейнерите, които ще бъдат обсъдени по-късно.
  • Извличане на долните 16 бита: Извличат се долните 16 бита на цялото число и се използват като позиция в контейнера.

Контейнери

Този контейнер съответства на вътрешния масив на двуизмерния масив, както беше аналогия. Въпреки това, за разлика от горните 16 бита, този контейнер променя вътрешната си структура в зависимост от количеството данни вътре. Roaring Bitmap поддържа следните 3 типа контейнери.

  • Array Container: Този контейнер се използва, когато има малко съхранени данни. По-конкретно, той се използва за съхранение на до 4096 елемента. Този контейнер е имплементиран като просто сортиран масив от цели числа. Елементите могат да бъдат намерени чрез бинарно търсене.
  • Bitmap Container: Този контейнер се използва, когато има много съхранени данни. По-конкретно, той се използва за съхранение на повече от 4096 елемента. Този контейнер е имплементиран като 65536-битов (8192 байта) bitmap. Всеки бит показва дали цялото число на съответната позиция съществува.
  • Run Container: Този контейнер се използва за съхранение на непрекъснати диапазони от цели числа. Например, той е ефективен за съхранение на последователни цели числа като 1, 2, 3, 4, 5. Този контейнер е имплементиран като списък от двойки (начална стойност, дължина). Ако всички са там? Това просто означава, че всички са там от началото до края, така че просто трябва да съхраните само (0, 65536).

Този подход позволява на Roaring Bitmap да използва паметта много ефективно и да осигурява оптимална производителност за различни плътности на данните.

Функционалност на Roaring Bitmap

Основни функции

Roaring Bitmap предоставя следните основни функции:

  • Вмъкване: Добавя ново цяло число към bitmap-а. По време на този процес може да бъде избран подходящ контейнер или контейнерът може да бъде преобразуван, ако е необходимо.
  • Изтриване: Премахва съществуващо цяло число от bitmap-а. По време на този процес се извършва подходяща обработка в зависимост от състоянието на контейнера.
  • Търсене: Проверява дали определено цяло число съществува в bitmap-а. Този процес се извършва много бързо.

Операции с множества

Roaring Bitmap също поддържа следните операции с множества:

  • Обединение (Union): Създава нов bitmap, който съдържа всички елементи от двата bitmap-а.
  • Пресичане (Intersection): Създава нов bitmap, който съдържа само елементи, които съществуват и в двата bitmap-а.
  • Симетрична разлика (Symmetric Difference): Създава нов bitmap, който съдържа елементи, които съществуват само в един от двата bitmap-а.

Тези операции са оптимизирани според типа на контейнера на bitmap-а и се изпълняват много бързо.

В езика Go

В езика Go можете лесно да използвате Roaring Bitmap, като използвате пакета github.com/RoaringBitmap/roaring. Този пакет предоставя всички функции на Roaring Bitmap и е оптимизиран за характеристиките на езика Go.

Инсталация

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

Пример за употреба

 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)     // Инициализира b1 с 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Инициализира b2 с 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Добавя 5 към b1
14	b2.Add(10) // Добавя 10 към b2
15
16	b2.Remove(12) // Премахва 12 от b2
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Операциите с bitmap променят оригинала, така че използвайте клонинг
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]

Основните функции, които не са показани в горния примерен код, включват:

  • Contains(x uint32) bool: Проверява дали определена стойност съществува в bitmap-а.
  • GetCardinality() uint64: Връща броя на елементите в bitmap-а.
  • Rank(x uint32) uint64: Връща броя на елементите, по-малки или равни на определена стойност.
  • ToBytes() ([]byte, error): Сериализира bitmap-а в байтов срез.
  • FromBytes(data []byte) error: Възстановява bitmap от байтов срез.
  • Clone() *Bitmap: Създава клонинг на bitmap-а.
  • Clear(): Инициализира bitmap-а.
  • NextValue(x uint32) int64: Връща следващия елемент, по-голям или равен на x.
  • PreviousValue(x uint32) int64: Връща предишния елемент, по-малък или равен на x.
  • Maximum() uint32: Връща най-големия елемент в bitmap-а.
  • Minimum() uint32: Връща най-малкия елемент в bitmap-а.

За повече подробности вижте официалната документация.

Между другото, пакетът roaring включва пакет, който поддържа uint64, както и uint32. Тъй като предоставя почти същия интерфейс, той може да бъде заменен директно.

 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)     // Инициализира b1 с 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Инициализира b2 с 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Добавя 5 към b1
14	b2.Add(10) // Добавя 10 към b2
15
16	b2.Remove(12) // Премахва 12 от b2
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Операциите с bitmap променят оригинала, така че използвайте клонинг
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}

Заключение

Roaring Bitmap е мощен инструмент за ефективно съхранение и манипулиране на набори от цели числа с висока кардиналност. Използвайки пакета github.com/RoaringBitmap/roaring в Go, всички функции на Roaring Bitmap могат лесно да бъдат използвани. Този пакет максимизира използването на паметта и производителността чрез различни типове контейнери и оптимизирани операции. Roaring Bitmap може да се използва в различни области като индексиране на бази данни, анализ на логове и статистически изчисления за ефективна обработка на данни.

Roaring Bitmap е особено ефективен при големи набори от данни и може да бъде полезен в различни приложения. В комбинация с ясния и ефективен синтаксис на Go, Roaring Bitmap предоставя мощен инструмент за разработчиците. Очаква се Roaring Bitmap да продължи да се развива, предлагайки повече функции и оптимизации.

Защо направих това? За бързо обединение на операции и индексиране по тагове в бази данни за времеви серии.