Что внутри индекса: B-дерево и откуда берутся его естественные пределы

MAATRIX

Когда вы создаёте индекс командой CREATE INDEX, база молча строит внутри себя отдельную структуру данных — B-дерево. Большинство разработчиков пользуются им годами, ни разу не заглянув внутрь, и удивляются, когда индекс «не помогает»: запрос с двумя условиями всё равно сканирует таблицу, а LIKE '%слово%' не ускоряется вообще. Причина не в том, что индекс сломан, а в том, что B-дерево спроектировано для одной конкретной задачи и за её пределами не работает, как бы вы его ни настраивали.

Зачем базе вообще нужна отдельная структура для поиска

Без индекса база находит строку по условию WHERE id = 42 единственным способом — читает таблицу целиком, строку за строкой, и сравнивает значение в каждой. Это называется последовательным сканированием (sequential scan). Время работы растёт прямо пропорционально размеру таблицы: вдвое больше строк — вдвое дольше скан.

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

Отсортированный массив решает первые две задачи — поиск в нём делается бинарным поиском за логарифмическое время. Но вставка в середину требует сдвинуть половину элементов, и с ростом таблицы это дорожает. Связный список решает проблему вставки, но убивает бинарный поиск — до элемента нельзя допрыгнуть, к нему нужно идти по ссылкам одну за другой. B-дерево — компромисс, который держит и поиск, и вставку на логарифмической сложности, да ещё и укладывается в то, как физически читаются данные с диска. Это не единственная возможная структура для индексов (дальше — про альтернативы), но именно она стала стандартом по умолчанию в PostgreSQL, MySQL/InnoDB, SQL Server, Oracle и большинстве других СУБД.

Анатомия B-дерева: как устроены узлы и почему оно «сбалансированное»

B-дерево — это не бинарное дерево, хотя название сбивает с толку. В классическом двоичном дереве поиска у каждого узла максимум два потомка. В B-дереве узел хранит сразу много ключей — обычно столько, сколько помещается в одну страницу (page) данных, которую база читает с диска за одну операцию. В PostgreSQL страница индекса по умолчанию занимает 8 КБ, и в неё помещается заметно больше одного ключа: сколько именно — зависит от размера индексируемого значения (короткое целое число даёт больше ключей на странице, чем длинная строка).

Узел B-дерева выглядит так:

[указатель] ключ1 [указатель] ключ2 [указатель] ключ3 [указатель]

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

Ключевое слово в названии — «сбалансированное». У всех листьев одна и та же глубина от корня, и это не случайность, а инвариант, который дерево поддерживает активно. Когда узел переполняется при вставке, он расщепляется на два, а средний ключ поднимается на уровень выше и становится разделителем в родительском узле; если переполняется и родитель — расщепление каскадом идёт вверх, вплоть до корня, и тогда высота дерева увеличивается на единицу сразу для всех веток, а не для одной. При удалении, когда узел становится слишком пустым, происходит обратная операция — слияние соседних узлов или заимствование ключа у соседа. Это и есть механизм, который не даёт дереву выродиться в перекошенный список: обычное бинарное дерево поиска можно довести до фактического связного списка последовательной вставкой уже отсортированных данных, а у B-дерева расщепление и слияние встроены в саму вставку и удаление и гарантируют баланс всегда, а не «в среднем при удачных данных».

Листовые узлы B-дерева (а в PostgreSQL и в большинстве других реализаций — ещё и узлы одного уровня) связаны между собой в цепочку указателей «следующий/предыдущий». Без этой детали B-дерево было бы бесполезно для диапазонных запросов: дойдя до первого подходящего листа, база не спускается с корня заново за следующим значением — она идёт по цепочке листьев вправо или влево.

Почему поиск требует логарифмического, а не линейного числа сравнений

Вот тут и находится главный выигрыш индекса. Пусть в узле помещается b ключей (branching factor, коэффициент ветвления). Тогда на каждом уровне число узлов увеличивается примерно в b раз, а высота дерева, необходимая для хранения N значений, растёт как log_b(N). Практический смысл: чтобы найти значение, не нужно сравнивать его со всеми N строками таблицы — нужно спуститься с корня до листа, то есть сделать число сравнений, пропорциональное высоте дерева.

Разница между линейной и логарифмической зависимостью — не количественная, а качественная. При линейном сканировании увеличение таблицы в 10 раз означает примерно десятикратное увеличение времени поиска. При логарифмическом поиске по B-дереву тот же рост добавляет высоте дерева буквально пару уровней, потому что log_b(10·N) = log_b(N) + log_b(10), а log_b(10) — константа, не зависящая от N. Чем выше коэффициент ветвления b (а страничная организация как раз даёт высокий b — десятки и сотни ключей на узел, а не два, как в бинарном дереве), тем медленнее растёт высота дерева с ростом N.

Практически высота дерева примерно равна числу операций чтения страницы, которые нужны, чтобы дойти от корня до листа с искомым значением — не считая того, что верхние уровни дерева почти всегда уже лежат в кеше страниц базы, потому что они маленькие и к ним постоянно обращаются. Точное число уровней зависит от объёма данных, размера ключа и настроек конкретной базы — конкретную цифру для своей таблицы даст только EXPLAIN, — но принцип один: рост числа операций чтения при росте таблицы кардинально медленнее, чем рост самой таблицы. Это и есть разница между «база отвечает стабильно на любом объёме» и «база всё медленнее отвечает по мере роста таблицы», которую вы видите на практике после добавления индекса на внешний ключ или на столбец фильтрации.

Диапазон и сортировка: где B-дерево работает лучше всего

