Битовый индекс

Битовый индекс — это структура данных, используемая в системах управления базами данных (СУБД) и информационном поиске для ускорения операций выборки, фильтрации и агрегации по столбцам, содержащим небольшое количество уникальных значений (кардинальность). В отличие от традиционных B-деревьев, битовые индексы хранят информацию о каждой строке таблицы в виде битовых строк (битовых карт), где каждый бит соответствует одному значению атрибута. Это позволяет выполнять логические операции (AND, OR, NOT) над множествами строк с высокой эффективностью.

История

Концепция битовых индексов была предложена в 1980-х годах как альтернатива инвертированным спискам и B-деревьям для аналитических запросов. Первые реализации появились в коммерческих СУБД, ориентированных на хранилища данных (Data Warehousing), где преобладают операции чтения больших объёмов данных. Пионерами в этой области стали системы, такие как Sybase IQ (1995) и Oracle с опцией Bitmap Index. В 2000-х годах битовые индексы получили широкое распространение в open-source решениях, например, в СУБД PostgreSQL (через расширение bitmap scan), Apache Druid, ClickHouse и Vertica. Развитие технологий сжатия битовых строк (например, алгоритмы WAH, BBC, Roaring Bitmaps) позволило значительно уменьшить объём хранимых данных, что сделало битовые индексы применимыми даже для столбцов с умеренной кардинальностью.

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

Битовый индекс представляет собой набор битовых карт, каждая из которых соответствует одному уникальному значению столбца. Для столбца с $N$ строками и $M$ уникальными значениями создаётся $M$ битовых строк длиной $N$ бит. Если в строке $i$ значение атрибута равно $k$, то в карте для значения $k$ бит с номером $i$ устанавливается в 1, иначе — в 0.

Пример

Рассмотрим таблицу «Продажи» со столбцом «Регион», содержащим значения: «Москва», «Санкт-Петербург», «Казань». Для трёх строк:

Битовые карты будут выглядеть так:

• Москва: 1 0 1
• Санкт-Петербург: 0 1 0
• Казань: 0 0 0

Запрос «Найти строки, где регион = Москва ИЛИ Санкт-Петербург» выполняется как побитовое OR двух карт: 101 OR 010 = 111, что даёт все три строки.

Классификация битовых индексов

По типу хранимых значений

• Простые битовые индексы — для столбцов с фиксированным набором значений (пол, статус, категория).
• Битовые индексы с кодированием — для числовых данных, где значения группируются в диапазоны (например, «возраст 18–25»). Используются битовые карты для каждого диапазона.
• Битовые индексы с отображением — для столбцов с высокой кардинальностью, где значения хэшируются или преобразуются в битовые строки через специализированные функции (например, Bloom-фильтры).

По способу сжатия

• Без сжатия — хранятся в виде плоских битовых массивов. Эффективны только для очень малых таблиц.
• Сжатые битовые индексы — применяют алгоритмы, уменьшающие объём данных за счёт кодирования повторяющихся последовательностей (например, WAH — Word-Aligned Hybrid, BBC — Byte-aligned Bitmap Code, Roaring Bitmaps). Roaring Bitmaps — один из наиболее популярных современных форматов, обеспечивающий высокую скорость операций и хорошее сжатие для разреженных данных.

По типу запросов

• Однородные — поддерживают только равенство (=) и простые логические комбинации.
• Диапазонные — позволяют выполнять запросы с операторами сравнения (<, >, BETWEEN) за счёт построения дополнительных карт для кумулятивных сумм.

Устройство и характеристики

Структура хранения

Битовый индекс обычно состоит из:

• Словаря значений — таблицы, сопоставляющей каждому уникальному значению столбца его идентификатор (обычно целое число).
• Массива битовых карт — каждая карта хранится в виде последовательности битов, возможно, сжатой. В современных СУБД карты могут быть организованы в виде сегментов (chunks) для параллельной обработки.

Операции над битовыми индексами

