B-tree: устройство индексов, которые используют почти все СУБД

Прямой ответ

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

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

Ключевые свойства:

• Все листья находятся на одной глубине. Дерево растёт вверх, а не вглубь: при переполнении корневого узла высота увеличивается на единицу сразу для всего дерева.
• Ключи в узле отсортированы. Это позволяет двоичным поиском внутри узла выбрать нужного потомка.
• Узел соответствует странице хранения. Типичный размер страницы — 8 КБ, поэтому ёмкость узла зависит от размера ключа.
• Вставка вызывает split. Когда узел переполняется, он делится пополам, а средний ключ поднимается в родителя.

Вариант B+ tree отличается тем, что сами значения хранятся только в листьях, а внутренние узлы содержат лишь ключи и указатели. Листья связаны в связный список, что делает эффективными диапазонные запросы. Большинство промышленных индексов реализованы именно как B+ tree.

-- PostgreSQL: явное указание метода (btree — по умолчанию)
CREATE INDEX orders_created_at_idx ON orders USING btree (created_at);

-- сколько страниц занимает индекс
SELECT relname, relpages, reltuples::bigint
FROM pg_class WHERE relname = 'orders_created_at_idx';

Практика: что из устройства следует для разработчика

1. Высота дерева определяет стоимость поиска. Для таблицы в 10 млн строк с целочисленным ключом высота индекса обычно три-четыре уровня. Корневые и промежуточные уровни почти всегда находятся в кэше, поэтому фактическая стоимость — одно-два чтения с диска. Рост таблицы в десять раз добавляет к высоте один уровень, а не увеличивает стоимость в десять раз.

2. Размер ключа влияет на ёмкость узла. Индекс по bigint вмещает в страницу сотни ключей, индекс по составу из трёх text-полей — десятки. Больше ключей в узле — меньше высота — меньше чтений. Это аргумент против «универсальных» составных индексов из длинных строк.

3. Вставка в случайное место дороже вставки в конец. Вставка значения, попадающего в середину заполненного узла, вызывает split и перебалансировку. Вставка в конец дерева затрагивает только крайний лист. Поэтому индексы по монотонно растущим значениям (id, created_at) ведут себя предсказуемее, чем по хешам или UUID v4.

4. Fill factor оставляет место под вставки. В PostgreSQL для B-tree по умолчанию заполняется 90 % страницы. Оставшееся место позволяет новым ключам попадать в существующие страницы без split. Для таблиц, где идут обновления индексируемых колонок, снижение fill factor уменьшает фрагментацию.

5. Удаление не освобождает место сразу. Страницы остаются в индексе, пока их не обработает механизм очистки. Раздутый индекс — частая причина замедления, см. VACUUM и bloat.

6. Диапазонные запросы работают благодаря связности листьев. Условие BETWEEN, сортировка по индексу и ORDER BY ... LIMIT опираются на обход листьев по цепочке, а не на повторный спуск от корня для каждой строки.

Рекомендации:

1. Проверяйте высоту, а не только размер. Если индекс вырос до пяти-шести уровней, стоит посмотреть на размер ключа и fill factor.
2. Не индексируйте длинные строки без необходимости. Если нужен индекс по тексту, рассмотрите хеш-колонку или специализированный тип индекса — о выборе методов в статье про индексы PostgreSQL.
3. Помните о стоимости записи. Каждый индекс — дополнительное дерево, которое нужно поддерживать при вставке и обновлении. Пять индексов на таблице — это пять структур, изменяющихся на каждую запись.
4. Сравнивайте с альтернативой. Для нагрузки с интенсивной записью существует другая модель — LSM-tree, где дерево заменяется журналом и отсортированными файлами.

Практический сценарий: замедление поиска по мере роста таблицы

Контекст: запрос по created_at занимал 8 мс на таблице в 2 млн строк и 90 мс на 40 млн, хотя план не менялся.

1. Диагностика. EXPLAIN ANALYZE показал тот же Index Scan, но число прочитанных блоков выросло непропорционально. Проверка pg_class дала: индекс занимает 1,9 ГБ, средняя плотность страниц низкая.
2. Причина 1. Ключ индекса — составной: tenant_id (uuid) + created_at (timestamptz) + status (varchar). Ёмкость узла получилась небольшой, высота дерева выросла до пяти уровней.
3. Причина 2. Массовые удаления старых записей оставили полупустые страницы: индекс раздулся примерно вдвое относительно полезного объёма.
4. Действия. (а) Составной индекс заменили на два: по (tenant_id, created_at) и отдельный частичный по status для частого значения; (б) выполнили перестроение индекса с освобождением пустых страниц; (в) для архивных данных включили партиционирование, чтобы старые партиции можно было удалять целиком — см. партиционирование.
5. Результат. Высота индекса снизилась до четырёх уровней, объём — до 700 МБ, время запроса вернулось к 11 мс.

Вывод: производительность B-tree определяется не «наличием индекса», а размером ключа, плотностью страниц и высотой дерева. Эти параметры напрямую зависят от решений разработчика о составе индекса.

FAQ

Чем B-tree отличается от B+ tree? В B+ tree значения хранятся только в листьях, а внутренние узлы содержат лишь ключи и указатели; листья связаны в список. Это увеличивает ёмкость внутренних узлов и ускоряет диапазонные обходы. В документации СУБД термин «B-tree» часто используется для реализации, которая фактически является B+ tree.

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

Когда B-tree работает плохо? При очень высокой частоте вставок в случайные позиции и при необходимости хранить огромные объёмы записываемых данных. В таких сценариях split-ы и перебалансировка становятся основным расходом, поэтому системы, ориентированные на запись, выбирают LSM-подход.

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

Источники: PostgreSQL docs (index types), Wikipedia (B-tree) — ссылки в шапке.