Внутреннее устройство B-Tree индексов

Понимание внутренней структуры B-Tree помогает предсказывать поведение индексов при вставке, обновлении и удалении данных. Это критически важно для высоконагруженных систем.

#Страницы — единица хранения

InnoDB работает со страницами (pages) — блоками фиксированного размера, обычно 16 КБ. Это минимальная единица чтения и записи с диска. B-Tree индекс состоит из трёх типов страниц:

Корневая страница (root page) — точка входа в дерево, одна на индекс
Внутренние страницы (internal pages) — содержат ключи и указатели на дочерние страницы
Листовые страницы (leaf pages) — содержат данные: для кластерного индекса — полные строки, для вторичного — значения PK

-- Размер страницы задаётся при инициализации и не меняется
SHOW VARIABLES LIKE 'innodb_page_size';
-- Результат: 16384 (16 КБ)

Каждая внутренняя страница может содержать сотни ключей-указателей (fan-out). Поэтому высота дерева мала: для 10 миллионов строк — всего 3-4 уровня. Это значит, что любой поиск требует 3-4 чтения страниц.

#Split страниц и балансировка

Когда страница заполняется (при INSERT), происходит split — деление на две страницы:

Записи делятся примерно пополам (midpoint split)
Половина записей перемещается на новую страницу
В родительский узел добавляется ключ-разделитель с указателем на новую страницу
Если родитель тоже заполнен — рекурсивный split вплоть до корня

До split:           После split:
[1,3,5,7,9] FULL    [1,3,5]  [7,9]
                     ↑        ↑
                 parent: 5 → новая страница

Split корня увеличивает высоту дерева на 1. Это редкое событие, но оно происходит автоматически и прозрачно.

#Вставка в конец vs вставка в середину

Вставка в конец (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% записей и обновление родительского узла. Это создаёт:

Больше I/O операций (чтение + запись нескольких страниц)
Фрагментацию (пустое место на страницах после split)
Больше блокировок (latch contention при конкурентных вставках)

#Fill factor — управление заполненностью

Параметр 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 нагрузки, но плохо при частых модификациях.

#Concurrent insert: latch'и на уровне страниц

InnoDB обеспечивает конкурентную запись без блокировки всего дерева через latch'и на уровне отдельных страниц:

Транзакция, модифицирующая страницу A, блокирует только её
Другая транзакция может одновременно модифицировать страницу B
При split блокируется также родительская страница

Дополнительно используется 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';