Как оглавление в книге, индекс базы данных помогает ей быстро находить ссылки на некоторое значение или диапазон значений, которые требуется получить из таблицы. Например, индексирование Last Name в таблице Persons позволяет быстро обращаться к списку строк таблицы, для которых Last Nanie= SMITH или где Last Name>=X AND Last Nanie< Y. Но, в противоположность оглавлению книги, работа с индексами базы данных практически не требует никаких усилий со стороны приложения. База данных сама несет ответственность за прохождение индексов, которые выбирает для использования, и поиск строк, необходимых запросу. Причем база данных обычно сама без подсказки выбирает подходящие индексы. Однако базы данных не всегда делают правильный выбор, и материал этой книги во многом посвящен таким проблемам.

Для каждого индекса существует естественный порядок сортировки, обычно по возрастанию в соответствии с типом индексированного столбца. Например, число 11 лежит между 10 и 12, однако строка символов 1Г лежит между Г и 2. Часто индексы охватывают несколько столбцов, но вы можете считать, что для таких индексов существует единственный ключ сортировки, составленный путем конкатенации значений нескольких столбцов с соответствующим заполнением пробелами, разрешающим сортировку второго столбца только после завершения сортировки первого столбца.

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

ПРИМЕЧАНИЕ

Адрес блока и номер строки в блоке вместе называются идентификатором строки. Индексы указывают на строки в таблицах при помощи идентификаторов строки.

Будем считать, что в таблице больше 300 индексированных строк. Тогда база данных следует по указателю в корневом блоке и попадает в блок следующего уровня, который охватывает начало диапазона значений, необходимых для вашего запроса. Если же в таблице больше 90 ООО индексированных строк, то блок второго уровня, в свою очередь, содержит поддиапазоны с указателями на блоки на следующем уровне. В конце концов (на первом не корневом уровне, если в таблице 300-90 ООО индексированных строк) база данных придет в листовой блок, в котором содержатся точное значение, соответствующее началу требуемого диапазона (пред-

►

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

полагается, что запрошенный диапазон содержит хотя бы несколько строк), и идентификатор строки для первой строки диапазона.

Если условие, которое управляет доступом к индексу, потенциально указывает на диапазон, включающий несколько строк, база данных выполняет сканирование диапазона индексов в листовых блоках. Сканирование диапазона индексов - это операция считывания (обычно при помощи операций логического ввода-вывода из кэша) последовательности индексов из необходимого количества листовых блоков. Листовые блоки состоят из списка пар значение/идентификатор строки, отсортированного по индексированному значению. База данных сортирует записи с одинаковыми значениями согласно порядку идентификаторов строк, отражая естественный порядок, в котором база данных хранит строки в физической таблице. В конце каждого списка листового блока находится указатель на следующий листовой блок, где отсортированный список продолжается. Если в таблице есть несколько строк, удовлетворяющих условию для диапазона индекса, то база данных следует по указателю от первой строки на следующую запись индекса в диапазоне (в более чем 99 % случаев следующая запись индекса находится в том же листовом блоке индекса) и так далее, пока не достигнет конца диапазона. Таким образом, каждое считывание интервала отсортированных значений требует одного прохождения вниз по дереву индекса и одного прохождения по отсортированным значениям в листовых блоках.

ПРИМЕЧАНИЕ

Обычно сканирование диапазона затрагивает только один листовой блок, так как в одном листовом блоке хранится 300значений. Этого обычно достаточно для большинства операций сканирования среднего размера, чтобы не покинуть блок. Однако сканирование большого диапазона может потребовать перехода по длинному списку листовых блоков.

Если в блоке индекса содержится приблизительно 300 записей, то на первом некорневом уровне будет примерно 300 блоков. Это достаточно малое значение для успешного кэширования, поэтому вы можете предполагать, что считывание этих блоков индексов будет исключительно логическим, без выполнения операций физического ввода-вывода. На нижнем, листовом уровне индекса, если индекс состоит из трех и более уровней, может быть гораздо больше трехсот листовых блоков. Но если в базе данных используется действительно объемный индекс, то на листовом уровне индекса находится порядка п/300 блоков, где п - количество индексированных строк, а база данных может эффективно кэшировать 1 ООО или более блоков индекса.

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

Стоимость индекса

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

В идеальном мире затраты на производительность, происходящие от добавления индексов, возникают только при добавлении, удалении и обновлении строк. В спокойных таблицах стоимость индексов никогда не бывает проблемой, но в активных, растущих таблицах стоимость индексов может быть весьма высока. Обычно добавления в индекс проходят без проблем, особенно в СУБД Oracle, которая особенно элегантно обрабатывает блокировку блоков индексов для незавершенной работы.

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

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

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