GoSuda

Жизнерадостен растерен образ

By snowmerak views ...

Какво е битмап?

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

Основно понятие

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

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

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

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

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

И така, къде всъщност се използва

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

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.

  • Нека битовият индекс за колоната active 1100110011... (битов масив от 1 000 000 бита) е предварително индексиран,
  • а битовият индекс за колоната sex 1010101010... (битов масив от 1 000 000 бита) е предварително индексиран.

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

Компромиси

Битовите индекси могат да бъдат много ефективни, но имат някои компромиси. Има и много други недостатъци, но сега ще отбележим само един.

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

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

И така, какво правим

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

Основни понятия на Roaring Bitmap

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

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

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

Контейнери

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

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

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

Функции на Roaring Bitmap

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

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

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

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

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

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

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

В езика 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)     // инициализиране с 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // инициализиране с 2, 4, 6, 8, 12
12
13	b1.Add(5)  // добавяне на 5
14	b2.Add(10) // добавяне на 10
15
16	b2.Remove(12) // премахване на 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// операциите с битмапове променят оригинала, затова се създава копие за използване
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: проверява дали определена стойност съществува в битмапа
  • GetCardinality() uint64: връща броя на елементите в битмапа
  • Rank(x uint32) uint64: връща броя на елементите, по-малки или равни на определена стойност
  • ToBytes() ([]byte, error): сериализира битмапа в байтов слайс
  • FromBytes(data []byte) error: възстановява битмапа от байтов слайс
  • Clone() *Bitmap: създава копие на битмапа
  • Clear(): нулира битмапа
  • NextValue(x uint32) int64: връща следващия елемент, по-голям или равен на x
  • PreviousValue(x uint32) int64: връща предишния елемент, по-малък или равен на x
  • Maximum() uint32: връща най-големия елемент в битмапа
  • Minimum() uint32: връща най-малкия елемент в битмапа

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

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

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

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