Материал: Методические указания к лабораторным работам № 6–9 по дисциплинам «Основы построения защищенных СУБД», «Безопасность систем баз данных». Плотников Д.Г
В MSSQL данные и индексы таблиц хранятся в виде страниц, формат которых показан на рис. 4:
Рис. 4. Формат страницы данных SQL Server
Каждая страница размером 8192 байт включает заголовок, имеющий длину 96 байт. Еще один фрагмент страницы используется для размещения других структур данных, например, информации о переполнении строк. Вся оставшаяся часть страницы (8060 байт) предназначена для размещения данных (т.е. информации таблицы или индекса).
Предположим, что таблица "Состав щколы" содержит и другую информацию, например домашний адрес работника, номер телефона и т.д. Размер одной строки данных таблицы "Состав щколы" в этом случае может составлять приблизительно 2000 байт, тогда как ширина столбца "Должность" составляет 25 байт. Учитывая приведенные значения, разместим показанную на рис. 2 таблицу и показанный на рис. 3 индекс на страницах SQL Server, формат которых представлен на рис. 4. Данное размещение показано на рис. 5:
44
Рис. 5. Страницы данных таблицы «Состав школы» и ее индекса в базе данных SQL Server
45
Исходя из представленной на рис. 5 схемы рассмотрим, как в SQL Server будет выполняться поиск (без использования индекса) всех работников школы, занимающих должность «Заместитель директора». Прежде всего, будет считана страница с номером пять и ее данные будут просмотрены в поисках записей о нужных работниках. На первой странице (номер пять) такие записи найдены не будут. SQL Server считает следующую страницу (номер десять), просмотрит ее содержимое и выведет информацию из четвертой записи. Поскольку системе неизвестно, в скольких записях столбца «Должность» таблицы содержится значение «Заместитель директора», будет считана и просмотрена еще одна, последняя, страница таблицы с номером двенадцать. Итак, SQL Server выполнил полное сканирование таблицы, прочитав все записи с ее данными - в этом примере считывается всего три страницы данных. Ну, а если бы таблица «Состав школы» содержала бы в тысячу раз больше записей - около 9000 (что совсем не много для SQL Server)? Тогда для выборки необходимых данных пришлось бы считать 3000 страниц, причем даже в том случае, если бы в ней существовала только одна удовлетворяющая условию запись.
Рассмотрим, как будет выполняться тот же запрос с использованием индекса. Прежде всего, SQL Server считает страницу с данными индекса и промотрит ее содержимое в поисках значения «Заместитель директора». Искомое значение содержится в третьей строке. Из этой строки выбирается значение указателя, показывающее, что соответствующая запись является четвертой на странице номер десять. SQL Server считывает десятую страницу, выбирает четвертую строку и отображает найденное значение имени. Номер строки на странице сокращенно обозначается RID (Row Identifier). Затем проверяется значение в следующей строке индекса. Поскольку значение в ней отличается от искомого, SQL Server заканчивает обработку запроса. Таким образом, в данном случае для выполнения запроса потребовалось считать только две страницы, а не три, как в случае сканирования таблицы.
46
А что можно сказать о выполнении обсуждавшегося выше запроса об именах техников? Сканирование таблицы предусматривает чтение всех трех страниц данных. Использование же индекса потребует от SQL Server считать все три страницы данных, плюс еще одну страницу индекса. В итоге считанных страниц получится даже больше, чем при обычном сканировании! В некоторых случаях сканирование таблицы может оказаться эффективнее по сравнению с примененим для поиска индекса. Принятие решения о выборе используемого при поиске индекса или применении метода сканирования в SQL Server возлагается на службу оптимимзации запросов.
Структура индексов в Microsoft SQL Server
Для представления индексов в SQL Server используется схема двоичного дерева, показанная на рис. 5. Двоичные деревья представляют собой многоуровневые динамические поддерживаемые структуры.
47
Рис. 6. Схема построения двоичного дерева
48