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

1) Битовый индекс занимает меньший объем памяти, чем обычное В-дерево.

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

V – число записей в таблице БД

Lq – длина индексируемого атрибута

Lr – длина идентификатора записи (rowid)

Lb – длина битового сегмента двоичной карты

Требуемый объем вычисляется по формуле:

, где = длина записи блока листового уровня битового индекса. Q << объема памяти блоков листового уровня для В-дерева.

- примерное число записей в блоках листового уровня

Каждая запись листового уровня описывает примерно 8Lb записей в таблице БД.

2) Быстрое выполнение операций с сегментами двоичной карты

Задано то же условие поиска, оценим качественно время его выполнения

Предположим, что атрибуты q и s индексированы с помощью битовых индексов.

	q		s
	A		B

q

s

Поиск записей, удовлетворяющих условиям выполняется в следующей последовательности:

1) Выделяется bitmap_segment₁. (Индексы по s читаются в битовый сегмент bitmap_segment₁)

2) Выделяется bitmap_segment_{2 (}Индексы по s читаются в битовый сегмент bitmap_segment₂)

3) Определяется результирующий битовый сегмент двоичной карты

bitmap_segment₁ bitmap_segment_{2 =} bitmap_segment₃

4) Определяется список идентификаторов записей, удовлетворяющих условиям. На интервал (13, 20) накладывается заданная маска (13,20) {bitmap_segment}₃

При выполнении 3 операции выполняется логическое пересечение битовых массивов, это можно выполнить 1 ассемблерной командой (системе не требуется выполнять вложенных циклов)