B-tree в индексах баз данных — как дерево ускоряет поиск, диапазоны и сортировку

B-tree хранит ключи в отсортированном сбалансированном дереве, где один узел вмещает десятки или сотни значений и ссылок. Такая структура быстро находит отдельную запись, начало диапазона и строки в нужном порядке, сохраняя небольшую высоту даже у таблиц с миллионами записей.

B-tree за одну минуту — упорядоченный каталог из нескольких уровней

В гайде по составным индексам левый префикс, диапазоны и порядок колонок опираются на одну базовую структуру — B-tree. Представьте большой справочник, разделённый на страницы. На верхней странице записаны границы крупных разделов, внутри каждого раздела есть ещё одна страница с более точными границами, а нижний уровень содержит индексные записи.

Упрощённая схема выглядит так:

[30 | 60]
                       /     |      \
              [10 | 20]   [40 | 50]   [70 | 80 | 90]

Числа в корневом узле делят всё множество ключей на три диапазона: левее 30, от 30 до 60 и правее 60. Поиск значения 50 начинается с корня. Сравнение с 30 и 60 направляет запрос в среднюю ветку. В дочернем узле база находит 50 среди небольшого набора отсортированных ключей. Миллионы остальных значений остаются за пределами поиска.

Три свойства дают B-tree практическую силу:

1. Ключи хранятся в порядке сравнения. Числа идут по возрастанию, даты — по хронологии, строки — по правилам выбранной сортировки и сравнения.
2. Каждый узел содержит много ключей. У дерева получается высокая ветвистость и малая глубина.
3. Все листья находятся на одной глубине. Любой путь от корня до нижнего уровня имеет одинаковую длину, поэтому отдельный участок дерева не превращается в длинную цепочку.

Название «дерево» описывает логическую схему. На диске или в памяти узлы обычно представлены страницами фиксированного размера, а ссылки между ними содержат номера страниц или внутренние адреса.

Страницы хранения объясняют форму B-tree лучше двоичного дерева

Двоичное дерево размещает в узле один ключ и имеет до двух дочерних ветвей. Дисковая база данных читает информацию страницами. PostgreSQL обычно использует блоки по 8 КиБ, InnoDB по умолчанию применяет страницы по 16 КиБ, SQLite поддерживает настраиваемый размер страницы файла.

Одно чтение страницы приносит сразу несколько килобайт. B-tree заполняет эту страницу большим количеством ключей и указателей. Один переход по уровню отбрасывает крупную часть пространства поиска.

Возьмём условный узел, который способен направить поиск в 200 дочерних страниц. Четыре перехода покрывают:

200 × 200 × 200 × 200 = 1 600 000 000

Это иллюстрация, а не расчёт ёмкости конкретного индекса. Реальное число зависит от размера страницы, длины ключей, служебных заголовков, ссылок на строки, заполненности страниц, сжатия и особенностей движка. Пример показывает главный эффект: высокая ветвистость удерживает дерево низким.

Количество уровней связывают с логарифмической сложностью:

O(logₘ N)

Здесь N — число ключей, а m — приблизительное число ветвей из одного узла. Большое m заметно уменьшает глубину. Добавление ещё одного уровня обычно требуется после многократного роста индекса.

Корень, внутренние страницы и листья выполняют разные задачи

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

Состав записи зависит от СУБД:

• PostgreSQL B-tree обычно хранит ключ и TID — идентификатор физической позиции версии строки в heap-таблице;
• вторичный индекс InnoDB хранит индексированные колонки и первичный ключ строки;
• индекс SQLite для rowid-таблицы включает индексированные значения и rowid;
• покрывающий индекс может хранить дополнительные поля, нужные запросу.

Эта разница влияет на количество чтений. В InnoDB поиск через вторичный индекс часто включает два дерева: сначала вторичный индекс возвращает первичный ключ, затем кластерный индекс находит всю строку.

B-tree и B+ tree описывают близкое семейство структур

Классическое B-tree допускает хранение записей во внутренних узлах и листьях. B+ tree концентрирует записи данных на листовом уровне, а верхние узлы использует для навигации. Листья обычно связаны в последовательность, что ускоряет проход по диапазону.

Документация СУБД часто использует общее название B-tree для семейства практических вариантов. Реализации добавляют ссылки на соседние страницы, верхние границы ключей, оптимизации дубликатов, сокращение разделительных ключей, конкурентные разбиения, собственные правила удаления и журналирование.

PostgreSQL реализует конкурентный вариант алгоритма Lehman–Yao. В его B-tree каждая страница имеет ссылку на правого соседа и верхнюю границу ключей. Поиск способен заметить параллельное разбиение и продолжить движение вправо.

Для чтения SQL-планов удобно держать в голове модель B+ tree: верхние страницы направляют поиск, листья образуют упорядоченный нижний уровень. Точные детали проверяют в документации выбранного движка.

Точечный поиск спускается к одному узкому диапазону

Пусть индекс содержит идентификаторы заказов, а запрос ищет order_id = 572341.

CREATE INDEX idx_orders_id
    ON orders (order_id);

SELECT *
FROM orders
WHERE order_id = 572341;

Движок выполняет последовательность действий:

1. Загружает корневую страницу индекса.
2. Сравнивает искомый ключ с разделителями корня.
3. Переходит на подходящую внутреннюю страницу.
4. Повторяет сравнение до листового уровня.
5. Находит первую запись с ключом 572341.
6. Получает локатор строки.
7. Читает строку таблицы, если нужные колонки отсутствуют в индексе.

Внутри одной страницы поиск по отсортированному массиву ключей может использовать двоичный поиск или близкую технику. Основная экономия появляется на уровне страниц: база посещает несколько узлов дерева и пропускает огромные участки индекса.

Дубликаты усложняют последний шаг. Индекс по status может содержать сотни тысяч записей со значением paid. Дерево быстро находит начало группы, затем запрос проходит по всем подходящим листовым записям. Скорость начального позиционирования остаётся высокой, общий объём работы определяется числом совпадений.

Диапазонный поиск находит начало и читает соседние записи

Упорядоченность превращает B-tree в удобную структуру для условий <, <=, >, >=, BETWEEN и диапазонов дат.

SELECT id, created_at, total_amount
FROM orders
WHERE created_at >= '2026-07-01'
  AND created_at <  '2026-08-01'
ORDER BY created_at;

Индекс:

CREATE INDEX idx_orders_created_at
    ON orders (created_at);

Сначала дерево ищет первую запись, удовлетворяющую нижней границе 2026-07-01. После позиционирования база последовательно читает следующие записи до границы 2026-08-01.

поиск нижней границы → первый подходящий лист
                    → следующая запись
                    → следующая запись
                    → соседняя листовая страница
                    → остановка на верхней границе

Такая модель объясняет несколько особенностей:

• небольшой диапазон читает малую часть индекса;
• широкий диапазон может охватить большую часть таблицы;
• отсутствие верхней границы продолжает сканирование до конца подходящей области;
• LIMIT способен остановить чтение после первых строк;
• подходящий ORDER BY получает готовый порядок без отдельной сортировки.

PostgreSQL рассматривает B-tree для операторов <, <=, =, >=, >, конструкций BETWEEN, IN, условий IS NULL и IS NOT NULL. Индекс может участвовать в префиксном поиске LIKE 'foo%' при подходящих правилах сравнения. Шаблон LIKE '%foo' не задаёт известное начало диапазона и обычно не даёт прямого позиционирования в обычном B-tree.

Сортировка уже встроена в порядок листовых записей

Запросу с ORDER BY нужен упорядоченный результат. Без подходящего индекса движок читает строки, помещает их в память или временное хранилище и сортирует. B-tree способен отдавать ключи в готовой последовательности.

CREATE INDEX idx_events_created
    ON events (created_at);

SELECT id, created_at
FROM events
ORDER BY created_at
LIMIT 50;

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

Обратный проход даёт порядок по убыванию:

SELECT id, created_at
FROM events
ORDER BY created_at DESC
LIMIT 50;

PostgreSQL умеет сканировать обычный B-tree вперёд и назад. Для многоколоночной сортировки направление каждой колонки требует внимания:

ORDER BY tenant_id ASC, created_at DESC

Подходящий индекс:

CREATE INDEX idx_events_tenant_created
    ON events (tenant_id ASC, created_at DESC);

Индекс (tenant_id ASC, created_at ASC) естественно поддерживает обе колонки по возрастанию при прямом проходе или обе по убыванию при обратном. Смешанное направление ASC, DESC задают в определении индекса, если такой запрос составляет заметную часть нагрузки.

Составной ключ сортируется как последовательность полей

Индекс:

CREATE INDEX idx_orders_tenant_status_created
    ON orders (tenant_id, status, created_at);

хранит записи в лексикографическом порядке. Сравнение начинается с tenant_id. При равенстве первого поля движок сравнивает status. Дата участвует после совпадения первых двух значений.

(1, cancelled, 2026-07-01)
(1, paid,      2026-07-01)
(1, paid,      2026-07-02)
(1, shipped,   2026-07-03)
(2, new,       2026-07-01)
(2, paid,      2026-07-02)

Индекс хорошо позиционируется для условий:

WHERE tenant_id = 1

WHERE tenant_id = 1
  AND status = 'paid'

WHERE tenant_id = 1
  AND status = 'paid'
  AND created_at >= '2026-07-01'

Запрос по одному status сталкивается с отдельными группами каждого tenant_id:

WHERE status = 'paid'

Классическое правило левого префикса остаётся главным ориентиром. Для индекса (a, b, c) естественные префиксы выглядят как (a), (a, b) и (a, b, c).

Современные оптимизаторы могут применять дополнительные техники. PostgreSQL 18 описывает skip scan: при небольшом числе различных значений ведущей колонки планировщик способен выполнить серию поисков по её возможным значениям и использовать условие на следующую колонку. Такой план зависит от статистики и стоимости. Проектирование индекса на регулярный запрос лучше строить вокруг явного ведущего префикса.

Первое диапазонное условие задаёт основную границу сканирования

Равенства фиксируют конкретную группу ключей. Первое условие диапазона определяет непрерывный участок внутри этой группы.

WHERE tenant_id = 7
  AND status = 'paid'
  AND created_at >= '2026-07-01'
  AND total_amount >= 10000

Индекс:

(tenant_id, status, created_at, total_amount)

быстро находит группу tenant_id = 7, затем подгруппу status = 'paid', затем начинает диапазон с заданной даты. Значения total_amount внутри этого диапазона перемешаны по датам. Условие по сумме может проверяться на индексных записях, но не образует одну общую непрерывную границу после диапазона даты.

Индекс:

(tenant_id, status, total_amount, created_at)

делает сумму первым диапазоном после равенств. Такой порядок полезен, когда отбор по сумме сокращает работу сильнее. Сортировка по дате после диапазона суммы потребует дополнительной обработки.

Рабочее правило для одного семейства запросов:

1. колонки с равенствами;
2. колонка первого значимого диапазона;
3. колонки, продолжающие нужный порядок;
4. данные покрытия, которые движок способен хранить отдельно от ключа.

Селективность, сортировка и LIMIT способны изменить оптимальный порядок. Ответ даёт план на реалистичном объёме данных.

Вставка добавляет ключ в лист и иногда делит страницу

Новая строка должна попасть в правильную позицию отсортированного индекса.

INSERT INTO orders (id, tenant_id, status, created_at)
VALUES (900001, 7, 'paid', CURRENT_TIMESTAMP);

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

Заполненная страница требует разбиения:

до вставки:
[10 | 20 | 30 | 40]

новый ключ:
25

разбиение:
[10 | 20]    [25 | 30 | 40]

Родитель получает новый разделитель и ссылку на появившуюся страницу. Заполненный родитель тоже делится. Цепочка может дойти до корня. Разбиение корня создаёт новый корень и увеличивает высоту дерева на один уровень.

Эта операция сохраняет баланс: все листья остаются на одинаковой глубине. Цена состоит из дополнительных записей страниц, журналирования, блокировок или защёлок внутренних структур и возможного перемещения ключей.

Последовательные и случайные ключи создают разную картину записи

Автоинкрементный идентификатор, растущая дата или последовательный номер обычно добавляются в правый край дерева. Запись концентрируется на последних листовых страницах. Такое расположение удобно для пакетных вставок и последовательного I/O, но горячая правая страница может стать точкой конкуренции при большом числе параллельных потоков.

Случайный UUID распределяет вставки по разным участкам индекса. Нагрузка размазывается по страницам, а рабочий набор становится шире. Возможные последствия:

• больше случайных чтений и записей;
• частые разбиения в разных частях дерева;
• меньшая локальность кеша;
• рост фрагментации и служебного пространства;
• увеличение размера вторичных индексов InnoDB при длинном первичном ключе.

Эти эффекты зависят от движка, формата UUID, объёма памяти, размера индекса и интенсивности записи. UUID с временной упорядоченностью, включая UUIDv7, даёт более локальный порядок вставок, сохраняя распределённую генерацию идентификаторов. Решение оценивают по фактической нагрузке, задержке записи и размеру всех связанных индексов.

Fill factor оставляет место для будущих вставок

Страница, заполненная почти до предела, использует пространство экономно. Вставка внутрь её диапазона быстрее приводит к разбиению. Параметр заполнения оставляет резерв.

В PostgreSQL B-tree можно задать fillfactor:

CREATE INDEX idx_orders_created
    ON orders (created_at)
    WITH (fillfactor = 80);

Значение 80 ориентирует построение индекса на заполнение листовых страниц примерно на 80 процентов. Оставшиеся 20 процентов дают место последующим вставкам. Индекс получается крупнее сразу после построения и может реже делить страницы при подходящей нагрузке.

Выбор зависит от характера ключа:

• монотонные вставки в правый край редко используют резерв по всему дереву;
• случайные вставки могут выигрывать от свободного места внутри страниц;
• преимущественно читаемая таблица обычно ценит компактность;
• частые обновления индексированных значений увеличивают потребность в запасе.

В InnoDB управление заполнением и разбиениями устроено иначе. Универсальное число для разных СУБД отсутствует.

Удаление освобождает запись, а слияние страниц зависит от реализации

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

Промышленные СУБД учитывают параллельные транзакции, журналирование, версии строк и стоимость немедленного слияния. Физическое удаление индексной записи может происходить позже логического DELETE.

PostgreSQL использует MVCC: обновление создаёт новую версию строки, а старая версия остаётся до очистки. VACUUM удаляет ссылки на версии, которые больше не видит ни одна транзакция. Длительные транзакции задерживают очистку и способны увеличивать таблицу и индексы.

InnoDB помечает записи для удаления и очищает их через фоновые механизмы purge. При низкой заполненности страница может стать кандидатом на слияние с соседней страницей. Конкретные пороги и алгоритмы относятся к реализации движка.

Размер B-tree после массового удаления редко уменьшается в файле мгновенно. Освободившееся место может использоваться повторно. Возврат места операционной системе и перестройка структуры требуют отдельных операций, которые различаются между PostgreSQL, MySQL и SQLite.

Обновление индексированной колонки похоже на удаление и новую вставку

UPDATE orders
SET status = 'shipped'
WHERE id = 900001;

Изменение status затрагивает индекс (status, created_at). Запись должна покинуть группу paid и попасть в группу shipped. Движок создаёт новую индексную позицию и выводит старую из использования по правилам своей транзакционной модели.

Обновление колонки, отсутствующей во всех индексах, обходится дешевле. PostgreSQL может выполнить HOT update, когда новая версия строки помещается на той же heap-странице и ни один индексированный столбец не изменяется. Условия HOT зависят от свободного места страницы и состава индексов.

Каждый дополнительный B-tree увеличивает стоимость записи:

• INSERT добавляет запись во все подходящие индексы;
• DELETE выводит записи из всех индексов;
• UPDATE меняет индексы, где затронут ключ или предикат;
• журнал транзакций получает больше данных;
• резервные копии и репликация передают больший объём изменений;
• кеш хранит больше страниц.

Индекс проектируют под подтверждённые запросы, ограничения целостности и измеримые планы.

Кластерный индекс InnoDB хранит строки в листьях первичного ключа

InnoDB организует таблицу вокруг кластерного индекса. Обычно им становится PRIMARY KEY.

CREATE TABLE orders (
    id           BIGINT PRIMARY KEY,
    tenant_id    BIGINT NOT NULL,
    status       VARCHAR(20) NOT NULL,
    created_at   DATETIME NOT NULL,
    total_amount DECIMAL(12, 2) NOT NULL,
    INDEX idx_orders_tenant_created (tenant_id, created_at)
) ENGINE=InnoDB;

Листовые записи кластерного индекса содержат данные строки. Поиск по PRIMARY KEY приводит прямо к странице с записью.

Вторичный индекс idx_orders_tenant_created содержит:

(tenant_id, created_at, primary_key)

Запрос всех колонок проходит два этапа:

1. вторичный B-tree находит подходящие первичные ключи;
2. кластерный B-tree получает строки по этим ключам.

Узкий первичный ключ уменьшает каждый вторичный индекс, потому что его значение дублируется в листовых записях. Длинный составной или строковый первичный ключ увеличивает размер всех вторичных деревьев.

Покрывающий вторичный индекс способен завершить запрос без второго поиска, если все требуемые поля присутствуют в его записи.

PostgreSQL отделяет B-tree от heap-таблицы

Обычная таблица PostgreSQL хранится как heap — набор страниц со строковыми версиями. B-tree содержит ключи и TID, который указывает на блок и позицию строки внутри блока.

B-tree:
(email, TID)

heap:
страница 142, позиция 7 → версия строки пользователя

Индексный порядок не задаёт постоянный физический порядок строк heap-таблицы. Команда CLUSTER может один раз переписать таблицу по выбранному индексу, а последующие вставки и обновления постепенно меняют физическую картину.

Обычный Index Scan читает B-tree, получает TID, обращается к heap, проверяет видимость версии строки и возвращает значения. Разбросанные TID приводят к обращениям к разным heap-страницам. Планировщик учитывает эту стоимость и способен выбрать Bitmap Index Scan: сначала собрать набор адресов, сгруппировать их по страницам, затем читать heap более последовательно.

Покрывающий индекс сокращает обращения к таблице

SELECT created_at, total_amount
FROM orders
WHERE tenant_id = 7
ORDER BY created_at DESC
LIMIT 50;

PostgreSQL позволяет добавить поле результата через INCLUDE:

CREATE INDEX idx_orders_tenant_created_cover
    ON orders (tenant_id, created_at DESC)
    INCLUDE (total_amount);

Ключевыми колонками остаются tenant_id и created_at. total_amount хранится как полезная нагрузка и не меняет порядок дерева.

Index Only Scan возможен, когда индексный метод способен вернуть нужные значения, запросу хватает колонок индекса, а правила MVCC позволяют подтвердить видимость без чтения конкретной heap-строки.

PostgreSQL проверяет карту видимости страниц. Для недавно изменённой heap-страницы может потребоваться обращение к таблице. Стабильные таблицы с большим числом all-visible страниц получают больше пользы.

В MySQL термин covering index означает, что вторичная индексная запись содержит все колонки запроса. Отдельный синтаксис INCLUDE в InnoDB отсутствует: дополнительные колонки добавляются в состав индекса и участвуют в его ключевой структуре. SQLite показывает USING COVERING INDEX в EXPLAIN QUERY PLAN, когда данные доступны из индекса.

Широкое покрытие увеличивает размер листовых записей, уменьшает ветвистость и удорожает изменения. Поля покрытия выбирают для конкретных частых запросов.

Уникальный B-tree одновременно ускоряет поиск и защищает данные

CREATE UNIQUE INDEX uq_users_email
    ON users (email);

Перед вставкой движок ищет подходящую позицию в B-tree. Совпадение вызывает ошибку уникальности, свободная позиция принимает новую запись.

Составная уникальность:

CREATE UNIQUE INDEX uq_documents_tenant_external
    ON documents (tenant_id, external_id);

гарантирует уникальную пару внутри организации.

Поведение NULL различается между СУБД и настройками. PostgreSQL по умолчанию разрешает несколько NULL в уникальном индексе, а NULLS NOT DISTINCT заставляет считать их равными:

CREATE UNIQUE INDEX uq_profiles_phone
    ON profiles (phone) NULLS NOT DISTINCT;

Ограничения PRIMARY KEY и UNIQUE часто создают индекс автоматически. Удаление такого индекса затрагивает целостность данных, поэтому сначала проверяют связанное ограничение.

Функция над колонкой требует совпадающего индексного выражения

Есть обычный индекс:

CREATE INDEX idx_users_email
    ON users (email);

Запрос:

SELECT *
FROM users
WHERE lower(email) = 'user@example.com';

сравнивает результат выражения lower(email). PostgreSQL может использовать индекс на том же выражении:

CREATE INDEX idx_users_email_lower
    ON users (lower(email));

Условие и индекс должны совпадать по операции, типам и правилам сравнения, которые понимает оптимизатор.

Частые случаи потери прямого доступа:

WHERE DATE(created_at) = '2026-07-17'

WHERE CAST(user_id AS TEXT) = '42'

WHERE price * quantity > 10000

Возможные решения:

• переписать условие как диапазон по исходной колонке;
• создать индекс на выражении;
• добавить generated column в движке, где она поддерживается;
• привести параметр к типу колонки на стороне приложения;
• выбрать операторный класс или collation, соответствующий запросу.

Для даты удобен полуоткрытый диапазон:

WHERE created_at >= '2026-07-17 00:00:00'
  AND created_at <  '2026-07-18 00:00:00'

Такой предикат задаёт две границы обычного B-tree по created_at.

Частичный индекс хранит только нужный фрагмент ключей

PostgreSQL умеет строить B-tree по строкам, удовлетворяющим предикату:

CREATE INDEX idx_orders_pending_created
    ON orders (created_at)
    WHERE status = 'pending';

Запрос:

SELECT id, created_at
FROM orders
WHERE status = 'pending'
ORDER BY created_at
LIMIT 100;

работает с компактным деревом активной очереди, если ожидающие заказы составляют небольшую часть таблицы.

Польза складывается из трёх эффектов:

• меньше листовых записей;
• меньше страниц индекса;
• изменения строк вне предиката не затрагивают этот индекс.

Планировщик должен доказать, что условие запроса подразумевает предикат индекса. Формулировка WHERE status = 'pending' совпадает явно. Параметризованные и логически эквивалентные выражения могут не пройти доказательство в конкретной версии и форме запроса.

MySQL не предоставляет прямой аналог произвольного частичного индекса InnoDB. Для ограниченных сценариев используют generated columns, функциональные индексы, изменение схемы или отдельную таблицу активных сущностей.

Низкая селективность снижает пользу индексного перехода

Селективность показывает долю строк, которую оставляет условие. Уникальный идентификатор возвращает одну строку. Булевый флаг может вернуть половину таблицы.

Индекс по is_active способен быстро найти начало группы true, затем ему придётся прочитать большое число листовых записей, получить множество локаторов, посетить много страниц таблицы и проверить дополнительные условия.

Последовательное сканирование читает таблицу крупными блоками и может оказаться дешевле. Универсального процента, после которого индекс проигрывает, нет. Решение зависит от ширины строк, размещения данных, кеша, скорости накопителя, параллелизма, покрытия и LIMIT.

Индекс по низкокардинальной колонке получает смысл в составе более точного ключа:

(tenant_id, is_active, created_at)

или в частичном индексе:

CREATE INDEX idx_tasks_open
    ON tasks (created_at)
    WHERE completed_at IS NULL;

Планировщик оценивает кардинальность по статистике. Устаревшие или слабые оценки приводят к неудачному выбору плана.

Оптимизатор выбирает стоимость, а наличие индекса ничего не гарантирует

Запрос с подходящим B-tree может получить Seq Scan или Table Scan. Типичные причины:

• таблица помещается в несколько страниц;
• условие возвращает большую долю строк;
• запрос выбирает широкие строки и требует много обращений к таблице;
• статистика оценивает распределение иначе;
• функция над колонкой не совпадает с индексом;
• составной ключ не имеет полезного ведущего префикса;
• collation или оператор не поддерживаются индексным классом;
• шаблон начинается с %;
• сортировка охватывает слишком много строк;
• другой индекс или bitmap-план дешевле;
• параметризованный план использует усреднённую оценку.

Принудительный выбор индекса способен скрыть ошибку оценки и ухудшить другие значения параметров. Сначала сравнивают расчётное и фактическое число строк, чтения страниц и время узлов.

EXPLAIN показывает реальную роль B-tree в запросе

Создадим учебную таблицу PostgreSQL:

CREATE TABLE orders (
    id           BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    tenant_id    BIGINT NOT NULL,
    status       TEXT NOT NULL,
    created_at   TIMESTAMPTZ NOT NULL,
    total_amount NUMERIC(12, 2) NOT NULL
);

CREATE INDEX idx_orders_tenant_created
    ON orders (tenant_id, created_at DESC)
    INCLUDE (status, total_amount);

Запрос:

SELECT id, status, created_at, total_amount
FROM orders
WHERE tenant_id = 42
  AND created_at >= TIMESTAMPTZ '2026-07-01 00:00:00+00'
ORDER BY created_at DESC
LIMIT 50;

Проверка:

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT id, status, created_at, total_amount
FROM orders
WHERE tenant_id = 42
  AND created_at >= TIMESTAMPTZ '2026-07-01 00:00:00+00'
ORDER BY created_at DESC
LIMIT 50;

В хорошем плане ожидаются узлы и поля, близкие к следующим:

Limit
  -> Index Only Scan using idx_orders_tenant_created
       Index Cond: (
           tenant_id = 42
           AND created_at >= ...
       )
       Heap Fetches: ...

Смотрите на:

• Index Scan, Index Only Scan или Bitmap Index Scan;
• Index Cond — условия, задающие поиск внутри дерева;
• Filter — условия, применённые после получения кандидатов;
• actual rows — фактическое число строк;
• rows в оценке — прогноз планировщика;
• Heap Fetches — обращения к heap при Index Only Scan;
• Buffers: shared hit/read — работа кеша и физического чтения;
• Rows Removed by Filter — объём лишних кандидатов;
• loops — число повторов узла.

EXPLAIN ANALYZE выполняет запрос. Для изменяющих команд и тяжёлых операций используйте тестовую среду или безопасную транзакцию.

MySQL EXPLAIN ANALYZE показывает range scan и покрытие InnoDB

CREATE TABLE orders (
    id           BIGINT NOT NULL AUTO_INCREMENT,
    tenant_id    BIGINT NOT NULL,
    status       VARCHAR(20) NOT NULL,
    created_at   DATETIME(6) NOT NULL,
    total_amount DECIMAL(12, 2) NOT NULL,
    PRIMARY KEY (id),
    KEY idx_orders_tenant_created (
        tenant_id,
        created_at DESC,
        status,
        total_amount
    )
) ENGINE=InnoDB;

Проверка:

EXPLAIN ANALYZE
SELECT id, status, created_at, total_amount
FROM orders
WHERE tenant_id = 42
  AND created_at >= '2026-07-01 00:00:00'
ORDER BY created_at DESC
LIMIT 50;

MySQL 8.4 выводит EXPLAIN ANALYZE в формате TREE. В плане могут встречаться:

Index range scan on orders using idx_orders_tenant_created

Covering index lookup

Table scan

actual time=...
rows=...
loops=...

Поля status и total_amount включены в ключ вторичного индекса, а id присутствует там как первичный ключ InnoDB. Такой набор способен стать покрывающим для запроса. Цена — широкая индексная запись и более дорогие изменения.

SQLite различает SEARCH, SCAN и USING COVERING INDEX

CREATE TABLE orders (
    id           INTEGER PRIMARY KEY,
    tenant_id    INTEGER NOT NULL,
    status       TEXT NOT NULL,
    created_at   TEXT NOT NULL,
    total_amount REAL NOT NULL
);

CREATE INDEX idx_orders_tenant_created
    ON orders (tenant_id, created_at DESC);

План:

EXPLAIN QUERY PLAN
SELECT id, created_at
FROM orders
WHERE tenant_id = 42
  AND created_at >= '2026-07-01'
ORDER BY created_at DESC
LIMIT 50;

SQLite показывает высокоуровневую стратегию:

SEARCH orders USING COVERING INDEX idx_orders_tenant_created
    (tenant_id=? AND created_at>?)

Слово SEARCH указывает на чтение подмножества записей. SCAN может означать полный проход таблицы или индекса. Строка USE TEMP B-TREE FOR ORDER BY говорит о временной сортировочной структуре. Подходящий индекс способен убрать такую сортировку.

Формат EXPLAIN QUERY PLAN предназначен для интерактивной диагностики и может меняться между версиями SQLite. Автоматические тесты лучше проверяют измеримые свойства запроса и наличие нужных индексов, а не точное текстовое оформление плана.

Размер ключа влияет на ветвистость, высоту и кеш

Короткий целочисленный ключ занимает меньше места, чем длинная строка. На одну страницу помещается больше записей. Растёт ветвистость, сокращается число листовых страниц, больше дерева помещается в памяти.

Широкий ключ появляется из нескольких источников:

• длинный VARCHAR;
• составной индекс из многих колонок;
• дублирование первичного ключа во вторичных индексах InnoDB;
• payload-колонки покрытия;
• многобайтовая кодировка;
• служебные данные и локаторы строк;
• низкое заполнение страниц.

Широкий индекс может оставаться высотой в несколько уровней, но занимать гигабайты и вытеснять полезные страницы таблиц из buffer pool или shared buffers.

Перед добавлением очередной колонки полезно определить её роль: сужение диапазона, продолжение сортировки, покрытие частого запроса, обеспечение уникальности или ускорение JOIN. Колонка без конкретного сценария требует измерения до изменения production-схемы.

Дубликаты меняют плотность листьев и объём прохода

Индекс по колонке status может содержать несколько значений:

cancelled
new
paid
shipped

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

PostgreSQL умеет дедуплицировать повторяющиеся ключи B-tree в подходящих случаях: одна запись ключа может хранить список TID. Такая упаковка уменьшает размер листьев для колонок с множеством дубликатов. Уникальные индексы и некоторые конфигурации имеют ограничения для этой оптимизации.

Даже компактный индекс обязан вернуть все совпадения. Запрос WHERE status = 'paid' по таблице из десяти миллионов оплаченных заказов выполняет большой объём работы. Дедупликация снижает размер структуры, но не превращает массовую выборку в точечный поиск.

Коллация определяет порядок строковых ключей

Строковый B-tree сортирует значения по правилам collation и операторного класса. Порядок может учитывать локаль, регистр, диакритические знаки, числовые фрагменты, двоичное представление и версию библиотеки сравнения.

Индекс, построенный для одного порядка, обслуживает операции, совместимые с этим порядком. Запрос с другой collation может потребовать отдельной сортировки или другого индекса.

Префиксный LIKE тоже связан с правилами сравнения. PostgreSQL указывает, что шаблон col LIKE 'foo%' может использовать B-tree при подходящей operator class. В локалях за пределами C для некоторых типов нужен специальный класс, например text_pattern_ops.

CREATE INDEX idx_users_name_pattern
    ON users (name text_pattern_ops);

Полнотекстовый поиск, морфология и вхождение подстроки требуют других структур: GIN, GiST, полнотекстовых индексов, триграмм или специализированного поискового движка.

NULL получает определённое место в порядке

B-tree должен упорядочить NULL относительно остальных значений. PostgreSQL по умолчанию хранит записи B-tree по возрастанию с NULLS LAST. Обратный проход соответствует убыванию с NULLS FIRST.

Порядок можно задать явно:

CREATE INDEX idx_tasks_due
    ON tasks (due_at ASC NULLS FIRST);

Такой индекс полезен, когда интерфейс регулярно показывает задачи без срока в начале списка.

Условие:

WHERE due_at IS NULL

может использовать B-tree. Польза зависит от доли NULL. Если почти все строки имеют NULL, последовательное чтение может получить меньшую стоимость.

B-tree хорошо работает с одной упорядочиваемой осью

B-tree требует линейного отношения порядка: один ключ меньше, равен или больше другого. Такая модель естественна для идентификаторов, чисел, дат, денежных значений, строк, версий и составных кортежей.

Координата на карте содержит минимум две оси. Полигон занимает область. Обычная лексикографическая сортировка (x, y) плохо отвечает на запросы пересечения, вложенности и ближайшего соседа. Для таких задач используют R-tree, GiST, SP-GiST и другие пространственные методы. Отдельный гайд по пространственным индексам показывает поиск по карте, радиусу и полигонам.

Массивы, JSON-наборы, полнотекстовые токены и геометрии требуют операторов, которые обычный B-tree не моделирует напрямую. Тип запроса определяет индексную структуру.

Пагинация по ключу использует сильные стороны дерева

Смещение:

SELECT id, created_at
FROM events
ORDER BY created_at DESC, id DESC
LIMIT 50 OFFSET 500000;

заставляет движок пройти или обработать большое число предыдущих записей. B-tree способен отдавать их в порядке, но полмиллиона позиций остаются работой.

Keyset pagination использует последнюю пару предыдущей страницы:

SELECT id, created_at
FROM events
WHERE (created_at, id) < (
    TIMESTAMPTZ '2026-07-17 10:30:00+00',
    812345
)
ORDER BY created_at DESC, id DESC
LIMIT 50;

Индекс:

CREATE INDEX idx_events_created_id
    ON events (created_at DESC, id DESC);

дерево позиционируется около переданной границы и читает следующие 50 записей. id служит стабильным вторичным ключом для одинаковых временных меток.

Условия применимости:

• порядок должен быть детерминированным;
• курсор хранит все поля сортировки;
• направление сравнения совпадает с порядком;
• изменения между запросами страниц могут влиять на видимость данных;
• переход к произвольному номеру страницы требует отдельной стратегии.

JOIN использует B-tree для повторяющихся точечных поисков

SELECT o.id, c.name
FROM orders AS o
JOIN customers AS c
  ON c.id = o.customer_id
WHERE o.created_at >= '2026-07-01';

Nested loop join может получить очередной заказ, взять customer_id, найти клиента по B-tree первичного ключа и повторить этот путь для следующих заказов. Такой план эффективен, когда внешняя сторона возвращает ограниченное число строк, а внутренний поиск точный.

Большой внешний набор создаёт тысячи или миллионы обращений. Оптимизатор может выбрать hash join или merge join. Индекс на внешнем ключе нужен и для обратных запросов:

SELECT *
FROM orders
WHERE customer_id = 123;

Во многих СУБД объявление внешнего ключа не создаёт индекс автоматически на дочерней колонке. Его добавляют по фактическим JOIN, удалению родительских строк и проверкам ссылочной целостности.

Конкурентные операции требуют больше механики, чем учебное дерево

В рабочей базе несколько сессий одновременно ищут, вставляют и удаляют ключи. Разбиение страницы не должно заставить читателя пропустить запись или попасть в повреждённую ветку.

Промышленные реализации применяют короткие защёлки страниц, ссылки на соседей, верхние ключи страниц, WAL или redo log, версии страниц, повторную проверку позиции и протоколы восстановления после сбоя.

Алгоритм Lehman–Yao, используемый PostgreSQL, позволяет поиску двигаться вправо после обнаружения, что целевая страница была разделена конкурентной транзакцией. Ссылка на правого соседа и high key сохраняют корректный путь.

SQL-разработчику редко приходится управлять этой механикой напрямую. Она объясняет, почему создание, перестройка и массовая запись индекса имеют собственные режимы блокировок и могут влиять на задержки других транзакций.

Построение B-tree читает таблицу, сортирует ключи и записывает страницы

Создание индекса на большой таблице включает чтение строк, вычисление ключей, сортировку, формирование листьев, построение верхних уровней, запись индекса и синхронизацию с параллельными изменениями в онлайн-режиме.

PostgreSQL:

CREATE INDEX idx_orders_created
    ON orders (created_at);

обычно блокирует конкурентные записи на время стандартного построения. Онлайн-вариант:

CREATE INDEX CONCURRENTLY idx_orders_created
    ON orders (created_at);

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

MySQL 8.4 поддерживает online DDL для многих операций InnoDB, но доступный алгоритм и уровень блокировки зависят от конкретного изменения. План миграции проверяют на той же версии, формате таблицы и объёме данных.

Для production оценивают длительность, временное место для сортировки, рост WAL или redo, репликационный лаг, нагрузку на накопитель, блокировки, возможность отмены и план удаления неудачного индекса.

Статистика связывает форму B-tree с решением планировщика

Дерево знает реальные ключи. Планировщик до выполнения запроса работает с оценками:

• число строк таблицы;
• число различных значений;
• доля NULL;
• наиболее частые значения;
• распределение по гистограмме;
• корреляция физического и логического порядка;
• зависимости между колонками;
• размеры таблицы и индексов.

PostgreSQL обновляет статистику через ANALYZE и autovacuum:

ANALYZE orders;

MySQL:

ANALYZE TABLE orders;

SQLite:

ANALYZE;

После массовой загрузки, большого удаления или резкого изменения распределения старые оценки могут расходиться с реальностью.

Признак проблемы в PostgreSQL:

rows=100
actual rows=500000

Планировщик ожидал сто записей и выбрал повторяющиеся индексные обращения. Фактический набор оказался в пять тысяч раз больше. Причина может лежать в статистике, корреляции колонок, параметрах или устаревших данных.

Корреляция физического порядка меняет цену индексного сканирования

Таблица журнала вставляется по времени. Физические страницы примерно следуют created_at. Диапазонный индексный проход по дате получает TID, расположенные близко друг к другу. Чтение похоже на последовательное.

Индекс по случайному user_id возвращает TID из разных частей таблицы. Один и тот же объём строк требует посещения большего числа страниц.

PostgreSQL хранит статистическую корреляцию и учитывает её при оценке Index Scan. InnoDB кластеризует строки по первичному ключу, поэтому вторичный диапазон, слабо связанный с первичным порядком, может инициировать много переходов к кластерному дереву.

Покрытие, bitmap-сканирование и Multi-Range Read уменьшают отдельные эффекты. Порядок индекса и расположение строк вместе определяют I/O.

Индексный скан и bitmap-скан обслуживают разные объёмы результата

PostgreSQL предлагает два распространённых пути.

Index Scan читает запись B-tree и почти сразу обращается к heap. Он подходит для небольшого числа строк, точного порядка и запросов с LIMIT.

Bitmap Index Scan сначала собирает битовую карту адресов. Затем Bitmap Heap Scan читает heap-страницы группами. Порядок индекса обычно теряется, поэтому ORDER BY может потребовать сортировки.

