Что такое B-tree индекс
На этой странице
B-tree — сбалансированное дерево, в листьях которого ключи хранятся в отсортированном порядке вместе с указателями на строки таблицы (TID), а листья связаны в список. Высота дерева обычно 3–4 уровня даже для сотен миллионов строк, поэтому поиск — это несколько чтений страниц. Благодаря упорядоченности B-tree поддерживает равенство, диапазоны (<, >, BETWEEN), IN, IS NULL, сортировку (ORDER BY без отдельного шага Sort, в том числе в обратном направлении), min/max и префиксный LIKE 'abc%' (при подходящем collation/operator class). Это тип индекса по умолчанию в PostgreSQL, на нём основаны PK и UNIQUE. Не подходит для поиска подстроки, содержимого jsonb и массивов — там нужны GIN/GiST.
Вопрос
Как устроен B-tree индекс и какие запросы он ускоряет?
Структура
[ 50 | 100 ] ← корень
/ | \
[10 | 30] [60 | 80] [120 | 150] ← внутренние узлы
/ | \ / | \ / | \
листья: 1..9 ↔ 10..29 ↔ 30..49 ↔ 50..59 ↔ ... ← отсортированные ключи + TID, связаны в списокПоиск id = 75: корень → узел [60 | 80] → лист → TID → строка таблицы (heap).
Какие условия поддерживает
| Условие | Работает |
|---|---|
col = $1, col IN (...), col = ANY($1) | Да |
col > $1, BETWEEN, >= и < | Да, сканирование диапазона по листьям |
ORDER BY col [DESC] LIMIT n | Да, без сортировки |
col IS NULL | Да |
col LIKE 'abc%' | Да при C collation или text_pattern_ops |
col LIKE '%abc%', jsonb @>, array @> | Нет — GIN |
lower(col) = $1 | Только индекс по выражению lower(col) |
Создание
CREATE INDEX orders_created_at_idx ON orders (created_at);
CREATE INDEX products_title_pattern_idx ON products (title text_pattern_ops); -- для LIKE 'abc%' при не-C collationIndex Scan, Index Only Scan, Bitmap
| Узел плана | Когда |
|---|---|
| Index Scan | Мало строк: идём по индексу и для каждой читаем строку из таблицы |
| Index Only Scan | Все нужные столбцы есть в индексе (covering index) |
| Bitmap Index Scan + Bitmap Heap Scan | Много строк: собираем битовую карту страниц, затем читаем их по порядку; можно объединять несколько индексов (BitmapAnd/Or) |
| Seq Scan | Нужна большая часть таблицы — дешевле прочитать всё подряд |
Сложность
| Операция | Без индекса | B-tree |
|---|---|---|
| Поиск по ключу | O(n) | O(log n) |
| Диапазон из k строк | O(n) | O(log n + k) |
| Вставка | O(1) в heap | + O(log n) на каждый индекс |
Особенности PostgreSQL
- Дедупликация повторяющихся ключей (PG 13+) делает B-tree на неуникальных столбцах компактнее.
- Индекс хранит указатели на версии строк; из-за MVCC после массовых
UPDATEиндекс может раздуваться — помогаетREINDEX CONCURRENTLY. - Порядок
DESC/NULLS FIRSTможно задать при создании: важно для составных индексов со смешанной сортировкой.
Частые ошибки
- Ожидать, что B-tree поможет
LIKE '%abc%'. - Функция над столбцом в условии при индексе по столбцу.
- Индекс на столбец с двумя значениями (boolean) — почти всегда бесполезен, лучше частичный индекс.
Что важно помнить
- B-tree — отсортированное сбалансированное дерево.
- Поддерживает равенство, диапазоны, сортировку и
min/max. - Для подстрок, JSON и массивов — другие типы индексов.
Мини-шпаргалка
CREATE INDEX ... ON t (col)— B-tree по умолчанию.=,<,>,BETWEEN,IN,IS NULL,ORDER BY.text_pattern_ops— префиксныйLIKE.REINDEX CONCURRENTLY— при раздувании.