Руководство по созданию эффективных запросов

и
ндексные
 
структуры
Этот раздел начинается с абстрактного определения того, какую структу-
ру хранения можно назвать индексом; кратко рассматриваются наиболее 
распространенные индексные структуры, такие как деревья и хеш-индексы, 
и затрагиваются некоторые особенности PostgreSQL.
Мы покажем, как оценить масштаб улучшений для разных типов индексов 
и как распознать случаи, когда использование индекса не дает никаких пре-
имуществ в смысле производительности.
Что такое индекс?
Можно предположить, что любой человек, работающий с базами данных, 
знает, что такое индекс. Увы, удивительно много людей – разработчиков баз 
данных и составителей отчетов, а в некоторых случаях даже администра-
торов баз данных – используют индексы и даже создают их, лишь поверх-
ностно представляя, что это за объекты и какова их структура. Во избежание 
недоразумений мы начнем с определения того, что мы подразумеваем под 
индексом.

---

Индексные структуры 

47
Существует множество типов индексов, поэтому мы ориентируемся не на структурные 
свойства, а определяем индекс по способу его использования. Структура данных назы-
вается индексом, если:
• это избыточная структура данных;
• она невидима для приложения;
• она предназначена для ускорения выбора данных по определенным критериям.
Избыточность означает, что индекс можно удалить без потери данных 
и восстановить по информации, хранящейся где-то еще (конечно, в табли-
цах). Невидимость означает, что приложение не может узнать о наличии ин-
декса или о его отсутствии. Иначе говоря, любой запрос дает те же результаты 
как с индексом, так и без него. И наконец, индекс создается в надежде (или 
с уверенностью), что это улучшит производительность конкретного запроса 
или (что еще лучше!) нескольких запросов.
Улучшение производительности не происходит бесплатно. Поскольку 
индекс избыточен, он должен обновляться при обновлении данных таб-
лицы. Это приводит к накладным расходам для операций обновления, 
которыми иногда нельзя пренебречь. В частности, индексы PostgreSQL 
могут оказывать большое влияние на операцию очистки (
VACUUM
). Однако 
многие учебники по базам данных переоценивают эти расходы. Совре-
менные высокопроизводительные СУБД используют алгоритмы, которые 
снижают стоимость обновлений индексов, поэтому несколько индексов 
в таблице – обычное дело.
Хотя индексные структуры могут значительно различаться для разных ти-
пов индексов, ускорение всегда достигается за счет быстрой проверки неко-
торых условий фильтрации, указанных в запросе. Такие условия фильтрации 
устанавливают определенные ограничения на атрибуты таблицы. На рис. 3.5 
показана структура наиболее распространенных индексов.
В правой части рисунка показана таблица, а в левой – индекс, который 
можно рассматривать как особый вид таблицы. Каждая строка индекса со-
стоит из индексного ключа и указателя на строку таблицы. Значение ключа 
обычно совпадает со значением атрибута таблицы. В примере на рис. 3.5 
в качестве значения используется код аэропорта; следовательно, данный 
индекс поддерживает поиск по коду аэропорта.
У столбца может быть одно и то же значение в нескольких строках табли-
цы. Если этот столбец индексирован, индекс должен содержать указатели на 
все строки, содержащие это значение индексного ключа. В PostgreSQL индекс 
содержит несколько записей, то есть ключ индекса повторяется для каждого 
указателя на строку таблицы.
Рисунок 3.5 объясняет, как добраться до соответствующей строки таблицы 
при обнаружении записи индекса; однако он не объясняет, почему строку 
индекса можно найти намного быстрее, чем строку таблицы. Действительно, 
это зависит от того, как структурирован индекс, и именно это мы обсуждаем 
в следующих подразделах.

---