• Побитовое AND — пересечение множеств (например, «регион = Москва И возраст > 30»).
• Побитовое OR — объединение множеств («регион = Москва ИЛИ Санкт-Петербург»).
• Побитовое NOT — дополнение множества («все строки, кроме региона = Москва»).
• Агрегация — подсчёт количества единиц в карте (COUNT) без извлечения самих строк.

Производительность

• Скорость чтения: битовые индексы позволяют выполнять логические операции над миллионами строк за микросекунды, так как процессоры современных компьютеров оптимизированы для побитовых операций (SIMD-инструкции).
• Скорость записи: вставка, обновление или удаление строк требует обновления всех битовых карт, что может быть медленным. Поэтому битовые индексы обычно применяются в системах с редкими изменениями данных (OLAP) и не рекомендуются для OLTP-нагрузок.
• Объём памяти: для столбцов с низкой кардинальностью (менее 1% от числа строк) битовые индексы могут занимать значительно меньше места, чем B-деревья. Например, для столбца с 100 уникальными значениями и 1 млн строк несжатый индекс займёт около 12,5 МБ (100 × 1 млн бит), а сжатый — ещё меньше.

Применение

Хранилища данных и аналитика

Битовые индексы широко используются в системах бизнес-аналитики (BI) для ускорения запросов, фильтрующих данные по нескольким категориальным признакам. Примеры:

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

Поисковые системы

В полнотекстовом поиске битовые индексы применяются для хранения инвертированных списков: каждому слову (терму) соответствует битовая карта, указывающая на документы, содержащие это слово. Это позволяет быстро находить пересечения (например, документы, содержащие одновременно «кот» и «собака»).

Графовые базы данных

В некоторых графовых СУБД битовые индексы используются для хранения связей между вершинами, что ускоряет операции поиска соседей и обхода графа.

Обработка событий

В системах мониторинга и телеметрии (например, Prometheus, Grafana Loki) битовые индексы помогают фильтровать потоки событий по меткам (labels) с низкой кардинальностью.

Преимущества и недостатки

Преимущества

• Высокая скорость выполнения сложных логических запросов — особенно для комбинаций нескольких условий.
• Эффективное сжатие — для столбцов с низкой кардинальностью объём индекса может быть меньше, чем исходные данные.
• Масштабируемость — битовые операции легко распараллеливаются на многоядерных процессорах и кластерах.
• Поддержка агрегаций без извлечения строк — например, подсчёт количества записей, удовлетворяющих условию, выполняется без чтения самих данных.

Недостатки

• Медленная запись — каждая модификация данных требует перестроения нескольких битовых карт.
• Непригодность для столбцов с высокой кардинальностью — если количество уникальных значений превышает несколько тысяч, размер индекса может стать сопоставимым с размером таблицы, а производительность запросов падает.
• Ограниченная поддержка в OLTP-системах — из-за проблем с блокировками и конкурентным доступом.
• Сложность реализации диапазонных запросов — для числовых данных требуется дополнительное кодирование.

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

• Алгоритм Roaring Bitmaps, разработанный в 2010-х годах, используется в таких проектах, как Apache Spark, Apache Lucene, Elasticsearch и Druid. Он сочетает скорость сжатых битовых массивов с эффективностью работы с разреженными данными.
• В СУБД Oracle битовые индексы могут быть «битовыми индексами с объединением» (bitmap join indexes), которые позволяют индексировать связи между таблицами без денормализации.
• В некоторых системах, например, в Vertica, битовые индексы применяются не только для фильтрации, но и для сортировки данных на этапе загрузки.

Источники

• Garcia-Molina, H., Ullman, J. D., Widom, J. «Database Systems: The Complete Book» (2nd edition). Pearson, 2009.
• Wu, K., Otoo, E. J., Shoshani, A. «Optimizing bitmap indices with efficient compression». ACM Transactions on Database Systems, 2006.
• Lemire, D., Kaser, O., Gutierrez, E. «Roaring Bitmaps: Implementation of an Optimized Software Library». Software: Practice and Experience, 2018.
• Документация PostgreSQL: «Bitmap Scan» (официальное руководство).
• Документация ClickHouse: «LowCardinality Data Type» (официальное руководство).