BSBD_k_ekzamenu / материал_к_билетам_14-21 / Билет_20_вопрос_1 / Индексы_на_основе_битовых_карт
.doc
http://karataev.nm.ru/ind/bitmap.html
Битмап индекс (bitmap index)
Битовый индекс является дополнительной структурой данных к основной, отображающей значения индексируемого атрибута на набор идентификаторов записей. В целом определение такое же, как и у простого индекса, но набор идентификаторов строк формируется иначе. Если в случае простого индекса хранятся хначения идентификаторов и, вообще говоря, они могут быть произвольными, в том числе строками, то в случае битовых индексов идентификаторы рассматриваются строго как целые числа.
Набором идентификаторов является битовая последовательность, в которой идентификатору строки соответствует положение бита в соответствии с его величиной. Наличие записи с заданным значением атрибута отмечается 1, отсутствие - 0 или пустым хвостом. Положим, что есть четыре записи:
1 шарик красный 12
2 шарик синий 5
3 кубик красный 7
4 кубик синий 3
В этом случае есть 4 идентификатора, их значения рассматриваются как позиции битов в битовой карте. В карте получается в данном случае 4 бита. По атрибуту фигура два различных значения, поэтому в этом индексе будет две карты. То же самое по атрибуту цвет.
Вот как будут выглядеть битовые карты по двум разным атрибутам
Битовая карта 1 (битмап индекс) по фигуре
значение атрибута биты 1 2 3 4
шарик 1 1 0 0
кубик 0 0 1 1
Битовая карта 2 (битмап индекс) по цвету
значение атрибута биты 1 2 3 4
красный 1 0 1 0
синий 0 1 0 1
Чтобы использовать битовые карты, база данных должна поддерживать операции с битовыми строками.
Операции получения идентификаторов строк по значениям атрибутов сводятся к использованию битовых операций с битовыми картами и выборке из получившейся битовой карты позиций ненулевых битов. Значения этих позиций считаются идентификаторами строк. Т.е., например, при выборке оператором SELECT синих объектов в примере нашей исходной таблицы строка значений атрибута первого столбца нашей исходной таблицы (первой строки в битовой карте 2) умножаются на на значения бита нижней строки битовой карты 2.
К особенностям битовых индексов относится то, что они могут быть, как и простые индексы, составными, но не могут быть кластерными. Другим ограничением является то, что идентификатором строки данных должно быть строго натуральное число. В большинстве систем второе ограничение совершенно незаметно, поскольку идентификаторы и без того поддерживаются в автоинкрементном режиме.
Битовые индексы и простые индексы по одной и той же таблице могут быть совмещены. Но если для таблицы используется кластерный индекс, то битовый индекс для нее уже не может быть применен, поскольку идентификатор строки фактически нечисловой. Совмещение и одновременное применение простых и битовых индексов выполняется алгоритмически. Также может быть организована многоиндексная выборка совместно из простого и битового индекса.
К обычным достоинствам битовых индексов относится то, что битовые операции могут быть оптимизированы и могут выполняться значительно быстрее чем операции с простыми списками. Другим достоинством является относительно меньший объем используемой дисковой памяти, чем в случае обычных индексов.