Индекс базы данных

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

Индекс — это копия выбранных столбцов данных из таблицы, предназначенная для обеспечения очень эффективного поиска. Индекс обычно включает в себя «ключ» или прямую ссылку на исходную строку данных, из которой он был скопирован, чтобы обеспечить эффективное извлечение всей строки. Некоторые базы данных расширяют возможности индексирования, позволяя разработчикам создавать индексы для значений столбцов, преобразованных с помощью функций или выражений . Например, индекс может быть создан на upper(last_name), который будет хранить только версии в верхнем регистре last_name поле в индексе. Другой вариант, который иногда поддерживается, — это использование частичного индекса , при котором записи индекса создаются только для тех записей, которые удовлетворяют некоторому условному выражению. Еще одним аспектом гибкости является возможность индексации пользовательских функций , а также выражений, сформированных из набора встроенных функций.

Использование

Поддержка быстрого поиска

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

Предположим, что база данных содержит N элементов данных, и один из них необходимо получить на основе значения одного из полей. Простая реализация извлекает и проверяет каждый элемент в соответствии с тестом. Если есть только один совпадающий элемент, процесс может остановиться, когда он найдет этот единственный элемент, но если совпадений несколько, он должен проверить все. Это значит, что количество операций в среднем случае равно O (N) или линейному времени . Поскольку базы данных могут содержать множество объектов и поскольку поиск является распространенной операцией, часто желательно повысить производительность.

Индекс — это любая структура данных, которая повышает производительность поиска. множество различных структур данных Для этой цели используется . Существуют сложные компромиссы при проектировании, включающие производительность поиска, размер индекса и производительность обновления индекса. Многие конструкции индексов демонстрируют логарифмическую ( O (log(N))) производительность поиска, а в некоторых приложениях можно добиться ровной ( O (1)) производительности.

Контроль ограничений базы данных

Индексы используются для контроля ограничений базы данных , таких как UNIQUE, EXCLUSION, PRIMARY KEY и FOREIGN KEY . Индекс может быть объявлен как UNIQUE, что создает неявное ограничение для базовой таблицы. Системы баз данных обычно неявно создают индекс для набора столбцов, объявленных PRIMARY KEY, а некоторые способны использовать уже существующий индекс для контроля этого ограничения. Многие системы баз данных требуют, чтобы как ссылающиеся, так и ссылающиеся наборы столбцов в ограничении FOREIGN KEY были проиндексированы, что повышает производительность вставок, обновлений и удалений таблиц, участвующих в ограничении.

Некоторые системы баз данных поддерживают ограничение EXCLUSION, которое гарантирует, что для вновь вставленной или обновленной записи определенный предикат не применяется ни к какой другой записи. Это можно использовать для реализации ограничения UNIQUE (с предикатом равенства) или более сложных ограничений, например, для обеспечения того, чтобы в таблице не хранились перекрывающиеся временные диапазоны или пересекающиеся геометрические объекты. Для обеспечения соблюдения такого ограничения необходим индекс, поддерживающий быстрый поиск записей, удовлетворяющих предикату.

Архитектура индекса и методы индексирования

Некластеризованный

Данные представлены в произвольном порядке, но логический порядок определяется индексом. Строки данных могут быть распределены по всей таблице независимо от значения индексированного столбца или выражения. Некластеризованное индексное дерево содержит ключи индекса в отсортированном порядке, причем конечный уровень индекса содержит указатель на запись (страницу и номер строки на странице данных в механизмах со страничной организацией; смещение строки в механизмах с файловой организацией). ).

В некластеризованном индексе

• Физический порядок строк не совпадает с порядком индекса.
• Индексированные столбцы обычно не являются столбцами первичного ключа, используемыми в предложениях JOIN, WHERE и ORDER BY.

В таблице базы данных может быть более одного некластеризованного индекса.

Кластеризованный

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

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

Кластер

Когда объединяются несколько баз данных и несколько таблиц, это называется кластером (не путать с кластерным индексом, описанным ранее). Записи таблиц, разделяющих значение ключа кластера, должны храниться вместе в одних и тех же или соседних блоках данных. Это может улучшить объединение этих таблиц по ключу кластера, поскольку совпадающие записи хранятся вместе, и для их обнаружения требуется меньше операций ввода-вывода. Конфигурация кластера определяет расположение данных в таблицах, являющихся частью кластера. Кластер может быть связан с индексом B-дерева или хэш-таблицей . Блок данных, в котором хранится запись таблицы, определяется значением ключа кластера.

Порядок столбцов

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

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

В примере телефонной книги с составным индексом, созданным по столбцам ( city, last_name, first_name), если мы выполняем поиск, задавая точные значения для всех трех полей, время поиска минимально, но если мы предоставим значения для city и first_name только, поиск использует только city поле для получения всех совпадающих записей. Затем последовательный поиск проверяет соответствие с помощью first_name. Итак, чтобы повысить производительность, необходимо обеспечить, чтобы индекс создавался в том же порядке, что и столбцы поиска.

