Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

BSBD_k_ekzamenu / материал_к_билетам_14-21 / Билет_20_вопрос_1 / Индексы_на_основе_битовых_карт

.doc
Скачиваний:
10
Добавлен:
05.06.2015
Размер:
31.74 Кб
Скачать

2

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.

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

Битовые индексы и простые индексы по одной и той же таблице могут быть совмещены. Но если для таблицы используется кластерный индекс, то битовый индекс для нее уже не может быть применен, поскольку идентификатор строки фактически нечисловой. Совмещение и одновременное применение простых и битовых индексов выполняется алгоритмически. Также может быть организована многоиндексная выборка совместно из простого и битового индекса.

К обычным достоинствам битовых индексов относится то, что битовые операции могут быть оптимизированы и могут выполняться значительно быстрее чем операции с простыми списками. Другим достоинством является относительно меньший объем используемой дисковой памяти, чем в случае обычных индексов.