Индекс базы данных: методы индексирования, приложения и ограничения

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

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

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

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

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

Рассмотрим следующий SQL запрос:

SELECT email_address FROM customers 
WHERE email_address LIKE '%@example.com';

Этот запрос даст адрес электронной почты для каждого клиента, чей адрес электронной почты оканчивается на "@example.com", но даже если столбец email_address был проиндексирован, база данных должна выполнить полное сканирование индекса. Это потому, что индекс строится с предположением, что слова идут слева направо. С подстановочным знаком в начале поискового термина программное обеспечение базы данных не может использовать базовую структуру данных B-дерева (другими словами, предложение WHERE не может быть sargable). Эта проблема может быть решена путем добавления другого индекса, созданного на reverse(email_address), и SQL-запроса, подобного следующему:

SELECT email_address FROM customers 
WHERE reverse(email_address) LIKE reverse('%@example.com');

Это ставит подстановочный знак в самой правой части запроса (теперь moc.elpmaxe@%), что может удовлетворить индекс на reverse(email_address).

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


Читайте также:


Комментарии

Популярные сообщения из этого блога

Язык поисковых запросов в Graylog

Хэш-таблица: разрешение коллизий

Нормальные формы, пример нормализации в базе данных