Современные
информационные технологии/2. Вычислительная техника и программирование
Аспирант
Токарчук А.М.
Московский
государственный университет путей сообщения (МИИТ), Россия
Классификация индексов в современных СУБД
Индексы в современных системах
управления базами данных (СУБД) различаются по многим критериям, в данной
статье будет проведена их классификация.
Индексы могут различаться по порядку сортировки. Упорядоченные — индексы, в которых элементы поля (столбца) упорядочены. Они
делятся на возрастающие или убывающие. Кроме того индексы могут быть
и вовсе неупорядоченные.
Если рассматривать индексы с точки зрения источника данных, то существуют индексы по представлению (view), индексы по выражениям (например в
PostgreSQL).
По воздействию
на источник данных индексы делятся на кластерные и некластерные. Некластерный индекс — наиболее типичный
представители семейства индексов. В отличие от кластерных, они не перестраивают
физическую структуру таблицы, а лишь организуют ссылки на соответствующие
строки. Принципиальным отличием кластерного
индекса от индексов других типов является то, что при его определении в таблице
физическое расположение данных перестраивается в соответствии со структурой
индекса.
Внутренняя
структура характеризует механизм
хранения информации индекса: B*-деревья,
B+-деревья, B-деревья, хеши. В большинстве СУБД в качестве механизма
хранения используются бинарные деревья.
Количественный
состав характеризует логическую
структуру индексируемых данных. Простой
индекс (индекс с одним ключом) — строится по одному полю. Составной (многоключевой, композитный)
индекс — строится по нескольким полям. Важен порядок следования полей (например,
в СУБД MongoDB). Индекс с включенными столбцами — некластеризованный индекс,
дополнительно содержащий кроме ключевых столбцов еще и неключевые. Главный индекс (индекс по первичному
ключу) — это индекс по такому ключу, под управлением которого в данный момент
находится таблица.
Характеристика
содержимого отражает качественный
состав информации в ключе. Уникальный
индекс — состоит из множества уникальных значений поля. Плотный индекс (NoSQL*) — индекс, при котором, каждом документе в индексируемой
коллекции соответствует запись в индексе, даже если в документе нет
индексируемого поля. Разреженный индекс
(NoSQL*) — тот, в котором
представлены только те документы, для которых индексируемый ключ имеет какое-то
определённое значение (существует). Пространственный
индекс — оптимизирован для описания географического местоположения. Он представляет
из себя многоключевой индекс, состоящий из широты и долготы.
Составной
пространственный индекс — индекс,
включающий в себя кроме широты и долготы ещё какие-либо метаданные (например,
теги). Но географические координаты должны стоять на первом месте.
Полнотекстовый
(инвертированный) индекс — словарь, в
котором перечислены все слова и указано, в каких местах они встречаются. При
наличии такого индекса достаточно осуществить поиск нужных слов в нём и тогда
сразу же будет получен список документов, в которых они встречаются.
Хэш-индекс — предполагает хранение не самих значений, а их
хэшей, благодаря чему уменьшается размер(а, соответственно, и увеличивается
скорость их обработки) индексов из больших полей. Кроме того, так как хэши не
уникальны, то для совпадающих хэшей применяются методы разрешения коллизий.
Битовый
индекс (bitmap index) — метод битовых индексов заключается в создании
отдельных битовых карт (последовательность 0 и 1) для каждого возможного
значения столбца, где каждому биту соответствует строка с индексируемым
значением, а его значение равное 1 означает, что запись, соответствующая
позиции бита содержит индексируемое значение для данного столбца или свойства.
Обратный
индекс (reverse index) — это тоже B-tree индекс но с реверсированным
ключом, используемый в основном для монотонно возрастающих значений (например,
автоинкрементный идентификатор) в OLTP
системах с целью снятия конкуренции за последний листовой блок индекса, т.к.
благодаря переворачиванию значения две соседние записи индекса попадают в
разные блоки индекса. Он не может использоваться для диапазонного поиска.
Функциональный
(function-based) индекс (индекс по вычисляемому полю) — индекс, ключи которого хранят результат
пользовательских функций.
Первичный
индекс — уникальный индекс по полю
первичного ключа.
Вторичный
индекс — индекс по другим полям
(кроме поля первичного ключа).
XML-индекс — вырезанное материализованное представление больших
двоичных XML-объектов (BLOB) в столбце с типом данных xml.
Механизм
обновления характеризует то, как
обновляется индекс при изменении данных, над которыми он построен. Полностью перестраиваемый — при
добавлении элемента заново перестраивается весь индекс.Пополняемый (балансируемый) — при добавлении элементов индекс
перестраивается частично (например одна из ветви) и периодически балансируется.
Покрытие
индексируемого содержимого
характеризует меру покрытия данных, над которыми построен индекс. Полностью покрывающий (полный) индекс —
покрывает всё содержимое индексируемого объекта. Частичный (partial) индекс — это индекс, построенный на части
таблицы, удовлетворяющей определенному условию самого индекса. Данный индекс
создан для уменьшения размера индекса. Инкрементный
(Delta) индекс — индексируется малая часть данных (дельта), как правило, по
истечении определённого времени. Используется при интенсивной записи. Например,
полный индекс перестраивается раз в сутки, а дельта-индекс строится каждый час.
По сути это частичный индекс по временной метке. Real-time индекс — особый вид delta
индекса в системе индексирования Sphinx,
характеризующийся высокой скоростью построения. Он предназначен для
часто-меняющихся данных.
С точки зрения кластерных систем индексы бывают глобальные и сегментные. Глобальный индекс — индекс по всему
содержимому всех shard’ов (секций). Сегментный
индекс — глобальный индекс по полю-сегментируемому ключу (shard key). Используется для быстрого
определения сегмента(shard’а), на котором хранятся данные в процессе
маршрутизации запроса в кластере БД. Локальный
индекс - индекс по содержимому
только одного shard’а.
*NoSQL – индексы,
отмеченные этой пометкой на данный момент реализуются, в основном, в нереляционных СУБД.
Литература: