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

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

Индекс - это копия выбранных столбцов данных из таблицы, называемая ключом базы данных или просто ключом, который можно очень эффективно искать, который также включает низкоуровневый адрес блока диска или прямую ссылку на полную строку данных, с которых данные индекса были скопированы. Некоторые базы данных расширяют возможности индексации, позволяя разработчикам создавать индексы для функций или выражений. Например, индекс может быть создан для 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 ограничения (с предикатом равенства) или более сложных ограничений, таких как обеспечение того, что в таблице не будут храниться перекрывающиеся временные диапазоны или пересекающиеся геометрические объекты. Индекс, поддерживающий быстрый поиск записей, удовлетворяющих предикату, необходим для контролирования такого ограничения.