Типы индексов, виды индексов, или какие вообще бывают индексы?

После прочтения многочисленной литературы по СУБД, некоторого опыта работы с MongoDB и листанию статей по базам данных у меня созрело желание сделать cheatsheet по индексам применительно к БД. А индексирование – достаточно интересный раздел теории баз данных, а главное – нужный в практике. Вообще-то говоря, золотое правило индексирования – иметь индекс под каждый запрос.

По порядку сортировки

  • Упорядоченные  – индексы, в которых элементы поля(столбца) упорядочены.
    • Возрастающие
    • Убывающие
  • Неупорядоченные – индексы, в которых элементы неупорядочены.

По источнику данных

  • Индексы по представлению (view).
  • Индексы по выражениям – например в PostgreSQL.

По воздействию на источник данных

  • Некластерный индекс – наиболее типичные представители семейства индексов. В отличие от кластерных, они не перестраивают физическую структуру таблицы, а лишь организуют ссылки на соответствующие строки. Для идентификации нужной строки в таблице некластерный индекс организует специальные указатели, включающие в себя: информацию об идентификационном номере файла, в котором хранится строка; идентификационный номер страницы соответствующих данных; номер искомой строки на соответствующей странице; содержимое столбца.
  • Кластерный индекс – Принципиальным отличием кластерного индекса от индексов других типов является то, что при его определении в таблице физическое расположение данных перестраивается в соответствии со структурой индекса. Логическая структура таблицы в этом случае представляет собой скорее словарь, чем индекс. Данные в словаре физически упорядочены, например по алфавиту. Кластерные индексы могут дать существенное увеличение производительности поиска данных даже по сравнению с обычными индексами. Увеличение производительности особенно заметно при работе с последовательными данными.

По структуре

  • B*-деревья
  • B+-деревья
  • B-деревья
  • Хеши.

По количественному составу

  • Простой индекс (индекс с одним ключом) – строится по одному полю.
    Составной (многоключевой, композитный) индекс – строится по нескольким полям. Важен порядок следования полей (например в MongoDB).
    Индекс с включенными столбцами – Некластеризованный индекс, дополнительно содержащий кроме ключевых столбцов еще и неключевые.
  • Главный индекс (индекс по первичному ключу) – это тот индексный ключ, под управлением которого в данный момент находится таблица. Таблица не может быть отсортирована по нескольким индексным ключам одновременно. Хотя, если одна и та же таблица открыта одновременно в нескольких рабочих областях, то у каждой копии таблицы может быть назначен свой главный индекс.

