Для рассматриваемых в настоящем учебном пособии вопросов оптимизации запросов и использования транзакций необходимо остановиться на следующих моментах.
Страницы данных и индексов являются физической частью базы данных, где сохраняются соответствующие таблицы и индексы.
Содержимое базы данных хранится в одном файле или в нескольких файлах, каждый файл разделен на страницы. Поэтому каждая страница таблицы или индекса (как физическая единица базы данных) может быть уникально определена с использованием идентификатора базы данных, идентификатора файла и номера страницы.
При создании таблицы или индекса система выделяет фиксированный объем внешней памяти для хранения данных таблицы или индекса. Когда это пространство заполняется, то должна быть выделена дополнительная память.
Основной единицей хранения данных является страница.
Database Engine поддерживает различные типы страниц, наиболее важные из них:

• страницы данных;
• индексные страницы.

Страницы данных содержат строки данных всех типов данных, кроме данных типа text, ntext, image, nvarchar(max), varchar(max) и varbinary(max). Индексные страницы содержат записи индекса.
Место на диске, предоставляемое для размещения файла данных (MDF- или NDF-файл) в базе данных, логически разделяется на страницы с непрерывным перечислением от 0 до п.
Страницы файлов данных SQL Server нумеруются последовательно; первая страница файла получает нулевой номер (0). Каждый файл базы данных имеет уникальный цифровой идентификатор. Чтобы уникальным образом определить страницу базы данных, необходимо использовать как идентификатор файла, так и номер этой страницы.
На рисунке 2.1 показаны номера страниц базы данных, содержащей первичный файл данных.

Дисковые операции ввода-вывода выполняются на уровне страницы, т.е. SQL Server считывает или записывает целые страницы данных.
Таблицы и индексы хранятся в виде коллекции страниц размером 8 Кбайт. Это значит, что в одном мегабайте базы данных SQL Server содержится 128 страниц.
Структура страницы показана на рисунке 2.2.

Каждая страница начинается с 96-байтового заголовка, используемого для хранения системной информации - идентификатор страницы, идентификатор объекта базы данных, которому принадлежит страница, ссылки на предыдущую и последующую страницу в цепочке страниц, тип страницы, объем свободного места на странице, для индексных страниц уровень страницы (уровень листьев является уровнем О, первый промежуточный уровень является уровнем 1 и т. д.) и др.
Строки данных заносятся на страницу последовательно, сразу же после заголовка. Каждая новая строка сохраняется после уже сохраненных строк, пока страница не будет заполнена. Если на странице нет достаточного места для размещения новой строки той же таблицы, строка сохраняется на следующей странице в цепочке страниц.
Для всех таблиц, которые имеют только столбцы фиксированной длины, одно и то же количество строк хранится на каждой странице.
Если же таблица имеет хотя бы один столбец переменной длины (например, столбец VARCHAR), то количество строк на страницах может отличаться, и система помещает на страницу столько строк, сколько эта страница может вместить.
Таблицы SQL Server используют один из двух методов организации страниц данных:

• Кучи - это таблицы, которые не имеют кластеризованного индекса;
• Кластеризованные таблицы - это таблицы, имеющие кластеризованный индекс.

