Мастерство индексации в MS SQL Server: от архитектуры B-дерева до эмпирической оптимизации

Архитектура хранения данных на страницах и фундаментальное устройство B-дерева

Когда вы отправляете запрос к базе данных на поиск одной строки среди ста миллионов записей, SQL Server не сканирует жесткий диск байт за байтом. Физическое хранение данных и алгоритмы доступа к ним жестко структурированы. Разница между запросом, который выполняется за 2 миллисекунды, и запросом, который «вешает» сервер на 5 минут, кроется в том, сколько минимальных блоков данных движку базы данных пришлось прочитать с диска в оперативную память. Чтобы оптимизировать запросы, не имея доступа к планам выполнения, необходимо научиться мыслить этими блоками и понимать физику перемещения данных.

Анатомия хранения: страницы и экстенты

Фундаментальной единицей хранения данных в MS SQL Server является страница (Page). Независимо от того, храните ли вы числа, текст или даты, все они упаковываются в блоки фиксированного размера — ровно 8 КБ (8192 байта). SQL Server выполняет операции ввода-вывода (I/O) исключительно на уровне страниц. Невозможно прочитать или записать половину страницы или одну конкретную строку; движок всегда считывает в память всю 8-килобайтную страницу целиком.

Физическая структура страницы строго регламентирована и состоит из трех основных компонентов:

Заголовок страницы (Page Header). Занимает первые 96 байт. Здесь хранится системная информация: номер страницы, тип страницы (данные, индекс, системная карта), объем свободного места и указатели на предыдущую и следующую страницы (если страница является частью связанного списка).

Область данных (Data Rows). Сразу после заголовка последовательно записываются сами строки с данными.

Таблица смещений строк (Row Offset Table). Располагается в самом конце страницы и растет в обратном направлении — навстречу строкам данных. Это массив двухбайтовых указателей. Каждый элемент этого массива хранит смещение (в байтах) от начала страницы до конкретной строки.

!Структура страницы данных SQL Server

Таблица смещений критически важна для работы с колонками переменной длины (например, VARCHAR). Если строка удаляется, на странице образуется пустое пространство, но SQL Server не сдвигает все оставшиеся строки физически, чтобы закрыть «дыру» — это было бы слишком дорогой операцией. Вместо этого обновляется только таблица смещений. Когда движку нужна строка номер 3, он обращается к третьему слоту с конца страницы, читает смещение (например, 450 байт) и мгновенно прыгает на 450-й байт от начала страницы.

Поскольку заголовок занимает 96 байт, для самих данных и таблицы смещений остается байт. Из-за служебных накладных расходов на каждую строку, практически доступный максимум для данных составляет 8060 байт. Это объясняет известное ограничение SQL Server: сумма длин всех колонок фиксированной длины в таблице не должна превышать 8060 байт.

Для эффективного управления памятью страницы объединяются в более крупные структуры — экстенты (Extents). Экстент состоит из 8 физически непрерывных страниц, образуя блок размером 64 КБ. Выделение места на диске для новых данных происходит именно на уровне экстентов.

Жизнь без индексов: Куча (Heap)

Если таблица создается без каких-либо индексов, она представляет собой структуру, которую в терминологии баз данных называют «Кучей» (Heap). В куче данные хранятся без какого-либо логического порядка. Новые строки просто записываются на первую попавшуюся страницу, где есть свободное место.

Поиск данных в куче — это катастрофа для производительности. Допустим, у нас есть таблица Users с 10 миллионами записей. Каждая строка весит 200 байт. На одну страницу поместится строк. Следовательно, вся таблица займет страниц.

Если мы выполняем запрос SELECT * FROM Users WHERE UserID = 745301, а индекса нет, SQL Server не знает, на какой из 250 тысяч страниц находится нужная запись. У него остается единственный выход — прочитать каждую страницу от первой до последней. Этот процесс называется полным сканированием таблицы (Table Scan).

Движок базы данных будет загружать в оперативную память страницу за страницей, проверять каждую из 40 строк на совпадение с условием UserID = 745301 и двигаться дальше. Объем прочитанных данных составит . Чтение двух гигабайт с жесткого диска ради поиска одной строки размером 200 байт — яркий пример неэффективного использования ресурсов. Более того, даже если нужная строка будет найдена на 5-й странице, SQL Server продолжит сканирование до конца таблицы, потому что в куче нет гарантии, что не существует другой строки с таким же UserID.

Фундамент быстрого поиска: B-дерево

Чтобы избежать полного сканирования, реляционные базы данных используют структуру данных, известную как B-дерево (B-Tree). Буква "B" означает "Balanced" (сбалансированное). В контексте SQL Server, узлами этого дерева являются те самые 8-килобайтные страницы.

B-дерево имеет строгую иерархию:

Корневой узел (Root Node). Единственная страница на самом верхнем уровне дерева. Это точка входа для любого поиска.

Промежуточные уровни (Intermediate Nodes). Страницы, которые служат навигационными указателями. Они содержат ключи и ссылки на страницы более низкого уровня.