Пример сочетания отдельных индексов:

CREATE INDEX idx_orders_tenant ON orders (tenant_id);
CREATE INDEX idx_orders_status ON orders (status);

SELECT *
FROM orders
WHERE tenant_id = 7
  AND status = 'paid';

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

Избыточные индексы расходуют запись и память

Есть индексы:

(a)
(a, b)
(a, b, c)

Индекс (a, b, c) способен обслуживать часть запросов по a и (a, b). Первые два индекса могут сохранять пользу для более узких запросов.

Узкий (a) занимает меньше места, имеет более высокую ветвистость, быстрее помещается в кеш и может дать более дешёвый bitmap-план. Широкий (a, b, c) покрывает больше условий, поддерживает дополнительный порядок и может убрать обращение к таблице, но дороже обновляется.

Решение принимают по статистике использования, планам, размеру и нагрузке записи. В PostgreSQL помогают pg_stat_user_indexes, pg_relation_size() и pg_indexes_size(). Счётчик редкого использования интерпретируют с учётом перезапуска статистики, сезонных задач и индексов ограничений.

Типичные ошибки становятся понятными через порядок дерева

Индекс создан на колонку с массовым результатом

CREATE INDEX idx_orders_status ON orders (status);

Запрос по самому частому статусу получает миллионы строк. Начало группы находится быстро, чтение группы остаётся большим.

Составной индекс начинается с отсутствующей в запросе колонки

INDEX (tenant_id, created_at)
WHERE created_at >= ...

Даты разбросаны по группам арендаторов. Skip scan может появиться только при подходящих условиях и статистике.

Функция скрывает исходный порядок

WHERE DATE(created_at) = '2026-07-17'

Диапазон по исходному timestamp или индекс на выражении даёт планировщику упорядочиваемый ключ.

Ведущий шаблон уничтожает известную границу

WHERE name LIKE '%server%'

Обычный B-tree не знает начало искомого диапазона. Для PostgreSQL часто подходит pg_trgm с GIN или GiST.

Индекс покрывает фильтр и ломает нужный порядок

INDEX (tenant_id, status, created_at)
WHERE tenant_id = ?
ORDER BY created_at DESC

Разные значения status создают отдельные группы дат. Общая лента арендатора требует сортировки или индекса (tenant_id, created_at DESC).

В индекс добавлены все колонки SELECT

Листовые записи становятся широкими, дерево растёт, вставки дорожают. Покрытие окупается у частых запросов с измеримым снижением heap или clustered lookup.

План проверен на пустой таблице

Десять строк почти всегда дают дешёвый полный скан. Тестовый набор должен отражать объём, распределение, долю NULL, повторяемость значений и реальные параметры.

Проверка нового B-tree проходит от запроса к метрикам

Шаг 1 — зафиксировать семейство запросов

Запишите реальные формы WHERE, JOIN, ORDER BY, LIMIT и список SELECT. Один индекс проектируют под повторяющееся семейство, а не под название колонки.

Шаг 2 — определить порядок ключа

Для каждого условия отметьте равенство, диапазон, сортировку, группировку, возвращаемые поля и уникальность. Равенства и ведущий диапазон определяют область дерева. Сортировка задаёт последовательность. Поля покрытия влияют на ширину.

Шаг 3 — измерить исходный план

PostgreSQL:

EXPLAIN (ANALYZE, BUFFERS)
SELECT ...;

MySQL:

EXPLAIN ANALYZE
SELECT ...;

SQLite:

EXPLAIN QUERY PLAN
SELECT ...;

Сохраните время, строки, чтения и сортировки.

Шаг 4 — создать индекс в тестовой среде

Проверьте размер, время построения, изменение плана, задержку чтения, задержку записи, поведение с разными параметрами, холодный и тёплый кеш.

Шаг 5 — повторить тест на распределении production

Полезный набор включает частое значение, редкое значение, пустой результат, маленький диапазон, широкий диапазон, разные LIMIT, свежие и старые даты, разных арендаторов и NULL, если он встречается.

Шаг 6 — проверить конкуренцию

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

Шаг 7 — наблюдать после выпуска

Следите за p95 и p99 задержкой, чтением блоков, размером индекса, частотой сканов, WAL или redo, репликационным лагом и временем DML.

Короткая памятка по B-tree

Источники и документация

• PostgreSQL 18 — типы индексов и возможности B-tree
• PostgreSQL 18 — многоколоночные индексы и skip scan
• PostgreSQL 18 — индексы и ORDER BY
• PostgreSQL 18 — Index Only Scan и INCLUDE
• PostgreSQL — реализация конкурентного B-tree Lehman–Yao
• MySQL 8.4 — многоколоночные индексы и левый префикс
• MySQL 8.4 — кластерный и вторичные индексы InnoDB
• MySQL 8.4 — EXPLAIN и EXPLAIN ANALYZE
• SQLite — формат B-tree в файле базы данных
• SQLite — EXPLAIN QUERY PLAN

B-tree превращает порядок ключей в предсказуемый путь к данным

B-tree ускоряет запрос, когда условие можно выразить через упорядоченный ключ: точное значение, непрерывный диапазон, подходящий префикс или нужную последовательность сортировки. Низкая высота сокращает число посещённых страниц, а связанный листовой уровень делает диапазонный проход последовательным.

Первый практический ориентир — взять медленный запрос, выписать его равенства, первый диапазон, ORDER BY и LIMIT, затем сопоставить их с фактическим порядком ключей в B-tree. План EXPLAIN ANALYZE покажет, какая часть условия стала навигацией по дереву, сколько записей осталось фильтровать и окупает ли индекс стоимость своего обслуживания.