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

2021-12-19T20:55:53Z

188.170.74.44: Убрать "заметим"

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

[[Файл: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)$.
* '''Индексы на строки'''. Рекомендуется использовать упорядоченные индексы только если имеются массовые операции над строками (например, поиск по префиксу). При этом на строках допускаются хеш-индексы, но для запросов потребуется знать точное значение строки.

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

[[Категория: Базы данных]]

Викиконспекты - Вклад участника [ru]

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