Битмап-индекс

Битмап-индекс (от англ. bitmap index, битовый индекс) — это структура данных в системах управления базами данных (СУБД), предназначенная для ускорения поиска записей по столбцам с небольшим количеством уникальных значений (низкой кардинальностью). В отличие от традиционного B-дерева, которое хранит упорядоченные ключи и ссылки на строки, битмап-индекс представляет каждое уникальное значение столбца в виде битовой карты (битового массива), где каждый бит соответствует одной строке таблицы. Значение бита (1 или 0) указывает, принадлежит ли данная строка этому значению.

Принцип работы

Битмап-индекс строится для каждого уникального значения (или диапазона значений) индексируемого столбца. Для таблицы, содержащей N строк, каждый такой индекс представляет собой битовую строку длиной N бит. Если в строке с номером i значение столбца равно индексируемому, то i-й бит в битовой карте устанавливается в 1, в противном случае — в 0.

Например, для столбца «Пол» с возможными значениями «Мужской» и «Женский» будут созданы два битмап-индекса:

• Индекс для значения «Мужской»: битовая карта, где 1 стоит на позициях строк, где пол указан как мужской.
• Индекс для значения «Женский»: зеркальная карта для женского пола.

Поиск записей по условию (например, «Пол = Мужской») сводится к простому считыванию соответствующей битовой карты. Для сложных условий с логическими операциями (AND, OR, NOT) применяются быстрые побитовые операции над битовыми картами, что позволяет выполнять фильтрацию без полного сканирования таблицы. Например, запрос «Пол = Мужской AND Возраст > 30» может быть выполнен как побитовое И между битмапом для «Мужской» и битмапом для диапазона возраста.

История

Концепция битмап-индексов была впервые предложена в 1980-х годах для систем, работающих с большими объёмами данных, где традиционные индексы на основе B-деревьев оказывались неэффективными из-за высоких накладных расходов на хранение и обновление. Одним из пионеров стала компания Sybase, внедрившая битмап-индексы в свою СУБD Sybase IQ (ныне SAP IQ) в 1990-х годах. Позднее технология была адаптирована другими системами, включая Oracle (с версии 7.3), PostgreSQL (через расширение bitmap scan), а также в специализированных колоночных СУБД, таких как Apache Druid, ClickHouse и Vertica.

Сравнение с B-деревом

Основные отличия битмап-индекса от классического B-дерева:

Классификация

По типу значений

1. Простые битмап-индексы — для дискретных значений (например, «Цвет», «Статус заказа»).
2. Битмап-индексы с диапазонами — для числовых или датовых значений, где битовая карта строится не на каждое значение, а на интервал (например, «Возраст от 20 до 30»). Это снижает количество карт при умеренной кардинальности.

По способу хранения

1. Плоские битмап-индексы — каждая битовая карта хранится как непрерывный массив бит. Простота реализации, но неэффективно при разреженных данных.
2. Сжатые битмап-индексы — используют алгоритмы сжатия, такие как Word-Aligned Hybrid (WAH), Concise или Roaring Bitmaps. Позволяют сократить объём памяти в 10–100 раз на типичных данных.

Применение

Битмап-индексы наиболее эффективны в следующих сценариях:

• Хранилища данных (Data Warehouses) — где таблицы содержат миллионы или миллиарды строк, а столбцы имеют низкую кардинальность (например, «Регион», «Категория товара», «Год»). Запросы часто включают агрегацию и фильтрацию по нескольким таким столбцам.
• Системы бизнес-аналитики (BI) — для быстрого выполнения OLAP-запросов с группировкой и фильтрацией.
• Колоночные СУБД — где данные хранятся по столбцам, что естественным образом сочетается с битмап-индексами.
• Поисковые системы — для индексации атрибутов документов (например, язык, тип файла).

Ограничения и недостатки

1. Высокая кардинальность — при большом количестве уникальных значений (например, «Имя клиента») количество битовых карт становится слишком большим, а их размер — избыточным. В таких случаях битмап-индексы неэффективны.
2. Операции вставки и обновления — каждая модификация строки требует перестроения всех битовых карт, затрагивающих изменённые столбцы. Это приводит к блокировкам и снижению производительности в системах с высокой транзакционной нагрузкой (OLTP).
3. Разреженные данные — если большинство значений в столбце уникальны или редки, битовые карты становятся почти полностью нулевыми, что снижает эффективность сжатия и поиска.

Примеры использования в СУБД

• Oracle — поддерживает битмап-индексы с версии 7.3, рекомендует их для столбцов с кардинальностью менее 1% от общего числа строк.
• PostgreSQL — использует bitmap scan для объединения нескольких индексов (в том числе B-деревьев) в битовые карты, что ускоряет сложные запросы.
• ClickHouse — поддерживает битмап-индексы как часть движка MergeTree, позволяя фильтровать данные по множеству условий без полного сканирования.
• Apache Druid — применяет битмап-индексы для сегментов данных, обеспечивая субсекундные ответы на запросы с фильтрацией.

Интересные факты

• Битмап-индексы особенно эффективны при работе с «звёздными схемами» (star schema) в хранилищах данных, где таблицы фактов соединяются с таблицами измерений, имеющими низкую кардинальность.
• Алгоритм Roaring Bitmap (разработан в 2011 году) считается одним из лучших для сжатия битовых карт, сочетая скорость и компактность. Он используется в Apache Spark, Elasticsearch и других системах.
• В СУБД Oracle битмап-индексы могут быть объединены с битовыми картами для столбцов с высокой кардинальностью через технику bitmap join index, которая предварительно вычисляет соединения между таблицами.

Источники

• Oracle Database Concepts, 19c — Bitmap Indexes
• PostgreSQL Documentation — Bitmap Scans
• ClickHouse Documentation — Data Skipping Indexes
• Apache Druid Documentation — Bitmap Indexes
• «Database Systems: The Complete Book» — H. Garcia-Molina, J. D. Ullman, J. Widom
• «Roaring Bitmaps: Implementation of an Optimized Software Library» — D. Lemire, O. Kaser, 2011