Индексация данных. Другие типы индексов. Применение индексов

Другие типы индексов

Пример битового индекса

Битовый (bitmap) индекс

Пусть в таблице имеется колонка, способная хранить ограниченный набор значений. Битовый индекс для каждого возможного значения хранит `1`, если это значение хранится в данной строке, и `0` иначе. Таким образом, количество битовых столбцов равно числу возможных значений для того столбца, по которому строится битовый индекс.

Ускоряемые запросы:

• Вычисление логических выражений
• Запросы с `count`: требуется считать только количество единичных битов, что эффективно

Основным недостатком битовых индексов является долгое обновление данных.

Битовый индекс с накоплением

Битовый индекс с накоплением

В случае, когда значения столбца, по которому строится битовый индекс, упорядочены, имеет место битовый индекс с накоплением. В отличии от обычного битового индекса, `1` записывается для всех значений, больше или равных заданному. Такой индекс позволяет эффективно проводить операции сравнения с константой.

Пример составного битового индекса и запроса в нём: `Gender = M and Year >= 3`

Составной битовый индекс

Представляет из себя битовый индекс, построенный на нескольких столбцах. Каждый столбец таблицы, на котором строится индекс, соответствует своему набору столбцов в битовом индексе. При этом индексы могут быть как с накоплением, так и без: например, одному столбцу соответствует обычный битовый индекс, а другому - битовый индекс с накоплением.

Оптимизация битового индекса

Основным преимуществом битовых индексов является небольшой объём памяти для хранения, в большинстве случаев их можно хранить в памяти целиком. Кроме того, существуют техники сжатия битовых индексов:

• RLE-кодирование (эффективно, так как в обычных битовых индексах хранится много нулей, и максимум одна единица)
• Byte-aligned Bitmap Code - индексы хранятся в упакованном виде, логические операции проводятся сразу же над ними, распаковка происходит только, когда это необходимо.

Недостатком оптимизированного хранения является сложность перестроения, что увеличивает время работы на их поддержание.

Размер битового индекса

Для несжатых битовых индексов: при различных `k` значениях и таблице с `n` строк хранение займёт `k * n` бит.

Оценка для сжатых индексов: предположим, что мы сжимаем по RLE. Всего в индексе `n` единиц, остаётся закодировать шаги в зависимости от их размера, что всего даёт порядка `O(n \log n)` бит. Следует обратить внимание, что эта оценка никак не зависит от `k`, что позволяет строить эффективные сжатые индексы на столбцах с большим диапазоном значений.

R-деревья

Для индексации многомерной информации и задач пространственного поиска одной из распространённых структур являются R-деревья. Для двумерного случая данные разбиваются на прямоугольники (допускаются пересечения), для `n`-мерного случая - `n`-мерные параллелепипеды.

Пример R-дерева (справа) и разбиения данных

Ускоряемые запросы:

• Диапазоны по нескольким координатам
• Поиск ближайших значений

Применение индексов

Когда используется индекс?

Заметим, что упорядоченные индексы эффективно использовать не только на полном наборе столбцов, но и на его префиксе. Например, упорядоченный индекс по `(Name, Surname)` позволяет эффективно искать по `Name`, однако для поиска только по `Surname` данный индекс бесполезен. Также, для составных ключей можно использовать диапазоны, фиксируя префикс ключа.

Следует отметить, что в индексах допускается хранение $null$.

Селективность индекса

Определение:

Селективностью индекса назвается характеристика, определяющая, насколько эффективно индекс разбивает данные.

Примеры селективности:

• Процент записей, получаемый по значению
• Среднее: $\operatorname{count}(distinct) / count$ - количество различных значений по отношению к общему числу значений
• Худшее: $\max(count) / count$ - размер максимального из значений по отношению к общему числу значений

Примеры индексов и их селективности:

• Номер паспорта: высокая селективность
• Возраст человека: средняя селективность
• Пол человека: низкая селективность

Оценка селективности

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

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

В случае достаточно низкой селективности индексы не используются, так как в такой ситуации полное последовательное чтение таблицы эффективнее, чем несколько случайных чтений.

Покрывающий индекс

Определение:

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

После поиска, для получения значений столбцов, хранящихся в покрывающем индексе, не требуется обращаться к записи - эта информация уже получена из индекса. С другой стороны, покрывающие индексы имеют повышенную высоту дерева и занимают больше памяти.

Покрывающие индексы очень полезны при покрытии идентификаторов: ветвимость дерева уменьшается незначительно (особенно, если в столбцах для поиска есть строки), и при этом не требуется обращаться непосредственно к записям.

Рекомендации

• Индексы на ключи. Данная рекомендация очень распространённая, и многие современные СУБД автоматически их создают.
• Индексы на внешние ключи
• Индексы на запросы по диапазонам. Для таких запросов стоит рассмотреть построение упорядоченного индекса.
• Индексы таблиц связей. Часто используются покрывающие индексы, причём, для двух столбцов, два индекса, в оба направления (так как неизвестно, какое направление использует запрос): $(id_1, id_2)$ и $(id_2, id_1)$.
• Индексы на строки. Рекомендуется использовать упорядоченные индексы только если имеются массовые операции над строками (например, поиск по префиксу). При этом на строках допускаются хеш-индексы, но для запросов потребуется знать точное значение строки.

Литература

• Дейт К. Введение в системы баз данных (Приложение Г)
• Кнут Д. Искусство программирования. Том 3. Сортировка и поиск
• Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts