B-tree на пальцах: почему поиск логарифмический

В предыдущем уроке мы сказали: «B-tree даёт log(N) вместо O(N)». Это не магия и не маркетинг — это прямое следствие того, как устроена структура. В этом уроке мы разберём её на интуитивном уровне: достаточно, чтобы понимать, почему индекс работает, и недостаточно, чтобы спорить с автором PostgreSQL о реализации. Глубокая часть — про страницы, B-link-tree, HOT updates — это уже следующий курс.

Зачем разработчику вообще знать про B-tree? Не для того, чтобы реализовать его руками — этим занимается команда PostgreSQL. А для того, чтобы понимать что хорошо и что плохо для индекса: почему диапазонные запросы быстрые, почему LIKE 'x%' работает, а LIKE '%x' — нет; почему ORDER BY по индексированной колонке бесплатен, а по неиндексированной стоит дорого. Все эти ответы вытекают из устройства B-tree, и если знать его на уровне картинки, ответы становятся очевидными.

B-tree — это упорядоченное дерево

B-tree (читается «би-три», иногда «би-дерево») — это

сбалансированное дерево поиска

, в котором:

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

Это три ключевых свойства. Из них всё дальнейшее выводится.

B-tree: дерево с упорядоченными ключами

Корень делит весь диапазон на части. Ветки делят свои части ещё мельче. Листья содержат ссылки на строки таблицы.

root[ 50 | 100 ]

branch[ 20 | 35 ]

leaf1,5,10 → row*

leaf22,28,33 → row*

leaf36,40,48 → row*

branch[ 70 | 85 ]

leaf55,60,68 → row*

leaf71,78,82 → row*

leaf86,90,98 → row*

branch[ 120 | 140 ]

leaf105,115,118 → row*

leaf121,128,135 → row*

leaf142,150,160 → row*

Каждый узел содержит несколько «разделителей» (на диаграмме — 50 и 100 в корне) и указатели на детей. «Меньше 50 → налево, 50-100 → в середину, больше 100 → направо». В реальности в одном узле сотни таких разделителей и детей — это high fan-out. Именно он делает дерево очень низким, как мы сейчас увидим.

Откуда берётся log(N)

Спуск по дереву — это серия выборов «в какую ветку идти», по одному выбору на каждый уровень. Если высота дерева — H, то и поиск стоит H операций.

Как меняется H, когда таблица растёт? Если в каждом узле помещается F разделителей (то есть F+1 веток), то дерево из H уровней покрывает $F^H$ ключей. Решаем обратно: $H = \log_F(N)$ .

Берём типичные числа для PostgreSQL: страница 8 КБ, средний ключ ~16 байт, в страницу влезает ~250 разделителей. Тогда:

H = 1: 250 ключей
H = 2: 62 500 ключей
H = 3: 15 миллионов ключей
H = 4: 3.9 миллиарда ключей

То есть четырёх обращений к диску достаточно, чтобы найти строку в таблице на 4 миллиарда записей. Это и есть «log(N) — это очень мало». На практике первые 2-3 уровня кешируются в RAM, и реальный поиск стоит 1-2 чтения с диска.

High fan-out — главное отличие B-tree от классического бинарного дерева поиска

. БД оптимизирует не общее число операций, а число обращений к диску: они на порядки дороже, чем сравнение чисел в памяти.

Поиск по равенству: как идём от корня к листу

Запрос: «найди строку с ключом 78».

Открываем корень. Видим разделители: 50 и 100. 78 попадает в диапазон 50-100 — спускаемся в среднюю ветку.
В этой ветке разделители: 70 и 85. 78 в диапазоне 70-85 — спускаемся в средний лист.
В листе ключи: 71, 78, 82. Находим 78. Берём указатель на строку в таблице.
По указателю читаем саму строку из heap (так в PostgreSQL называется основное хранилище таблицы).

Четыре шага: корень → ветка → лист → heap. И это работает одинаково для таблицы на 100 строк и на миллиард — структура подстраивает высоту автоматически.

Диапазонные запросы: листья связаны в список

Главный бонус B-tree, который отличает его от хеш-таблицы:

листья связаны между собой

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

Это делает диапазонный поиск тоже быстрым:

SELECT * FROM customers WHERE id BETWEEN 100 AND 200;

Спускаемся к ключу 100 — log(N) шагов.
Читаем ключ 100, 101, 102, …, пока не вылетим за 200 — это уже линейно, но только по найденному диапазону, а не по всей таблице.
Для каждого ключа достаём строку из heap.

Стоимость: $O(\log N + k)$ , где k — размер найденного диапазона. Если по запросу попадает 100 строк из миллиарда — суммарно ~20 операций, а не миллиард.

То же самое работает для ORDER BY по индексированной колонке: проход по листьям уже идёт в порядке возрастания ключа, не нужна отдельная сортировка.

Диапазонный поиск: 100 ≤ id ≤ 200

Спустились по дереву до ключа 100. Дальше идём по связному списку листьев — log(N) на спуск, потом линейно до конца диапазона.

root → ... → leafспуск за log(N)

нашлиключ 100

→

leaf →100, 101, 102 ...

leaf →...150, 160...

leaf195, 198 → стоп

Что происходит при вставке

В обратную сторону: когда мы делаем INSERT INTO customers (...) VALUES (...), PostgreSQL:

Вставляет строку в heap.
Для каждого индекса на таблице — спускается по дереву до нужного листа.
Кладёт в лист пару (ключ, указатель_на_строку).
Если лист переполнен — разбивает его пополам, обновляет родителя.
Если родитель тоже переполнен — разбивает и его. И так до корня.

Эти разбиения и есть та цена за поддержание дерева сбалансированным, о которой мы говорили в прошлом уроке. Чаще всего разбиения локальные — затрагивают один-два уровня. Но в худшем случае разбиение может дойти до корня — и тогда дерево вырастает на один уровень. На больших таблицах это редкое событие, но именно оно гарантирует, что высота дерева остаётся $O(\log N)$ навсегда, что бы ты в него ни вставлял.

Детали — какой именно процент заполнения страницы вызывает split, как работает

HOT updates

, что такое page bloat — всё это в следующем курсе. Сейчас достаточно интуиции: «вставка стоит O(log N), и иногда дерево перестраивается».

Split: что происходит при переполнении листа

Лист переполнен — он делится пополам, ключ-разделитель уезжает в родителя. Если родитель тоже переполнен — split идёт вверх, до самого корня. В крайнем случае дерево растёт на уровень.

до splitполный лист

leaf[10, 20, 30, 40, 50, 60, 70, 80]

после splitразделение пополам

leaf left[10, 20, 30, 35]

leaf right[40, 50, 60, 70, 80]

parentтеперь содержит разделитель 40

Сортировка ключей: что значит «упорядоченные»

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

Для чисел всё очевидно: 1 < 2 < 3. Для текста — лексикографически, посимвольно. Но есть нюансы:

Collation
— порядок строк зависит от языка. 'apple' < 'banana' в любой локали, но 'ABC' < 'abc' или 'abc' < 'ABC' — зависит от настроек. Индекс хранит данные в порядке collation, и при сравнении использует ту же collation. Если запрос использует другую — индекс не поможет.
NULL — в PostgreSQL NULL сортируется после всех остальных значений (NULLS LAST по умолчанию для ORDER BY ASC). Это влияет и на порядок в индексе.
Композитные ключи сортируются лексикографически по компонентам: сначала по первой колонке, при равенстве — по второй, и так далее. Это базис для leftmost prefix rule (урок 4).

Когда тебе кажется, что индекс «должен использоваться, но не используется» — иногда дело в неявной разнице collation между колонкой и литералом. Это редкий, но коварный случай.

Смотрим, как индекс выглядит в PostgreSQL

PostgreSQL предоставляет системные view, через которые можно увидеть, какие индексы есть и сколько они занимают.

Создадим пару индексов и посмотрим, что у PostgreSQL внутри:

PostgreSQL

На крошечной вселенной размеры будут смешные — байты, не килобайты. Но представь те же запросы на таблице в миллиард строк: индекс customers_email_key мог бы занимать гигабайт. Это не страшно, но это реальный объём, который надо иметь в бюджете.

А теперь посмотрим, что меняется в плане запроса по id (PRIMARY KEY автоматически создаёт индекс):

Поиск по PRIMARY KEY — индекс уже есть, и это будет видно в плане:

PostgreSQL

В выводе ты увидишь либо Index Scan using customers_pkey, либо Seq Scan (если таблица очень маленькая). На таблице из 12 строк PostgreSQL может решить, что Seq Scan быстрее — это совершенно нормально и не значит «индекс не работает». Это значит «индекс не нужен на таких объёмах», что само по себе ценная информация.

Что хеш-индекс не умеет

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

Hash-индекс

хранит хеши ключей и поэтому очень быстро ищет по равенству — O(1). Но у него есть фатальный недостаток: он не умеет диапазонный поиск. WHERE x > 100 через хеш-индекс не работает — в хеш-таблице соседние ключи лежат хаотически, нет понятия «следующий».

ORDER BY через хеш-индекс тоже не работает по той же причине. Поэтому в большинстве СУБД индекс по умолчанию — B-tree, а хеш используется только в очень узких сценариях.

B-tree vs Hash — кто что умеет

B-tree универсален. Hash быстрее на точечных запросах, но не умеет ничего, кроме равенства.

B-treeдерево с упорядоченными ключами

=O(log N) — отлично

<, >, BETWEENO(log N + k) — отлично

LIKE 'x%'отлично (диапазон)

ORDER BYбесплатно (листья сорт.)

Hashхеш-таблица ключей

=O(1) — быстрее B-tree

<, >, BETWEENне поддерживается

LIKE 'x%'не поддерживается

ORDER BYне поддерживается