Листовой уровень (Leaf Nodes). Самый нижний уровень дерева. В зависимости от типа индекса (что будет подробно разобрано в следующих главах), здесь хранятся либо сами строки данных, либо указатели на них.

Главная сила B-дерева заключается в его коэффициенте ветвления (Fan-out). Коэффициент ветвления — это количество дочерних страниц, на которые может ссылаться одна родительская страница.

Поскольку страница индекса содержит только значения ключевого столбца (например, UserID) и 6-байтовый указатель на дочернюю страницу (FileID:PageID), записи на страницах промежуточных уровней очень компактны. Если ключ UserID имеет тип INT (4 байта), то одна запись занимает около 10 байт (плюс служебная информация). На одной 8-килобайтной странице поместится около 600-700 таких указателей.

Посмотрим на математику роста дерева с коэффициентом ветвления, равным 600:

Уровень 0 (Корень): 1 страница. Ссылается на 600 страниц 1-го уровня.

Уровень 1: 600 страниц. Каждая ссылается на 600 страниц 2-го уровня. Итого: страниц.

Уровень 2 (Листья): 360 000 страниц. Если на листовой странице помещается 40 строк данных, то дерево покрывает строк.

Дерево, покрывающее более 14 миллионов записей, имеет глубину всего в 3 уровня.

!Пошаговый поиск в B-дереве

Когда выполняется запрос SELECT * FROM Users WHERE UserID = 745301, алгоритм поиска работает следующим образом:

SQL Server читает 1 корневую страницу. Он видит, что значения от 1 до 800 000 находятся в первой дочерней странице, от 800 001 до 1 600 000 — во второй и так далее. Движок выбирает нужный указатель.

Читается 1 страница на промежуточном уровне. Там указатели более детализированы. Движок находит диапазон, содержащий 745301, и спускается ниже.

Читается 1 страница на листовом уровне, где находится искомая строка.

Вместо сканирования 250 000 страниц в куче (2 ГБ данных), SQL Server прочитал ровно 3 страницы (). Вычислительная сложность такого поиска логарифмическая — . Даже если таблица вырастет до миллиарда строк, глубина дерева увеличится максимум до 4 или 5 уровней. Затраты на поиск одной строки составят 4-5 логических чтений. Именно этот механизм делает индексы такими мощными.

Механика горизонтального сканирования (Range Scan)

B-дерево в SQL Server имеет важную модификацию: страницы на одном уровне связаны друг с другом в двусвязный список. Заголовок каждой страницы содержит указатели NextPage и PrevPage.

Это критически важно для запросов, запрашивающих диапазоны данных, например: SELECT * FROM Users WHERE UserID BETWEEN 100 AND 500. Без двусвязного списка движку пришлось бы спускаться от корня к листьям для значения 100, затем снова идти от корня для 101, затем для 102 и так далее.

Благодаря двусвязному списку алгоритм меняется:

SQL Server выполняет вертикальный спуск по дереву, чтобы найти стартовую точку — UserID = 100.

Найдя нужную листовую страницу, он читает строки до конца этой страницы.

Дойдя до конца, он не возвращается к корню. Он читает указатель NextPage в заголовке страницы и мгновенно переходит на соседнюю листовую страницу.

Горизонтальное чтение продолжается до тех пор, пока не встретится значение больше 500.

Такая операция называется сканированием диапазона (Range Scan). Она сочетает в себе скорость точного поиска по индексу с эффективностью последовательного чтения страниц.

Балансировка и расщепление страниц (Page Split)

Слово «сбалансированное» означает, что путь от корня до любого листа всегда состоит из одинакового количества шагов (страниц). Дерево не может иметь одну ветвь длиной в 3 уровня, а другую — в 5. Это гарантирует предсказуемое время выполнения запросов.

Но данные постоянно добавляются. Что происходит, когда листовая страница заполняется на 100%, и в нее нужно вставить новую строку, которая по логическому порядку ключа должна находиться именно там?

SQL Server выполняет операцию расщепления страницы (Page Split).

Движок выделяет новую пустую страницу (8 КБ) в памяти и на диске.

Он берет переполненную страницу и перемещает ровно половину ее записей на новую страницу.

Обновляются указатели NextPage и PrevPage в двусвязном списке, чтобы встроить новую страницу в правильное место цепочки.

Обновляется родительская страница на промежуточном уровне: в нее добавляется указатель на новую созданную страницу.

Расщепление страницы — это тяжелая и ресурсоемкая операция. Во-первых, она требует дополнительных операций записи на диск и генерации большого объема записей в журнал транзакций (Transaction Log). Во-вторых, новая страница часто выделяется в другом экстенте, физически далеко от исходной страницы.

Это приводит к логической фрагментации: логический порядок страниц (по ключу индекса) перестает совпадать с их физическим порядком на диске. Когда таких расщеплений происходит много, горизонтальное чтение по указателям NextPage заставляет считывающую головку жесткого диска (или контроллер SSD) постоянно перепрыгивать между разными участками памяти, что деградирует производительность последовательного чтения.

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