re:re:actable
Урок 023 минуты чтения

Что такое 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 collation

Index 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 — при раздувании.

Документация

PostgreSQL: B-Tree Indexes, PostgreSQL: Index Types.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам