Индекс базы данных — это структура данных , которая повышает скорость операций по извлечению данных из таблицы базы данных за счет дополнительных записей и дискового пространства для поддержания структуры данных индекса. Индексы используются для быстрого поиска данных без необходимости выполнять поиск каждой строки в таблице базы данных каждый раз при доступе к ней. Индексы могут быть созданы с использованием одного или нескольких столбцов таблицы базы данных , обеспечивая основу как для быстрого случайного поиска , так и для эффективного доступа к упорядоченным записям.
Индекс — это копия выбранных столбцов данных из таблицы, которая разработана для обеспечения очень эффективного поиска. Индекс обычно включает «ключ» или прямую ссылку на исходную строку данных, из которой он был скопирован, чтобы обеспечить эффективное извлечение всей строки. Некоторые базы данных расширяют возможности индексирования, позволяя разработчикам создавать индексы по значениям столбцов, которые были преобразованы функциями или выражениями . Например, индекс может быть создан по 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 (с предикатом равенства) или более сложных ограничений, например, для обеспечения того, чтобы в таблице не хранились перекрывающиеся временные диапазоны или пересекающиеся геометрические объекты. Для контроля такого ограничения требуется индекс, поддерживающий быстрый поиск записей, удовлетворяющих предикату. [1]
Данные представлены в произвольном порядке, но логический порядок задается индексом. Строки данных могут быть распределены по всей таблице независимо от значения индексированного столбца или выражения. Некластеризованное дерево индекса содержит ключи индекса в отсортированном порядке, при этом уровень листьев индекса содержит указатель на запись (страница и номер строки на странице данных в организованных по страницам движках; смещение строки в организованных по файлам движках).
В некластеризованном индексе
В таблице базы данных может быть более одного некластеризованного индекса.
Кластеризация изменяет блок данных в определенный отдельный порядок, чтобы соответствовать индексу, в результате чего данные строк хранятся в порядке. Таким образом, для данной таблицы базы данных может быть создан только один кластеризованный индекс. Кластеризованные индексы могут значительно увеличить общую скорость поиска, но обычно только там, где доступ к данным осуществляется последовательно в том же или обратном порядке кластеризованного индекса или когда выбран диапазон элементов.
Поскольку физические записи находятся в этом порядке сортировки на диске, следующий элемент строки в последовательности находится непосредственно перед или после последнего, и поэтому требуется меньшее количество чтений блоков данных. Поэтому основной особенностью кластеризованного индекса является упорядочение строк физических данных в соответствии с индексными блоками, которые указывают на них. Некоторые базы данных разделяют блоки данных и индекса в отдельные файлы, другие помещают два совершенно разных блока данных в один и тот же физический файл(ы).
Когда объединяются несколько баз данных и несколько таблиц, это называется кластером (не путать с кластеризованным индексом, описанным ранее). Записи для таблиц, разделяющих значение ключа кластера, должны храниться вместе в тех же или соседних блоках данных. Это может улучшить объединения этих таблиц по ключу кластера, поскольку соответствующие записи хранятся вместе, и для их поиска требуется меньше операций ввода-вывода. [2] Конфигурация кластера определяет структуру данных в таблицах, которые являются частями кластера. Кластер может быть зашифрован с помощью индекса B-дерева или хэш-таблицы . Блок данных, в котором хранится запись таблицы, определяется значением ключа кластера.
Порядок, в котором определение индекса определяет столбцы, важен. Можно получить набор идентификаторов строк, используя только первый индексированный столбец. Однако невозможно или неэффективно (в большинстве баз данных) получить набор идентификаторов строк, используя только второй или более высокий индексированный столбец.
Например, в телефонной книге, организованной сначала по городу, затем по фамилии, а затем по имени, в определенном городе можно легко извлечь список всех телефонных номеров. Однако было бы очень утомительно искать все телефонные номера для определенной фамилии. Пришлось бы искать записи с этой фамилией в разделе каждого города. Некоторые базы данных могут это делать, другие просто не будут использовать индекс.
В примере телефонной книги с составным индексом, созданным по столбцам ( city, last_name, first_name), если мы ищем, указывая точные значения для всех трех полей, время поиска минимально, но если мы указываем значения только для cityи first_name, поиск использует только cityполе для извлечения всех соответствующих записей. Затем последовательный поиск проверяет соответствие с first_name. Таким образом, для повышения производительности необходимо гарантировать, что индекс создается в порядке столбцов поиска.
Индексы полезны для многих приложений, но имеют некоторые ограничения. Рассмотрим следующий оператор SQL : . Чтобы обработать этот оператор без индекса, программное обеспечение базы данных должно просмотреть столбец last_name в каждой строке таблицы (это известно как полное сканирование таблицы ). С индексом база данных просто следует структуре данных индекса (обычно B-дерево ), пока не будет найдена запись Smith; это намного менее затратно с точки зрения вычислений, чем полное сканирование таблицы.SELECT first_name FROM people WHERE last_name = 'Smith';
Рассмотрим этот оператор SQL: . Этот запрос выдаст адрес электронной почты для каждого клиента, адрес электронной почты которого заканчивается на "@wikipedia.org", но даже если столбец email_address был проиндексирован, база данных должна выполнить полное сканирование индекса. Это связано с тем, что индекс построен с предположением, что слова идут слева направо. С подстановочным знаком в начале поискового термина программное обеспечение базы данных не может использовать базовую структуру данных индекса (другими словами, предложение WHERE не является sargable ). Эту проблему можно решить путем добавления другого индекса, созданного на и SQL-запроса, такого как этот: . Это помещает подстановочный знак в самую правую часть запроса (теперьSELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';reverse(email_address)SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');gro.aidepikiw@%), которому может соответствовать индекс reverse(email_address).
Когда символы подстановки используются с обеих сторон поискового слова, как %wikipedia.org% , индекс, доступный в этом поле, не используется. Вместо этого выполняется только последовательный поиск, который занимает время.
Индекс битовой карты — это особый вид индексации, который хранит большую часть своих данных в виде битовых массивов (битовых карт) и отвечает на большинство запросов, выполняя побитовые логические операции над этими битовыми картами. Наиболее часто используемые индексы, такие как деревья B+ , наиболее эффективны, если индексируемые ими значения не повторяются или повторяются небольшое количество раз. Напротив, индекс битовой карты предназначен для случаев, когда значения переменной повторяются очень часто. Например, поле пола в базе данных клиентов обычно содержит не более трех различных значений: мужской, женский или неизвестный (не записано). Для таких переменных индекс битовой карты может иметь значительное преимущество в производительности по сравнению с обычно используемыми деревьями.
Плотный индекс в базах данных — это файл с парами ключей и указателей для каждой записи в файле данных. Каждый ключ в этом файле связан с определенным указателем на запись в отсортированном файле данных. В кластеризованных индексах с дублирующимися ключами плотный индекс указывает на первую запись с этим ключом. [3]
Разреженный индекс в базах данных — это файл с парами ключей и указателей для каждого блока в файле данных. Каждый ключ в этом файле связан с определенным указателем на блок в отсортированном файле данных. В кластеризованных индексах с дублирующимися ключами разреженный индекс указывает на самый низкий ключ поиска в каждом блоке.
Индекс с обратным ключом меняет значение ключа на противоположное перед его вводом в индекс. Например, значение 24538 становится 83542 в индексе. Изменение значения ключа на противоположное особенно полезно для индексации таких данных, как порядковые номера, где новые значения ключа монотонно увеличиваются.
Инвертированный индекс сопоставляет слово содержимого с содержащим его документом, тем самым позволяя выполнять полнотекстовый поиск.
Первичный индекс содержит ключевые поля таблицы и указатель на неключевые поля таблицы. Первичный индекс создается автоматически при создании таблицы в базе данных.
Он используется для индексации полей, которые не являются ни полями упорядочивания, ни ключевыми полями (нет гарантии, что файл организован по ключевому полю или полю первичного ключа). Одна запись индекса для каждого кортежа в файле данных (плотный индекс) содержит значение индексированного атрибута и указатель на блок или запись.
Хэш-индекс в базе данных — наиболее часто используемый индекс в управлении данными. Он создается на столбце, содержащем уникальные значения, такие как первичный ключ или адрес электронной почты.
Другим типом индекса, используемым в системах баз данных, является линейное хеширование .
Индексы могут быть реализованы с использованием различных структур данных. Популярные индексы включают сбалансированные деревья , деревья B+ и хэши . [4]
В Microsoft SQL Server конечный узел кластеризованного индекса соответствует фактическим данным, а не просто указателю на данные, которые находятся в другом месте, как в случае с некластеризованным индексом. [5] Каждое отношение может иметь один кластеризованный индекс и много некластеризованных индексов. [6]
Индекс обычно одновременно используется несколькими транзакциями и процессами, поэтому требуется управление параллелизмом . Хотя в принципе индексы могут использовать общие методы управления параллелизмом базы данных, существуют специализированные методы управления параллелизмом для индексов, которые применяются в сочетании с общими методами для существенного повышения производительности.
В большинстве случаев индекс используется для быстрого поиска записей данных, из которых считываются требуемые данные. Другими словами, индекс используется только для поиска записей данных в таблице, а не для возврата данных.
Покрывающий индекс — это особый случай, когда сам индекс содержит требуемые поля данных и может предоставить требуемые данные.
Рассмотрим следующую таблицу (остальные поля опущены):
Чтобы найти Имя для ID 13, индекс по (ID) полезен, но запись все равно должна быть прочитана, чтобы получить Имя. Однако индекс по (ID, Name) содержит требуемое поле данных и устраняет необходимость поиска записи.
Индексы покрытия предназначены для каждой конкретной таблицы. Запросы, которые JOIN/ обращаются к нескольким таблицам, могут потенциально рассматривать индексы покрытия для более чем одной из этих таблиц. [7]
Покрывающий индекс может значительно ускорить извлечение данных, но сам по себе может быть большим из-за дополнительных ключей, которые замедляют вставку и обновление данных. Чтобы уменьшить размер такого индекса, некоторые системы позволяют включать в индекс неключевые поля. Неключевые поля сами по себе не являются частью упорядочивания индекса, а включаются только на уровне листьев, что позволяет использовать покрывающий индекс с меньшим общим размером индекса.
Это можно сделать в SQL с помощью . [8] [9]CREATE INDEX my_index ON my_table (id) INCLUDE (name);
Ни один стандарт не определяет, как создавать индексы, поскольку стандарт ISO SQL не охватывает физические аспекты. Индексы являются одной из физических частей концепции базы данных среди других, таких как хранилище (табличное пространство или файловые группы). [ уточнить ] Все поставщики СУРБД предоставляют синтаксис с некоторыми конкретными опциями, которые зависят от возможностей их программного обеспечения.CREATE INDEX
{{cite book}}: |work=проигнорировано ( помощь )