Индекс базы данных - Database index
Индекс базы данных является структурой данных , которая повышает скорость извлечения данных операций на таблице базы данных за счет дополнительных операций записи и пространства для хранения , чтобы сохранить структуру данных индекса. Индексы используются для быстрого поиска данных без необходимости искать каждую строку в таблице базы данных при каждом доступе к таблице базы данных. Индексы могут быть созданы с использованием одного или нескольких столбцов таблицы базы данных , обеспечивая основу как для быстрого случайного поиска, так и для эффективного доступа к упорядоченным записям.
Индекс - это копия выбранных столбцов данных из таблицы, которая предназначена для обеспечения очень эффективного поиска. Индекс обычно включает «ключ» или прямую ссылку на исходную строку данных, из которой он был скопирован, чтобы обеспечить эффективное извлечение всей строки. Некоторые базы данных расширяют возможности индексирования, позволяя разработчикам создавать индексы для значений столбцов, преобразованных функциями или выражениями . Например, можно создать индекс 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-Tree или хеш-таблицей . Блок данных, в котором хранится запись таблицы, определяется значением ключа кластера.
Порядок столбцов
Порядок, в котором определение индекса определяет столбцы, важен. Можно получить набор идентификаторов строк, используя только первый индексированный столбец. Однако невозможно или неэффективно (в большинстве баз данных) получить набор идентификаторов строк, используя только второй или больший индексированный столбец.
Например, в телефонной книге, организованной сначала по городам, затем по фамилии, а затем по имени, в конкретном городе можно легко извлечь список всех телефонных номеров. Однако было бы очень утомительно найти все номера телефонов для определенной фамилии. Нужно будет искать в разделе каждого города записи с этой фамилией. Некоторые базы данных могут это делать, другие просто не используют индекс.
В примере телефонной книги с составным индексом, созданным для столбцов ( 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 | Предохранитель | ... |
Чтобы найти Имя для ID 13, полезен индекс по (ID), но запись все равно должна быть прочитана, чтобы получить Имя. Однако индекс на (ID, Name) содержит обязательное поле данных и избавляет от необходимости искать запись.
Каждый индекс покрытия предназначен для определенной таблицы. Запросы, которые JOIN / обращаются к нескольким таблицам, потенциально могут рассматривать возможность покрытия индексов более чем одной из этих таблиц.
Покрывающий индекс может значительно ускорить извлечение данных, но сам по себе может быть большим из-за дополнительных ключей, которые замедляют вставку и обновление данных. Чтобы уменьшить такой размер индекса, некоторые системы позволяют включать в индекс неключевые поля. Неключевые поля сами по себе не являются частью упорядочивания индекса, а включаются только на конечном уровне, что позволяет использовать покрывающий индекс с меньшим общим размером индекса.
Стандартизация
Ни один стандарт не определяет, как создавать индексы, потому что стандарт ISO SQL не охватывает физических аспектов. Индексы - это одна из физических частей концепции базы данных, например, хранилище (табличное пространство или файловые группы). Все поставщики СУБД предоставляют синтаксис CREATE INDEX с некоторыми конкретными параметрами, которые зависят от возможностей их программного обеспечения.