Приложения и ограничения

Индексы полезны для многих приложений, но имеют некоторые ограничения. Рассмотрим следующий оператор SQL : SELECT first_name FROM people WHERE last_name = 'Smith';. Чтобы обработать этот оператор без индекса, программное обеспечение базы данных должно просмотреть столбец Last_name в каждой строке таблицы (это называется полным сканированием таблицы ). При использовании индекса база данных просто следует структуре данных индекса (обычно B-дереву ), пока не будет найдена запись Смита; это гораздо менее затратно в вычислительном отношении, чем полное сканирование таблицы.

Рассмотрим этот оператор SQL: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. Этот запрос даст адрес электронной почты для каждого клиента, адрес электронной почты которого заканчивается на «@wikipedia.org», но даже если столбец email_address был проиндексирован, база данных должна выполнить полное сканирование индекса. Это связано с тем, что индекс построен с учетом предположения, что слова идут слева направо. При использовании подстановочного знака в начале поискового запроса программное обеспечение базы данных не может использовать базовую структуру данных индекса (другими словами, предложение WHERE не может быть записано ). Эту проблему можно решить путем добавления еще одного индекса, созданного на reverse(email_address) и такой SQL-запрос: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. Это поместит подстановочный знак в самую правую часть запроса (теперь gro.aidepikiw@% ), чему может соответствовать индекс на реверсе (email_address).

Когда подстановочные знаки используются с обеих сторон искомого слова как %wikipedia.org% , индекс, доступный в этом поле, не используется. Вместо этого выполняется только последовательный поиск, который занимает ⁠ $O(N)$⁠ время.

Типы индексов

Индекс растрового изображения

Основная статья: Индекс растрового изображения

Индекс растрового изображения — это особый вид индексации, при котором основная часть данных хранится в виде битовых массивов (растровых изображений) и отвечает на большинство запросов, выполняя побитовые логические операции над этими растровыми изображениями. Наиболее часто используемые индексы, такие как деревья B+ , наиболее эффективны, если индексируемые ими значения не повторяются или повторяются небольшое количество раз. Напротив, индекс растрового изображения предназначен для случаев, когда значения переменной повторяются очень часто. Например, поле пола в базе данных клиентов обычно содержит не более трех различных значений: мужской, женский или неизвестный (не записанный). Для таких переменных индекс растрового изображения может иметь значительное преимущество в производительности по сравнению с обычно используемыми деревьями.

Плотный индекс

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

Разреженный индекс

Разреженный индекс в базах данных представляет собой файл с парами ключей и указателей для каждого блока в файле данных. Каждый ключ в этом файле связан с определенным указателем на блок в файле отсортированных данных. В кластерных индексах с повторяющимися ключами разреженный индекс указывает на наименьший ключ поиска в каждом блоке.

Обратный индекс

Основная статья: Обратный индекс

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

Инвертированный индекс

Основная статья: Инвертированный индекс

Инвертированный индекс сопоставляет слово содержимого с содержащим его документом, тем самым позволяя выполнять полнотекстовый поиск.

Первичный индекс

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

Вторичный индекс

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

Хэш-индекс

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

Линейное хеширование

Другой тип индекса, используемый в системах баз данных, — линейное хеширование .

Реализации индексов

Индексы могут быть реализованы с использованием различных структур данных. Популярные индексы включают сбалансированные деревья , деревья B+ и хеши .

В Microsoft SQL Server конечный узел кластеризованного индекса соответствует фактическим данным, а не просто указателю на данные, которые находятся в другом месте, как в случае с некластеризованным индексом. Каждое отношение может иметь один кластеризованный индекс и множество некластеризованных индексов.

Управление параллелизмом индексов

Основная статья: Блокировка индекса

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

Индекс покрытия

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

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

Рассмотрим следующую таблицу (остальные поля опущены):

ИДЕНТИФИКАТОР	Имя	Другие поля
12	Затыкать	...
13	Лампа	...
14	Предохранитель	...

Чтобы найти имя для идентификатора 13, полезен индекс (ID), но запись все равно необходимо прочитать, чтобы получить имя. Однако индекс (ID, Имя) содержит необходимое поле данных и устраняет необходимость поиска записи.

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

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

Это можно сделать в SQL с помощью CREATE INDEX my_index ON my_table (id) INCLUDE (name);.

Стандартизация

Ни один стандарт не определяет, как создавать индексы, поскольку стандарт ISO SQL не охватывает физические аспекты. Индексы являются одной из физических частей концепции базы данных, среди прочего, таких как хранилище (табличное пространство или файловые группы). Все поставщики РСУБД дают CREATE INDEX синтаксис с некоторыми конкретными параметрами, которые зависят от возможностей их программного обеспечения.

См. также

• Блокировка индекса
• Инвертированный индекс — тип индекса базы данных.
• Индексирование поисковыми системами – метод управления данными