B-дерево — не только про точечный поиск WHERE id = 42. Благодаря упорядоченности ключей и связке листьев в цепочку оно отлично справляется и с диапазонными запросами: WHERE created_at BETWEEN '2026-08-01' AND '2026-08-31' или WHERE price > 1000. База спускается к первому подходящему значению за логарифмическое число шагов, а дальше идёт по цепочке листьев вправо, пока не выйдет за границу диапазона — без повторных спусков от корня.

Та же особенность даёт бесплатную сортировку: если запрос требует ORDER BY по тому же столбцу, что и в индексе (в прямом направлении или в обратном — дерево обходится в обе стороны), база отдаёт строки в порядке обхода листьев, не выполняя отдельный шаг сортировки. В плане запроса это видно сразу: вместо Sort появляется Index Scan, который уже отдаёт данные в нужном порядке.

Композитный (многоколоночный) индекс — B-дерево, где ключ составной: (город, дата). Такие ключи упорядочены лексикографически, сначала по первому столбцу, потом по второму внутри одинаковых значений первого — как в телефонной книге сначала по фамилии, потом по имени. Отсюда правило leftmost prefix: индекс (город, дата) эффективно ускоряет запросы по город и по город + дата, но не ускоряет поиск только по дата — значения даты упорядочены не глобально, а лишь локально, внутри каждого города. Это не ограничение реализации, а прямое следствие того, как устроен порядок ключей в дереве.

О том, как индекс встраивается в план запроса и когда планировщик решает его не использовать — в статьях как индекс ускоряет запрос и когда замедляет и почему статистики после загрузки данных ещё нет.

Естественный предел: несколько независимых признаков одновременно

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

Представьте таблицу заказов и запрос WHERE status = 'paid' AND city = 'Москва' AND courier_id = 17. У каждого из трёх условий — своя независимая кардинальность (число уникальных значений). Индекс — это один порядок ключей. Композитный индекс (status, city, courier_id) идеально ускорит именно этот запрос. Но стоит другому запросу искать по city и courier_id, не трогая status, — и leftmost prefix уже не сработает так же хорошо, потому что первым столбцом в индексе стоит status, а не city.

Отсюда растёт классическая проблема: под реальное приложение с десятком фильтров в разных комбинациях нельзя построить один индекс на все случаи. Комбинаций слишком много, а каждый лишний индекс — отдельная структура, которую нужно обновлять при каждой вставке, удалении и изменении строки, и которая занимает место на диске. На практике выбирают несколько самых частых комбинаций фильтров и строят композитные индексы под них, смиряясь с тем, что редкие комбинации читают больше данных, чем хотелось бы, либо база пересечёт результаты нескольких одноколоночных индексов (bitmap index scan умеет объединять их через побитовое AND/OR) — это работает, но не так эффективно, как один точный композитный индекс.

Тот же эффект объясняет, почему индекс по низкоселективному столбцу — например, status с тремя возможными значениями на миллион строк — часто бесполезен сам по себе: диапазон в дереве под одно значение status всё равно охватывает треть таблицы, и планировщик резонно решает, что дешевле прочитать таблицу целиком, чем прыгать по индексу и таблице поочерёдно для сотен тысяч подходящих строк.

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

У B-дерева есть предположение, зашитое в саму идею упорядоченного ключа: каждому значению соответствует один чёткий порядок сравнения — меньше, равно, больше. Это отлично работает для чисел, дат, коротких строк вроде email. И совсем не работает для полнотекстового поиска.

Возьмём столбец с текстом статьи и запрос «найти строки, где встречается слово „сервер“». В тексте это слово может быть где угодно — в начале, середине, конце. У текста как единого значения нет одного «места в алфавите», которое можно упорядочить и найти бинарным поиском: LIKE '%сервер%' с маской в начале вообще не может использовать упорядоченность B-дерева, потому что неизвестно, с чего начинается совпадение. Даже LIKE 'сервер%' без начальной маски использует B-дерево лишь частично — как поиск по префиксу.

Для этого нужна принципиально другая структура — инвертированный индекс: вместо «строка → её значение» он хранит «слово (токен) → список строк, где оно встречается». Это делает GIN (Generalized Inverted Index) в PostgreSQL поверх tsvector, полнотекстовые индексы MySQL, специализированные системы вроде Elasticsearch и Meilisearch: текст разбивается на токены (снятие окончаний, нижний регистр, фильтрация стоп-слов), а дальше строится структура, которая для каждого токена быстро находит список содержащих его строк. GIN, кстати, тоже использует B-дерево внутри себя — но не для самого текста, а для упорядоченного списка уникальных токенов; сам текст в него напрямую не укладывается.

Похожая история с сортировкой по критерию, которого нет ни в одном индексе — например, ORDER BY similarity_score при полнотекстовом или векторном поиске, где релевантность вычисляется на лету под конкретный запрос. У такого критерия нет заранее известного порядка, который можно было бы зафиксировать в дереве: он зависит от самого запроса, а не только от данных в строке. База обязана вычислить критерий для подходящих строк и отсортировать результат отдельным шагом — индекс тут ускоряет только предварительный отбор кандидатов, а не саму сортировку по вычисляемому значению.

Для поиска по векторным эмбеддингам существуют свои структуры (HNSW, IVFFlat в pgvector) — тоже не B-деревья, потому что задача другая: не «найти совпадение или диапазон по одному числу», а «найти ближайшие по расстоянию в многомерном пространстве». Если в проекте нужен и обычный реляционный поиск, и полнотекстовый или векторный, держать под них разные типы индексов на одной базе — это нормально, а не ошибка проектирования. Подробнее — в материале почему гибридный поиск часто нужен даже там, где, казалось бы, хватило бы одних векторов: разные задачи поиска требуют разных структур данных.

Частые вопросы