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, би бил да се използва bitwise AND операция.

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

Тогава, чрез извършване на bitwise 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)     // Инициализира с 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	// Операциите с 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)     // Инициализира с 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	// Операциите с 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 е мощен инструмент за ефективно съхранение и манипулиране на множества от цели числа с висока кардиналност. В езика Go, използвайки пакета github.com/RoaringBitmap/roaring, можете лесно да използвате всички функции на Roaring Bitmap. Този пакет максимизира използването на паметта и производителността чрез различни типове контейнери и оптимизирани операции. Roaring Bitmap може да се използва в различни области като индексиране на бази данни, анализ на логове и статистически изчисления за реализиране на ефективна обработка на данни.

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

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