GoSuda

Яркое растровое изображение

By snowmerak views ...

Что такое битмап?

Здесь битмап является одним из видов индекса. Если вы пришли, думая о компьютерной графике, можете нажать «назад».

Базовые понятия

Битмап (bitmap) представляет собой одну из техник индексирования в базах данных. Значения определенного столбца представляются в виде одного элемента или формы битового массива или вектора, где каждый бит указывает, существует ли определенное значение данного столбца. Поэтому в простейшей форме каждой строке (row) назначается битовый индекс, а наличие или отсутствие значения выражается нулями и единицами.

Например, предположим, что есть таблица со столбцом пола. В этой таблице 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 бит целого числа извлекаются и используются как позиция внутри контейнера.

Контейнер

Контейнер, как и было сказано в аналогии, соответствует внутреннему массиву двумерного массива. Однако, в отличие от внешнего массива, внутренняя структура контейнера меняется в зависимости от того, сколько данных в нем содержится. 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	// операции с 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: проверяет, существует ли определенное значение в битмапе
  • 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	// операции с 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 появится еще больше функций и оптимизаций.

Зачем я всё это делал? Чтобы реализовать индексирование по каждому тегу и быстрые операции объединения в базе данных временных рядов.