По характеристике содержимого

  • Уникальный индекс – состоит из множества уникальных значений поля.
    Плотный индекс (NoSQL) – индекс, при котором, каждом документе в индексируемой коллекции соответствует запись в индексе, даже если в документе нет индексируемого поля.
  • Разреженный индекс (NoSQL) – тот, в котором представлены только те документы, для которых индексируемый ключ имеет какое-то определённое значение (существует).
  • Пространственный индекс – оптимизирован для описания географического местоположения. Представляет из себя многоключевой индекс состоящий из широты и долготы.
  • Составной пространственный индекс – индекс, включающий в себя кроме широты и долготы ещё какие-либо мета-данные (например теги). Но географические координаты должны стоять на первом месте.
  • Полнотекстовый (инвертированный) индекс – словарь, в котором перечислены все слова и указано, в каких местах они встречаются. При наличии такого индекса достаточно осуществить поиск нужных слов в нём и тогда сразу же будет получен список документов, в которых они встречаются.
  • Хэш-индексы – предполагают хранение не самих значений, а их хэшей, благодаря чему уменьшается размер(а, соответственно, и увеличивается скорость их обработки) индексов из больших полей. Таким образом, при запросах с использованием HASH-индексов, сравниваться будут не искомое со значения поля, а хэш от искомого значения с хэшами полей.
    Из-за нелинейнойсти хэш-функций данный индекс нельзя сортировать по значению, что приводит к невозможности использования в сравнениях больше/меньше и «is null». Кроме того, так как хэши не уникальны, то для совпадающих хэшей применяются методы разрешения коллизий.
  • Битовый индекс (bitmap index) – метод битовых индексов заключается в создании отдельных битовых карт (последовательность 0 и 1) для каждого возможного значения столбца, где каждому биту соответствует строка с индексируемым значением, а его значение равное 1 означает, что запись, соответствующая позиции бита содержит индексируемое значение для данного столбца или свойства.
  • Обратный индекс (reverse index) – это тоже B-tree индекс но с реверсированным ключом, используемый в основном для монотонно возрастающих значений(например, автоинкрементный идентификатор) в OLTP системах с целью снятия конкуренции за последний листовой блок индекса, т.к. благодаря переворачиванию значения две соседние записи индекса попадают в разные блоки индекса. Он не может использоваться для диапазонного поиска.
  • Функциональный (function-based) индекс (индекс по вычисляемому полю) – индекс, ключи которого хранят результат пользовательских функций. Функциональные индексы часто строятся для полей, значения которых проходят предварительную обработку перед сравнением в команде SQL. Например, при сравнении строковых данных без учета регистра символов часто используется функция UPPER. Создание функционального индекса с функцией UPPER улучшает эффективность таких сравнений. Кроме того, функциональный индекс может помочь реализовать любой другой отсутствующий тип индексов данной СУБД(кроме, пожалуй, битового индекса, например, Hash для Oracle)
  • Первичный индекс – уникальный индекс по полю первичного ключа.
  • Вторичный индекс – индекс по другим полям (кроме поля первичного ключа).
  • XML-индекс – вырезанное материализованное представление больших двоичных XML-объектов (BLOB) в столбце с типом данных xml.

По механизму обновления

  • Полностью перестраиваемый – при добавлении элемента заново перестраивается весь индекс.
  • Пополняемый (балансируемый) – при добавлении элементов индекс перестраивается частично (например одна из ветви) и периодически балансируется.

По покрытию индексируемого содержимого

  • Полностью покрывающий (полный) индекс – покрывает всё содержимое индексируемого объекта.
  • Частичный (partial) индекс – это индекс, построенный на части таблицы, удовлетворяющей определенному условию самого индекса. Данный индекс создан для уменьшения размера индекса.
  • Инкрементный (Delta) индекс – индексируется малая часть данных(дельта), как правило, по истечении определённого времени. Используется при интенсивной записи. Например, полный индекс перестраивается раз в сутки, а дельта-индекс строится каждый час. По сути это частичный индекс по временной метке.
  • Real-time индекс – особый вид delta индекса в Sphinx, характеризующийся высокой скоростью построения. Предназначен для часто-меняющихся данных.

Индексы в кластерных системах

  • Глобальный индекс – индекс по всему содержимому всех shard’ов (секций).
  • Сегментный индекс – глобальный индекс по полю-сегментируемому ключу (shard key). Используется для быстрого определения сегмента(shard’а), на котором хранятся данные в процессе маршрутизации запроса в кластере БД.
  • Локальный индекс –  индекс по содержимому только одного shard’а.

Если есть неточности, коррективы – пишите в комменты. Надеюсь кому-то будет полезным эта “шпаргалка”.

Ссылки

http://ru.wikipedia.org/wiki/Индекс_(базы_данных)
http://habrahabr.ru/post/102785/
http://www.sql.ru/articles/mssql/03013101indexes.shtml#16_3
http://msdn.microsoft.com/ru-ru/library/ms175049(v=sql.90).aspx

6 Comments

  1. Душевно изложили. Шпаргалка и впрямь интересна, а вот если снабдить каждую характеристику use case’ом, вообще цены бы не было 🙂

    1. Спасибо, Алекс. Чего-то вот ночью гуглил-гуглил, и решил разрозненные сведения в одно место собрать. А насчёт use-case так это к каждому отдельно не сделаешь, надо по ситуации смотреть 🙂

  2. А в чем разница между индексом по вычисляему полю и функциональным?

Leave a Comment