Как менялись B-trees исторически

Короткая историческая справка, потому что она объясняет, почему многие термины звучат немного по-разному в разных книгах:

B-tree (1972) — оригинальная статья Bayer и McCreight. Ключи и payload могут храниться и в листьях, и во внутренних узлах.
B+tree — модификация, где все payload только в листьях, а внутренние узлы содержат только разделители. Листья связаны в список. Это то, что используется в PostgreSQL, InnoDB MySQL, SQL Server.
B-link-tree — модификация B+tree с дополнительными ссылками между соседями, упрощающая параллельные операции. Это уже точное описание того, что внутри PostgreSQL.

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

Когда ширина важнее глубины

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

Что это означает на практике:

Индекс по bigint — очень компактен, очень быстр (тысячи fan-out).
Индекс по text со средней длиной 50 символов — fan-out ~150, дерево чуть выше.
Индекс по text со средней длиной 500 символов — fan-out ~15, дерево заметно выше.

Поэтому, когда выбираешь, по какой колонке делать FK + индекс, иногда стоит подумать: «а нельзя ли это сделать через integer surrogate key вместо длинного UUID?». На больших объёмах разница ощутима — как по объёму индекса, так и по скорости. Это

surrogate key

— стандартная практика проектирования для FK.

Проверка знанийKnowledge check

Таблица events на 100 миллионов строк, индекс по occurred_at. Запрос: SELECT * FROM events WHERE occurred_at BETWEEN '2025-01-01' AND '2025-01-31'. Этот запрос вернёт ~3 миллиона строк. PostgreSQL выберет Index Scan или Seq Scan?

ОтветAnswer

Скорее всего Seq Scan — и это правильно. 3 миллиона строк из 100 миллионов — это 3% таблицы. Index Scan стоит "log(N) + k×fetch_from_heap": для каждой из 3M строк нужно пойти по указателю в heap. А fetch_from_heap — это случайное чтение, оно медленнее, чем последовательное. Когда доля выбираемых строк превышает ~10%, Seq Scan почти всегда выигрывает, потому что он читает heap последовательно (хорошо для диска, хорошо для prefetch). Это контринтуитивный, но фундаментальный факт: индекс эффективен на маленькой выборке, на большой — нет. Если бы запрос фильтровал по дню, а не по месяцу — выборка стала бы ~0.1%, и Index Scan выиграл бы. Решает оптимизатор на основе статистики rows_per_value и подсказок про random_page_cost.

Что внутри одного узла B-tree

Финальный мазок к интуиции — что на самом деле лежит в узле дерева. Каждый узел — это страница диска (page) размером 8 КБ в PostgreSQL. Внутри page лежит:

Header (~24 байта) — служебная информация: тип узла (leaf / branch / root), счётчик ключей, ссылки на соседей.
Массив ключей и их разделителей — пары (ключ, ссылка). В leaf-узле ссылка — это TID на строку heap. В branch-узле — указатель на дочернюю страницу.
Свободное место — резервируется под будущие вставки. По умолчанию страница заполняется не на 100%, а на 90% (fillfactor).
Item pointers / line pointers — таблица смещений на массив ключей, чтобы можно было быстро прыгать на нужную позицию внутри страницы.

Когда PG делает поиск, он читает одну страницу (8 КБ за один disk I/O), внутри неё бинарным поиском находит нужный slot — и переходит на следующую страницу. Бинарный поиск внутри страницы — O(log F), но это в RAM и быстро.

Мы намеренно не углубляемся в эту физику здесь — для базовой интуиции хватит «узел = страница = много ключей». Но имей в виду: когда в выводе EXPLAIN ANALYZE видишь Buffers: shared hit=15 read=3, это значит «прочитал 15 страниц из RAM-кеша и 3 — с диска». Это и есть физические операции спуска по дереву.

Внутреннее устройство B-tree: страницы, split, fill factor Page splits и почему random INSERT медленнее sequential

Чек-лист

B-tree — сбалансированное дерево с упорядоченными ключами и высоким fan-out (сотни детей на узел).
Высота — $O(\log_F N)$ . Для F=250 и N=4 миллиарда — высота 4. Очень мало.
Поиск по равенству: спуск от корня к листу, затем чтение строки из heap.
Диапазонный поиск: спуск к началу диапазона, потом проход по связному списку листьев.
ORDER BY по индексированной колонке не требует отдельной сортировки — листья уже упорядочены.
Вставка — $O(\log N)$ со случайной перестройкой дерева; высота остаётся логарифмической.
Hash-индекс умеет только равенство, не умеет диапазон/ORDER BY — потому B-tree по умолчанию.
Узел B-tree = одна страница диска (~8 КБ); внутри неё ключи ищутся бинарно.
Collation влияет на порядок ключей в индексе — несовпадение collation между колонкой и запросом ломает использование индекса.
Глубокие детали (страницы, splits, HOT, MVCC) — следующий курс. Сейчас интуиции достаточно.