Глубокое погружение в структуру B-Tree: страницы, узлы, балансировка, кластеризация
Понимание внутренней структуры B-Tree помогает предсказывать поведение индексов при вставке, обновлении и удалении данных. Это критически важно для высоконагруженных систем.
InnoDB работает со страницами (pages) — блоками фиксированного размера, обычно 16 КБ. Это минимальная единица чтения и записи с диска. B-Tree индекс состоит из трёх типов страниц:
-- Размер страницы задаётся при инициализации и не меняется
SHOW VARIABLES LIKE 'innodb_page_size';
-- Результат: 16384 (16 КБ)Каждая внутренняя страница может содержать сотни ключей-указателей (fan-out). Поэтому высота дерева мала: для 10 миллионов строк — всего 3-4 уровня. Это значит, что любой поиск требует 3-4 чтения страниц.
Когда страница заполняется (при INSERT), происходит split — деление на две страницы:
До split: После split:
[1,3,5,7,9] FULL [1,3,5] [7,9]
↑ ↑
parent: 5 → новая страница
Split корня увеличивает высоту дерева на 1. Это редкое событие, но оно происходит автоматически и прозрачно.
Вставка в конец (AUTO_INCREMENT) — оптимальный сценарий:
-- InnoDB всегда вставляет в последнюю листовую страницу
CREATE TABLE orders (
id BIGINT AUTO_INCREMENT PRIMARY KEY,
user_id INT NOT NULL,
created_at DATETIME DEFAULT NOW()
);
-- Каждый INSERT идёт на одну и ту же (последнюю) страницуНовые записи всегда попадают на последнюю листовую страницу. Она ещё не заполнена, поэтому split происходит редко. Это обеспечивает последовательный (sequential) I/O — самый быстрый тип доступа.
Вставка в середину (UUID, случайный ключ) — проблемный сценарий:
-- UUID v4 — случайный, вставки распределяются по всему дереву
CREATE TABLE sessions (
id CHAR(36) PRIMARY KEY DEFAULT (UUID()),
user_id INT,
data JSON
);
-- Каждая вставка может попасть на ЛЮБУЮ страницу → частые split'ыСлучайный ключ распределяет вставки по ВСЕМ страницам дерева. Каждая вставка на заполненную страницу вызывает split, перемещение ~50% записей и обновление родительского узла. Это создаёт:
Параметр innodb_fill_factor контролирует заполненность страниц при создании индекса:
-- По умолчанию 100 — страницы заполнены полностью
-- Для нагрузки с частыми вставками можно оставить 10-20% свободного места
SET GLOBAL innodb_fill_factor = 85;
CREATE INDEX idx_user_created ON orders(user_id, created_at);
-- Страницы заполнены на 85%, 15% свободно для будущих вставокЗначение 85 означает, что страницы заполняются на 85%, оставляя 15% для будущих вставок. Это снижает частоту split'ов при последующих INSERT. Значение 100 (по умолчанию) оптимально для read-only нагрузки, но плохо при частых модификациях.
InnoDB обеспечивает конкурентную запись без блокировки всего дерева через latch'и на уровне отдельных страниц:
Дополнительно используется optimistic insert — попытка вставки без latch'а родительской страницы, если на листовой есть свободное место. При неудаче — pessimistic insert с полной блокировкой пути до корня.
Выбирайте монотонно растущий PRIMARY KEY. AUTO_INCREMENT INT/BIGINT или UUID v7 (timestamp-based) обеспечивают вставку в конец дерева, минимизируя split и фрагментацию.
Избегайте случайных ключей. UUID v4, MD5, хэши — все они распределяют вставки случайно по дереву, вызывая постоянные split.
Мониторьте высоту дерева. Для большинства таблиц высота 3-4. Если высота растёт (>4), проверьте размер индекса и fill factor:
-- Косвенная оценка через размер индекса
SELECT INDEX_NAME,
ROUND(STAT_VALUE * @@innodb_page_size / 1024 / 1024, 2) AS size_mb
FROM mysql.innodb_index_stats
WHERE table_name = 'orders' AND stat_name = 'size';Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.