Битовые карты

Битовая карта (англ. bitmap, bit array, bitmap index) — это структура данных, представляющая собой упорядоченный набор битов (двоичных разрядов), каждый из которых может принимать значение 0 или 1. В информатике и вычислительной технике битовые карты используются для компактного хранения множеств, флагов состояний, индексации данных и представления растровых изображений (в контексте графики термин «битовая карта» часто является синонимом растрового изображения, где каждый бит или группа битов кодирует цвет пикселя).

История

Концепция битового массива как способа компактного представления множества восходит к ранним этапам развития программирования. Одним из первых применений стало использование битовых масок в машинных кодах для управления флагами процессора и периферийными устройствами. В 1960-х годах битовые карты начали применяться в файловых системах (например, в операционной системе Unix для отслеживания свободных блоков на диске). С развитием графических дисплеев в 1970-х годах термин «bitmap» закрепился за форматом представления изображений, где каждый пиксель кодируется одним или несколькими битами. В 1980-х годах битовые индексы стали использоваться в системах управления базами данных для ускорения запросов к большим таблицам.

Классификация и виды

По способу представления

• Несжатые битовые карты — каждый бит хранится в явном виде, занимая фиксированный объём памяти. Пример: массив типа std::bitset в C++.
• Сжатые битовые карты — применяются алгоритмы сжатия (например, RLE, WAH, Roaring Bitmaps) для уменьшения объёма данных при разреженном заполнении. Используются в базах данных и поисковых системах.

По назначению

• Битовые индексы — структура данных для ускорения запросов в базах данных. Каждому значению атрибута соответствует битовая карта, где 1 указывает на строки, содержащие это значение.
• Битовые маски — набор флагов, используемый для кодирования состояний или прав доступа (например, в Unix-подобных системах права доступа к файлам кодируются тремя битами: чтение, запись, выполнение).
• Растровые изображения — графические файлы, где каждый пиксель представлен битовой картой (например, монохромные BMP-изображения, где 1 бит = 1 пиксель, или цветные с глубиной цвета 24 бита на пиксель).

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

Представление в памяти

Битовая карта обычно реализуется как массив целых чисел (например, unsigned int или uint64_t). Каждый элемент массива хранит фиксированное количество битов (32, 64 и т.д.). Для доступа к конкретному биту вычисляется номер элемента и смещение внутри него.

Пример: для хранения 1000 бит в массиве 32-битных целых чисел потребуется 32 элемента (1000 / 32 = 31,25, округление вверх).

Основные операции

• Установка бита: array[index] |= (1 << offset)
• Сброс бита: array[index] &= ~(1 << offset)
• Проверка бита: (array[index] >> offset) & 1
• Поиск первого установленного бита (FFS — Find First Set): аппаратная инструкция или побитовый поиск.
• Подсчёт единиц (population count): аппаратная инструкция POPCNT или алгоритмы с таблицами предварительных вычислений.

Эффективность

• Память: битовая карта занимает минимальный объём — 1 бит на элемент множества, что делает её эффективной для плотных множеств (где большинство битов установлено в 1). Для разреженных множеств (мало единиц) сжатые битовые карты (например, Roaring Bitmaps) могут быть компактнее.
• Скорость: побитовые операции (AND, OR, XOR) выполняются за O(N/word_size), где N — количество битов, word_size — размер машинного слова (32 или 64 бита). Это позволяет быстро выполнять операции над множествами (пересечение, объединение, разность).

Применение

Базы данных

Битовые индексы широко применяются в системах управления базами данных (СУБД) для ускорения запросов по атрибутам с небольшим количеством уникальных значений (кардинальность). Например, в столбце «Пол» (значения: «Мужской», «Женский») создаются две битовые карты: одна для мужчин, другая для женщин. Запрос «Найти всех мужчин старше 30 лет» выполняется как побитовое И между картой «Мужской» и картой «Возраст > 30». СУБД, активно использующие битовые индексы: Oracle, PostgreSQL (расширение bitmap scan), Apache Druid, ClickHouse.

