8
правок
Изменения
Новый викиконспект: Индексация данных. Другие типы индексов. Применение индексов
== Другие типы индексов ==
[[Файл:Index_Bitmap_1.png|мини|Пример битового индекса]]
===Битовый (bitmap) индекс===
Пусть в таблице имеется колонка, способная хранить ограниченный набор значений. Битовый индекс для каждого возможного значения хранит `1`, если это значение хранится в данной строке, и `0` иначе.
Таким образом, количество битовых столбцов равно числу возможных значений для того столбца, по которому строится битовый индекс.
Ускоряемые запросы:
* Вычисление логических выражений
* Запросы с `count`: требуется считать только количество единичных битов, что эффективно
Основным недостатком битовых индексов является долгое обновление данных.
[[Файл:Index_Bitmap_3.png|мини|Битовый индекс с накоплением]]
===Битовый индекс с накоплением===
В случае, когда значения столбца, по которому строится битовый индекс, упорядочены, имеет место битовый индекс с накоплением. В отличии от обычного битового индекса, `1` записывается для всех значений, больше или равных заданному. Такой индекс позволяет эффективно проводить операции сравнения с константой.
[[Файл:Index_Bitmap_5.png|мини|Пример составного битового индекса и запроса в нём: `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`-мерные параллелепипеды.
[[Файл:Index_Other_RTree.png|thumb|center|600px|Пример R-дерева (справа) и разбиения данных]]
Ускоряемые запросы:
* Диапазоны по нескольким координатам
* Поиск ближайших значений
== Применение индексов ==
===Когда используется индекс?===
Заметим, что упорядоченные индексы эффективно использовать не только на полном наборе столбцов, но и на его префиксе. Например, упорядоченный индекс по `(Name, Surname)` позволяет эффективно искать по `Name`, однако для поиска только по `Surname` данный индекс бесполезен. Также, для составных ключей можно использовать диапазоны, фиксируя префикс ключа.
Следует отметить, что в индексах допускается хранение $null$.
===Селективность индекса===
{{Определение
|definition=
'''Селективностью индекса''' назвается характеристика, определяющая, насколько эффективно индекс разбивает данные.
}}
Примеры селективности:
* Процент записей, получаемый по значению
* Среднее: $\operatorname{count}(distinct) / count$ - количество различных значений по отношению к общему числу значений
* Худшее: $\max(count) / count$ - размер максимального из значений по отношению к общему числу значений
Примеры индексов и их селективности:
* Номер паспорта: высокая селективность
* Возраст человека: средняя селективность
* Пол человека: низкая селективность
===Оценка селективности===
Для оценивания селективности можно использовать несколько подходов. Например, опираться на статистику с предыдущих запросов или подсчитывать специальным образом.
Например, для хеш-индексов можно использовать размеры и количество корзин. Если значение входит в корзину большого размера, вероятно, селективность индекса ниже. Для B-деревьев имеют место гистограммы распределения, построенные на верхних уровнях.
В случае достаточно низкой селективности индексы не используются, так как в такой ситуации полное последовательное чтение таблицы эффективнее, чем несколько случайных чтений.
===Покрывающий индекс===
{{Определение
|definition=
'''Покрывающим индексом''' назвается упорядоченный индекс, хранящий не только столбцы, по которым осуществляется поиск, но и дополнительные столбцы, загружающиеся вместе со столбцами для поиска.
}}
После поиска, для получения значений столбцов, хранящихся в покрывающем индексе, не требуется обращаться к записи - эта информация уже получена из индекса. С другой стороны, покрывающие индексы имеют повышенную высоту дерева и занимают больше памяти.
Покрывающие индексы очень полезны при покрытии идентификаторов: ветвимость дерева уменьшается незначительно (особенно, если в столбцах для поиска есть строки), и при этом не требуется обращаться непосредственно к записям.
===Рекомендации===
* '''Индексы на ключи'''. Данная рекомендация очень распространённая, и многие современные СУБД автоматически их создают.
* '''Индексы на внешние ключи'''
* '''Индексы на запросы по диапазонам'''. Для таких запросов стоит рассмотреть построение упорядоченного индекса.
* '''Индексы таблиц связей'''. Часто используются покрывающие индексы, причём, для двух столбцов, два индекса, в оба направления (так как неизвестно, какое направление использует запрос): $(id_1, id_2)$ и $(id_2, id_1)$.
* '''Индексы на строки'''. Рекомендуется использовать упорядоченные индексы только если имеются массовые операции над строками (например, поиск по префиксу). При этом на строках допускаются хеш-индексы, но для запросов потребуется знать точное значение строки.
