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

1.

Курс «Хранилища данных»
Тема: Битовые индексы
Барабанщиков
Игорь Витальевич
1

2.

Индекс
Индекс – это структура,
которая определяет
соответствие значения
ключа записи (атрибута или
группы атрибутов) и
местоположения этой
записи
Индексирование – это
средство ускорения
операций поиска записей в
таблице.
2

3.

Использование индексов
• Каждый индекс связан с определенной таблицей
• Индекс обычно хранится отдельно от таблицы
• СУБД использует индексы неявно при выполнении
команд SQL.
• СУБД поддерживает индексы в актуальном состоянии.
3

4.

Индексы СУБД Oracle
• В*Tree индексы:
- наиболее часто используемый тип индекса
• Reverse – индексы
• Индексы, основанные на функциях
(function-based)
• Bitmap-индексы
• Пространственные индексы
• Составные индексы
4

5.

Bitmap Index
• Bitmap index – метод битовых индексов
заключается в создании отдельных битовых карт
(последовательность 0 и 1) для каждого
возможного значения столбца.
• Каждому биту соответствует строка с
индексируемым значением, а его значение
равное 1 означает, что запись, соответствующая
позиции бита содержит индексируемое значение
для данного столбца или свойства.
• Основное преимущество битовых индексов в
том, что на больших множествах с низкой
мощностью и хорошей кластеризацией по их
значениям индекс будет меньше чем B*-tree.
5

6.

Структура Bitmap-индекса
Значение
Начало
Конец
Битовая карта
Мужской
Адрес 1-й строки Адрес последней
строки
10010100
Женский
Адрес 1-й строки Адрес последней
строки
01101011
• Применяются, в основном, в OLAP-системах.
• Это идеальный индекс для столбца с низкой
кардинальностью (число уникальных записей в
таблице мало) при большом размере таблицы.
• Чувствительны к перестроению индекса.
6

7.

Структура bitmap-индекса
7

8.

Особенности bitmap-индекса
• каждый элемент битового индекса открывает огромное
количество строк в таблице, так что когда данные
обновляются или вставляются из таблицы, то
необходимые обновления битового индекса очень
велики.
• сам индекс может существенно увеличиться в размере.
Единственный способ обойти это увеличение размера
индекса с последующим падением
производительности заключается в регулярной его
перестройке.
• Битовый индекс – не слишком разумная альтернатива
для таблиц, подвергающихся большому количеству
вставок, удалений и обновлений.
8

9.

Сравнение B*Tree и Bitmap индексов
B*Tree Index
Bitmap Index
Хороши для данных с
высокой кардинальностью
Хороши для данных с низкой
кардинальностью
Хороши для баз данных OLTP
Хороши для хранилищ
данных и OLAP
Занимают много места
Используют относительно
мало места
Легко обновляются
Трудно обновляются
9

10.

Пример BITMAP-индекса
В таблице EMP есть поле SEX (пол), которое
обладает низкой селективностью – может
принимать всего два значения.
CREATE BITMAP INDEX idx_sex
ON emp(sex);
10

11.

Применение Bitmap-индексов
Применение Bitmap-индексов особенно
эффективно при выполнении сложных запросов,
выбирающих данные по нескольким условиям.
11

12.

Применение Bitmap-индексов
Bitmap индексы полезны когда:
• Количество уникальных значений в столбце
мало по сравнению с количеством строк
таблицы.
• Количество строк в таблице большое.
• Столбец используется в операциях
булевой алгебры.
12

13.

Применение Bitmap-индексов
Bitmap-индексы лучше всего подходят для DSS-систем
независимо от селективности, по следующим
причинам:
• С bitmap-индексами оптимизатор может эффективно
отвечать на запросы, которые включают AND, OR
или XOR.
• С bitmap-индексами оптимизатор может отвечать на
запросы, когда выполняется поиск или подсчет nullов. Значения null также индексируются в bitmapиндексах (в отличие от B*tree индексов).
• Bitmap-индексы в DSS системах поддерживают ad
hoc запросы, в то время как B*tree нет.
13

14.

Итоги
Применение Bitmap индексов в ХД позволяет
оптимизировать их производительность при
выполнении сложных SQL-запросов.
14