Файловые системы

В файловых системах (например, ext2/ext3/ext4 в Linux) битовые карты используются для отслеживания свободных и занятых блоков данных и индексных дескрипторов (inode). Каждый бит соответствует одному блоку или inode: 1 — занят, 0 — свободен. Это позволяет быстро находить свободное место при записи нового файла.

Сетевые протоколы и телекоммуникации

• Флаги в заголовках пакетов: в протоколах TCP/IP, Ethernet и других битовые карты используются для кодирования флагов (например, SYN, ACK, FIN в TCP).
• Битовые маски подсетей: в IPv4 маска подсети (например, 255.255.255.0) представляет собой битовую карту, где единицы обозначают сетевую часть адреса, нули — хостовую.

Графика и обработка изображений

В контексте компьютерной графики термин «битовая карта» (bitmap) часто обозначает растровое изображение. Формат BMP (Windows Bitmap) является одним из старейших и простейших форматов, где пиксели хранятся в виде битовой карты. Монохромные изображения (1 бит на пиксель) и изображения с палитрой (например, 8 бит на пиксель с таблицей цветов) также являются примерами битовых карт.

Криптография и хеширование

• Фильтр Блума (Bloom filter) — вероятностная структура данных, основанная на битовой карте, используемая для проверки принадлежности элемента множеству. Применяется в базах данных, кэшах и системах защиты от спама.
• Битовые маски в алгоритмах хеширования: для проверки целостности данных или в системах контроля версий.

Операционные системы

• Управление памятью: в ядрах операционных систем битовые карты используются для отслеживания свободных и занятых страниц физической памяти (например, в Linux — struct page и битовые карты mem_map).
• Планировщики задач: битовые карты могут применяться для кодирования приоритетов процессов или состояний (готов, выполняется, заблокирован).

Примеры

Пример 1: Битовый индекс в базе данных

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

Запрос «Найти сотрудников из Москвы или Казани» выполняется как побитовое ИЛИ между картами «Москва» и «Казань»: 1010 OR 0001 = 1011, что соответствует ID 1, 3, 4.

Пример 2: Битовые маски прав доступа

В Unix-подобных системах права доступа к файлу кодируются тремя группами по три бита: владелец (rwx), группа (rwx), остальные (rwx). Например, значение 755 (двоично: 111 101 101) означает: владелец может читать, писать и выполнять; группа и остальные — читать и выполнять.

Критика и ограничения

• Разреженность: для множеств с очень малой плотностью единиц (например, 1% заполнения) несжатая битовая карта может быть неэффективной по памяти. В таких случаях предпочтительнее использовать сжатые битовые карты (Roaring Bitmaps) или другие структуры данных (например, деревья интервалов).
• Масштабируемость: при большом количестве уникальных значений атрибута (кардинальность > 10^5) число битовых карт может стать слишком большим, что приводит к росту объёма индекса и замедлению операций.
• Ограниченность типов данных: битовые индексы эффективны только для категориальных данных с низкой кардинальностью. Для непрерывных числовых значений (например, зарплата) требуется предварительное дискретизирование (создание диапазонов).
• Сложность обновления: при вставке или удалении строк в таблице необходимо обновлять все битовые карты, что может быть затратным по времени.

Источники

1. Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2006. — Глава 2.2.6.
2. Witten I. H., Moffat A., Bell T. C. Managing Gigabytes: Compressing and Indexing Documents and Images. — Morgan Kaufmann, 1999. — Глава 5.
3. Lemire D., Ssi-Yan-Kai G., Kaser O. Consistently faster and smaller compressed bitmaps with Roaring // Software: Practice and Experience. — 2016. — Vol. 46, No. 11. — P. 1547–1569.
4. Документация PostgreSQL: Bitmap Scans. — URL: https://www.postgresql.org/docs/current/indexes-bitmap-scans.html (дата обращения: 2025).
5. Документация Linux: Файловая система ext4. — URL: https://www.kernel.org/doc/html/latest/filesystems/ext4/index.html (дата обращения: 2025).