В таблице с кластеризованным B-деревом случайные вставки постепенно замедлили диапазонное чтение при неизменном числе строк. Какой механизм индекса это объясняет?
Случайные вставки могут вызывать разбиение страниц индекса. Новая строка не помещается в целевую страницу, поэтому СУБД делит её на две и перераспределяет записи; логический порядок страниц начинает хуже соответствовать их физическому расположению. Диапазонное чтение после этого требует большего числа операций ввода-вывода, хотя количество строк не изменилось.
B-деревья и их варианты создавались для эффективной работы с дисковыми страницами: поиск должен был читать небольшое число хорошо заполненных узлов, а диапазон — последовательно обходить листовые страницы. Такая организация существенно уменьшает число обращений к диску по сравнению с неструктурированным поиском.
Однако страницы имеют фиксированный размер, а записи могут вставляться в середину ключевого диапазона. Для сохранения порядка индекс должен перераспределять записи, поэтому производительность чтения зависит не только от логической структуры дерева, но и от физического размещения его страниц.
Проблема возникает при вставках ключей, распределённых по существующему диапазону, например случайных идентификаторов. Целевая страница постепенно заполняется, и очередная вставка приводит к page split — разделению страницы и перемещению части записей на новую страницу.
После множества таких операций соседние в логическом порядке страницы могут находиться далеко друг от друга на диске. Диапазонный запрос вынужден читать больше страниц и чаще выполнять разрозненные операции ввода-вывода. Дополнительно индекс может занимать больше места из-за неполной заполненности страниц.
В листовом уровне B-дерева записи упорядочены по ключу. При вставке в середину диапазона СУБД находит нужную страницу, а если свободного места недостаточно, создаёт новую страницу и распределяет записи между старой и новой.
Разбиение сохраняет логический порядок ключей, поэтому индекс остаётся корректным. Но физический порядок страниц может стать менее последовательным: следующий листовой блок по ключу не обязательно расположен рядом с текущим блоком. Это особенно важно для диапазонных сканирований, которые читают много соседних по ключу записей.
Фрагментация не означает автоматически медленный запрос. Для небольшого индекса, полностью помещающегося в памяти, влияние может быть почти незаметным. Сильнее всего страдают крупные диапазонные чтения, когда страницы приходится получать с диска или из распределённых хранилищ.
Один из способов уменьшить число разбиений — оставить свободное место на страницах при перестроении индекса, используя подходящий fill factor. Компромисс очевиден: свободное место снижает вероятность ближайших разбиений, но увеличивает размер индекса и количество страниц, которые нужно читать при сканировании.
Периодическое перестроение или реорганизация индекса может восстановить более компактное размещение страниц, но это не универсальное лечение. Необходимо учитывать блокировки, дополнительную нагрузку, размер индекса, доступное место и то, действительно ли запросы выполняют большие диапазонные чтения. Причину следует подтверждать измерениями, а не устранять фрагментацию только по процентному показателю.
В таблицу заказов постоянно поступали записи с непоследовательными внешними идентификаторами. Диапазонные отчёты по кластеризованному ключу со временем стали читать заметно больше страниц, хотя объём результата почти не изменился.
Рассматривались три варианта. Замена ключа на последовательно возрастающий уменьшила бы число разбиений, но потребовала бы изменения модели данных и могла создать конкуренцию за последнюю страницу при высокой параллельности. Увеличение свободного места на страницах снизило бы частоту разбиений, но сразу увеличило бы размер индекса. Регулярное перестроение было проще внедрить, однако добавляло периоды высокой нагрузки и не устраняло саму причину.
Выбрали последовательный технический ключ для кластеризации, оставив исходный идентификатор отдельным некластеризованным индексом, и настроили обслуживание крупных индексов по фактическим метрикам. Это уменьшило число новых разбиений и сделало диапазонные чтения более последовательными без изменения условий отчётов.
Нет. Точечный поиск обычно читает небольшой путь от корня к листовой странице, поэтому логическая разрозненность листьев влияет на него слабее, чем на диапазонный обход. Тем не менее увеличенный размер индекса может ухудшить использование кэша, а большое число разбиений — повысить общую стоимость обслуживания и конкуренцию за страницы.
Нет. Такой ключ обычно уменьшает вставки в середину дерева, но не устраняет все причины фрагментации. Возможны удаления, обновления ключа, другие индексы с неудачным порядком ключей, недостаток свободного места и параллельная нагрузка на последнюю страницу. Кроме того, последовательный ключ может сделать одну область индекса горячей при интенсивных вставках.
Перестроение исправляет уже возникшее физическое размещение: страницы создаются заново в более компактном порядке, а заданный коэффициент заполнения определяет, сколько свободного места оставить для будущих вставок. Свободное место помогает предотвратить новые разбиения, но увеличивает объём чтения. Перестроение само по себе не меняет характер будущих вставок, поэтому без изменения ключа или настройки заполнения фрагментация может быстро вернуться.