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, можно использовать операцию битового И.

  • Предположим, что Bitmap-индекс для столбца active предварительно проиндексирован как 1100110011... (битовый массив из 1 000 000 бит), и
  • Bitmap-индекс для столбца sex предварительно проиндексирован как 1010101010... (битовый массив из 1 000 000 бит).

Тогда, выполнив операцию битового И над двумя Bitmap-индексами, можно быстро найти строки, в которых оба столбца имеют значение TRUE. Поскольку это простая битовая операция, результат можно получить намного быстрее, чем при сканировании других индексов.

Компромиссы

Bitmap-индексы могут быть очень эффективными, но имеют несколько компромиссов. Несмотря на множество других недостатков, сейчас мы остановимся только на одном.

А именно, Bitmap-индексы больше подходят для низкой кардинальности (то есть, когда количество возможных значений в столбце невелико). Использование Bitmap-индекса для столбца с высокой кардинальностью может привести к очень большому Bitmap.

При использовании Bitmap-индекса для столбца с высокой кардинальностью может потребоваться много места для хранения, так как для каждого уникального значения необходимо создать отдельный Bitmap. Например, если столбец содержит 1 000 000 уникальных значений, потребуется создать 1 000 000 Bitmap'ов, что может быть очень неэффективно.

Итак, мы

В качестве альтернативы Bitmap'ам, возникающим при высокой кардинальности, можно использовать Roaring Bitmap. Roaring Bitmap обладает несколькими характеристиками, но его основная философия и особенность заключаются в динамическом выборе наиболее подходящего метода хранения в зависимости от плотности данных, чтобы максимизировать как степень сжатия, так и скорость операций.

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

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

Roaring Bitmap для хранения одного целого числа сначала проходит следующие 2 этапа. Это называется двухуровневым индексированием, но вы можете просто представить это как двумерный массив.

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

Контейнер

Этот контейнер соответствует внутреннему массиву в двумерном массиве, как было упомянуто ранее. Однако, в отличие от старших 16 бит, внутренняя структура этого контейнера меняется в зависимости от количества содержащихся в нем данных. Roaring Bitmap поддерживает следующие 3 типа контейнеров.

  • Array Container: Этот контейнер используется, когда внутри хранится мало данных. В частности, он используется для хранения до 4096 элементов. Этот контейнер просто реализован как отсортированный массив целых чисел. Элементы можно найти с помощью бинарного поиска.
  • Bitmap Container: Этот контейнер используется, когда внутри хранится много данных. В частности, он используется для хранения более 4096 элементов. Этот контейнер реализован как Bitmap из 65536 бит (8192 байта). Каждый бит указывает на наличие или отсутствие целого числа в соответствующей позиции.
  • 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 будет продолжаться, принося новые функции и оптимизации.

Зачем я это сделал? Для индексирования по тегам и быстрых операций объединения в базах данных временных рядов.