Все индексы имеют одинаковую, рассмотренную выше B-tree структуру.
Рассмотрим организацию кучи и кластеризованной таблицы и алгоритмы работы с ними в операциях обработки данных.
В таблицах, которые не имеют кластеризованного индекса (Куча, heap), строки данных хранятся без определенного порядка (не отсортированы), и какой-либо порядок в последовательности страниц данных отсутствует. Страницы данных не образуют связный список.
На рисунке 2.3 показана таблица данных, организованная в виде кучи (используется таблица Customers из базы данных Northwind, входящей в поставку СУБД MS SQL Server [ 11J). Для упрощения на рисунке приведено только ключевое поле (Фамилия), со значениями ROMEY, MORGK и т.д. Записи не упорядочены. Страницы данных имеют последовательные номера 10, 11, 12, 13, 14.
При отсутствии индекса, чтобы найти искомые записи, SQL Server последовательно читает (сканирует) всю таблицу. Например, для поиска записи, удовлетворяющей условию CustomerlD = ‘ВОТТМ’ SQL Server прочитает все записи, начиная с первой и заканчивая последней, и выберет те, которые будут удовлетворять указанному условию (на странице 13, первая строка).

Для такой таблицы может быть построен индекс в виде В-tree структуры (рисунок 2.4). Файл индексов хранится отдельно (страницы файла индекса имеют номера 30, 20, 21, 22, 23. Таблицы индексов одного уровня дерева имеют последовательные номера 20, 21, 22, 23. Эти же таблицы являются листьями дерева индекса. Записи файла упорядочены по ключу.
Корневой узел содержит строки индекса - значение ключа и указатель на индексную страницу следующего уровня (например, ANATR и 1:20, где ANATR -значение ключа первой записи страницы индекса, 1 -номер файла индекса, 20 - номер страницы файла индекса.
Лист дерева содержит строки индекса - значение ключа и указатель на соответствующую запись в файле данных, содержащий номер файла, номер страницы данных и номер записи на странице (например, ANTON и 1:11:1, где ANTON - значение ключа, 1 - номер файла данных, 11 - номер страницы данных, 1 - номер записи на странице). По этой информации осуществляется прямой доступ к соответствующей записи таблицы данных.
Теперь, для поиска записи, удовлетворяющей условию CustomerlD = ‘ROMEY’ SQL Server прочитает страницу корневого узла индекса, перейдет на страницу 22, выберет на ней запись по условию CustomerlD = ‘ROMEY’, по адресу 1:10:1 выберет первую строку в первом файле данных на десятой странице.
Как указывалось ранее, индексы в SQL Server представляют собой сбалансированные деревья. Это означает, что длины веток для всех ответвлений индекса, одинаковы. Если идти по дереву индекса на рисунке 8 сверху вниз, то нужно просканировать только три страницы (две страницы индекса и одну страницу данных), чтобы найти удовлетворяющую условию строку. Без дерева индексов нужно было бы просканировать пять страниц.
Каждая строка некластеризованного индекса на уровне листьев содержит ключевое значение и указатель на строку на странице данных файла данных, содержащей соответствующее ключевое значение.
Можно создать несколько некластеризованных индексов на одну таблицу (например, в SQL-сервер можно создать 249 некластеризованных индексов).
Следует обратить внимание, что из-за приведенного выше свойства фиксированного размера страниц вытекает, что количество строк в узле-листе некластеризованного индекса зависит от размера индексных записей.

Кластеризованный или кластерый индекс означает индекс, объединенный с данными (индекс представляет собой часть таблицы данных). Для кластерного индекса уровень листьев этого индекса есть сами страницы таблицы с данными. На рисунке 2.5 показан кластерный индекс, созданный для тех же самых данных рассмотренного примера.

Для кластерного индекса уровень листьев этого индекса есть сами страницы таблицы с данными. Эти данные являются упорядоченными (на рисунке 8 данные на странице таблицы данных не были упорядочены). Строки данных хранятся по порядку ключа кластеризованного индекса.
При создании первичного ключа таблицы данных в MS SQL Server автоматически создается кластеризованный индекс для этого ключа.
Страницы в каждом уровне индекса, включая страницы данных на конечном уровне, связаны в двунаправленый список, обеспечивающий эффективные алгоритмы работы с деревом индекса.
Из принципа организации кластерного индекса вытекает важное следствие. Поскольку сами данные таблицы являются частью индекса, то очевидно, что для таблицы может быть создан только один кластерный индекс. Кроме того, кластерный индекс является уникальным индексом по определению. Это означает, что все ключи записей должны быть уникальные. Если существуют записи с одинаковыми значениями, то, например, в MS SQL Server они делаются уникальными добавлением номера из внутреннего (невидимого снаружи) счетчика.
Таким образом, есть только два способа найти необходимую запись: по указателю на строку на странице данных (row ID, когда нет кластерного индекса) или по ключу кластерного индекса в противном случае.
Как было сказано выше, для таблицы может быть создано несколько некластеризованных индексов. Если таблица не имеет кластеризованного индекса, то каждая строка некластеризованного индекса на уровне листьев содержит ключевое значение и указатель на строку на странице данных файла данных, содержащей соответствующее ключевое значение
Если по таблице создан кластеризованный индекс, то некластери- зованные индексы будут содержать в узле-листе значение ключа кластеризованного индекса для этих данных (рисунок 2.6). Указатель ссылается не на физическое положение строки в базе данных, а на соответствующий элемент кластерного индекса, описывающего эту строку.

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

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

• поиск страницы данных, где должна располагаться добавляемая запись с заданным значением ключа;
• если на найденной странице есть «пустая» запись, добавляемая запись заносится на эту страницу (с необходимым переупорядочением записей внутри страницы);
• если на найденной странице нет пустого места, страница делится на две. Часть записей (обычно равняется половине записей, которые могут быть размещены на странице фиксированной длины) размещается на первой, во вторую заносятся остальные (значением ключа каждой из страниц будет являться минимальное значение ключей у записей на этой странице);
• добавляемая запись заносится на соответствующую страницу;
• появление нового блока с новым значением ключа обуславливает необходимость формирования соответствующей новой записи в индексе на предыдущем уровне. Эта запись содержит новое значение ключа новой страницы и указатель на её месторасположение;
• процедура добавления такой записи аналогична указанной в первых пунктах алгоритма (находится страница предыдущего уровня, куда должна быть помещена эта запись. Если на странице есть пустое место, запись добавляется на эту страницу, если страница заполнена, то она делится на две, запись заносится на одну из страниц, формируется запись индекса предыдущего уровня и т.д.).
• возможен вариант, когда придется делить страницу самого верхнего уровня и формировать еще один уровень дерева.

Проанализировав алгоритм, можно сделать вывод, что при наличии свободного места на страницах дерева индекса преобразование проходит быстрее (новые записи добавляются на страницы без необходимости их разделения и последующего преобразования верхних уровней индекса). Однако, при одном и том же объеме данных и фиксированном размере страниц, увеличивается количество страниц данных и количество уровней дерева индекса.
Количество уровней дерева индекса, в свою очередь, увеличивает количество обращений к индексному файлу (равно количеству уровней дерева индекса, см. выше) и соответственно время доступа к данным. Необходим выбор компромиссного решения при организации конкретного файла дерева индексов таблицы базы данных. Это решается при создании индексов для таблиц данных путем задания соответствующих параметров в SQL Server, которые будут рассмотрены далее.