Индексы в базах данных: B-tree, hash, LSM, составные и покрывающие индексы

Коротко

• Индекс — отдельная структура, отсортированная по ключу и указывающая на строки. Он превращает полный проход по таблице за $O(n)$ в поиск за $O(\log n)$ плюс чтение найденного.
• B-tree — универсальный выбор. Равенство, диапазоны, ORDER BY, префиксный LIKE. Hash умеет только равенство. LSM жертвует скоростью чтения ради очень быстрой записи.
• Составной индекс работает по левому префиксу. Индекс (user_id, created_at) помогает запросу по user_id, но не запросу только по created_at.
• Покрывающий индекс отвечает на запрос без похода в таблицу. Это часто самая дешёвая оптимизация из возможных.
• Каждый индекс замедляет запись и занимает место. Индексы подбирают под реальные запросы и проверяют через EXPLAIN, а не создают «на всякий случай».

Как устроено само B-дерево, почему у него сотни ключей в узле и чем B+ дерево отличается от B-дерева, разобрано в отдельной статье про B-дерево. Здесь — взгляд со стороны инженера, который проектирует схему и отвечает на вопросы интервьюера.

Что такое индекс и зачем он нужен

Таблица на диске — это набор страниц (обычно по 4–16 КБ), в которых строки лежат примерно в порядке вставки. Чтобы найти заказы пользователя 42 без индекса, база читает все страницы и проверяет каждую строку. Это называется полным сканированием: Seq Scan в PostgreSQL, type: ALL в MySQL, SCAN в SQLite.

Индекс — это вторая структура данных рядом с таблицей. В ней хранятся значения ключа в отсортированном виде и ссылка на строку: физический адрес (ctid в PostgreSQL) или первичный ключ (вторичные индексы InnoDB в MySQL).

Проверим на SQLite: таблица на миллион заказов, ищем заказы одного пользователя.

import sqlite3, random, time

db = sqlite3.connect(':memory:')
db.execute('CREATE TABLE orders(id INTEGER PRIMARY KEY, user_id INT, '
           'status TEXT, created_at TEXT, total INT)')
random.seed(1)
statuses = ['new', 'paid', 'shipped', 'cancelled']
db.executemany(
    'INSERT INTO orders(user_id, status, created_at, total) VALUES (?, ?, ?, ?)',
    [(random.randint(1, 100_000), random.choice(statuses),
      f'2026-{random.randint(1, 12):02d}-{random.randint(1, 28):02d}',
      random.randint(1, 10_000)) for _ in range(1_000_000)])

def plan(sql):
    for row in db.execute('EXPLAIN QUERY PLAN ' + sql):
        print(row[3])

q = 'SELECT * FROM orders WHERE user_id = 42'
plan(q)   # SCAN orders
db.execute('CREATE INDEX idx_orders_user ON orders(user_id)')
plan(q)   # SEARCH orders USING INDEX idx_orders_user (user_id=?)

На моей машине запрос без индекса занял около 20 мс, с индексом — меньше десятой доли миллисекунды. На миллионе строк разница в сотни раз, на миллиарде — это разница между «работает» и «лежит».

B-tree, hash и LSM: три способа организовать индекс

B-tree (точнее, B+ tree)

Индекс по умолчанию в PostgreSQL, MySQL InnoDB, SQLite, Oracle и SQL Server. Ключи отсортированы, листья связаны в список, высота дерева на миллиардах строк — 3–5 уровней.

Что умеет:

• равенство: WHERE email = ?;
• диапазоны: BETWEEN, >, <;
• сортировку: ORDER BY created_at без отдельного шага сортировки;
• префиксный поиск: LIKE 'abc%' (в PostgreSQL для этого при не-C локали нужен класс операторов text_pattern_ops);
• MIN и MAX — это просто крайние листья.

Слабое место — случайная запись. Вставка в середину дерева меняет страницу на диске «на месте», а при переполнении страница делится. Поэтому случайные UUIDv4 как первичный ключ в InnoDB ведут к фрагментации, а последовательные ключи (автоинкремент, UUIDv7) всегда дописываются в правый край.

Hash-индекс

Тот же принцип, что у хеш-таблицы: ключ → хеш → корзина. Поиск по равенству — в среднем $O(1)$.

Чего не умеет:

• диапазоны и сортировку: хеш разрушает порядок, соседние ключи оказываются в случайных корзинах;
• составной поиск по префиксу: хеш считается от всего ключа целиком.

На практике hash-индексы встречаются редко. В PostgreSQL они есть (USING hash), но до версии 10 не писались в WAL и не переживали падение. Обычно они дают небольшой выигрыш по размеру для длинных ключей, которые ищут только по равенству. В InnoDB явного hash-индекса нет, зато есть внутренний adaptive hash index, который движок строит сам поверх горячих страниц B-tree. Зато hash — основа key-value хранилищ в памяти вроде Redis.

LSM-дерево (Log-Structured Merge)

Подход RocksDB, LevelDB, Cassandra, ScyllaDB, HBase. Идея — никогда не писать на диск случайно:

1. Запись идёт в журнал (WAL) и в memtable — отсортированную структуру в памяти, часто skip list.
2. Когда memtable заполнилась, она целиком сбрасывается на диск в неизменяемый отсортированный файл — SSTable.
3. Фоновая компакция сливает мелкие SSTable в крупные, выкидывая перезаписанные и удалённые значения.

Чтение сложнее: ключ может лежать в memtable или в любом из SSTable, от свежих к старым. Чтобы не открывать каждый файл, у каждого SSTable есть фильтр Блума: он быстро отвечает «этого ключа здесь точно нет».

На интервью это формулируют через три вида «усиления» (amplification): чтения (сколько страниц прочитать ради одного ключа), записи (сколько байт реально записано на диск ради одного байта данных) и места. B-tree выигрывает по чтению, LSM — по записи. Нагрузка вида «миллионы событий в секунду, читаем редко» (метрики, логи, ленты) — классический аргумент за LSM.

Составные индексы и правило левого префикса

Составной индекс (user_id, created_at) — это записи, отсортированные сначала по user_id, а при равенстве — по created_at. Как телефонный справочник: по фамилии, потом по имени.

Из этого прямо следует, какие запросы он ускоряет:

CREATE INDEX idx_user_created ON orders(user_id, created_at);

-- SEARCH ... (user_id=? AND created_at>?) — оба поля используются
SELECT * FROM orders WHERE user_id = 42 AND created_at >= '2026-06-01';

-- SEARCH ... (user_id=?) — и сортировка бесплатно, без отдельного шага
SELECT * FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 10;

-- SCAN orders — индекс бесполезен, нет левого префикса
SELECT * FROM orders WHERE created_at >= '2026-06-01';

Все три плана получены в SQLite через EXPLAIN QUERY PLAN. Обрати внимание на второй запрос: если бы индекс был только по user_id, в плане появилась бы строка USE TEMP B-TREE FOR ORDER BY — база сортировала бы результат отдельно.

Порядок колонок

Здесь интервьюер обычно и копает. Практические правила:

• Сначала колонки с равенством, потом сортировка, потом диапазон. В мире MongoDB это называют правилом ESR: Equality, Sort, Range.
• Диапазон «обрывает» индекс. В индексе (a, b) для условия a > 10 AND b = 5 по b уже не получится сузить поиск: внутри диапазона по a значения b не отсортированы. Значит, колонку с равенством ставим первой: (b, a).
• Не обязательно «самую селективную колонку первой». Это популярный миф. Важнее, какие запросы есть: индекс (tenant_id, created_at) полезен всем запросам «по тенанту», даже если тенантов немного.

Некоторые СУБД умеют обходить отсутствие левого префикса через skip scan: перебирают различные значения первой колонки и для каждого ищут по второй. Это есть в Oracle, в MySQL 8.0, а в PostgreSQL B-tree skip scan появился в 18-й версии. Но работает он, только когда различных значений первой колонки мало, — полагаться на него при проектировании не стоит.

Один составной или несколько одиночных

Два отдельных индекса по a и по b не равны одному (a, b). База может объединить их (bitmap-сканирование в PostgreSQL, index merge в MySQL), но это дороже, чем пройти по одному составному индексу. Обратное тоже верно: составной (a, b) уже покрывает запросы по одному a, поэтому отдельный индекс по a рядом с ним — лишний.

Покрывающие индексы

Обычный поиск по индексу — это два шага: найти ключ в индексе, потом сходить за строкой в таблицу. Второй шаг — случайное чтение, и на тысячах строк он доминирует.

Если все нужные запросу колонки уже есть в индексе, второй шаг не нужен. Такой индекс называют покрывающим (covering):

-- SEARCH orders USING COVERING INDEX idx_user_created (user_id=?)
SELECT created_at FROM orders WHERE user_id = 42;

-- total в индексе нет, приходится идти в таблицу
SELECT user_id, created_at, total FROM orders WHERE user_id = 42;

CREATE INDEX idx_cov ON orders(user_id, created_at, total);
-- SEARCH orders USING COVERING INDEX idx_cov (user_id=?)
SELECT user_id, created_at, total FROM orders WHERE user_id = 42;

Как это выглядит в разных СУБД:

• PostgreSQL: план Index Only Scan. С версии 11 есть INCLUDE: CREATE INDEX ON orders(user_id) INCLUDE (total) — total лежит в листьях, но не участвует в сортировке. Нюанс: index-only scan всё равно заглядывает в таблицу, если страница не отмечена в visibility map как полностью видимая, поэтому на часто обновляемых таблицах эффект меньше — до прохода VACUUM.
• MySQL InnoDB: в EXPLAIN в колонке Extra будет Using index. Вторичный индекс InnoDB уже содержит первичный ключ, поэтому SELECT id FROM t WHERE email = ? покрывается индексом по одному email.

Отсюда же вред от SELECT *: он почти никогда не покрывается индексом и тащит лишние колонки по сети.

Кластерный индекс

В InnoDB и SQL Server таблица и есть B-tree по первичному ключу: строки лежат в листьях индекса. Это кластерный индекс. Следствия:

• поиск по первичному ключу — один проход по дереву, сразу со строкой;
• вторичные индексы хранят первичный ключ, и поиск по ним — это два прохода по деревьям; длинный первичный ключ раздувает все вторичные индексы;
• диапазон по первичному ключу читается последовательно.

В PostgreSQL таблица — это heap, неупорядоченная куча, а все индексы, включая первичный, — вторичные. Команда CLUSTER переупорядочивает таблицу один раз, но порядок не поддерживается при последующих вставках.

Селективность: когда индекс не помогает

Селективность — доля строк, которые отбирает условие. user_id = 42 в нашей таблице отбирает около 10 строк из миллиона — это высокая селективность, индекс идеален. status = 'paid' отбирает четверть таблицы — низкая селективность.

При низкой селективности индекс может быть медленнее полного сканирования. Полный проход читает страницы последовательно, а поиск по индексу на каждую из 250 000 строк делает случайный переход в таблицу. Планировщик это знает и по статистике (ANALYZE) выбирает Seq Scan. В нашем эксперименте SQLite после ANALYZE всё же выбрал индекс по status, и запрос шёл столько же, сколько полное сканирование, около 200 мс: выигрыша ноль, а индекс надо поддерживать при каждой записи.

Точного порога нет: он зависит от размера строк, кэша и того, лежат ли данные физически в порядке индекса. Поэтому вместо правила «индекс полезен до N%» проверяй план.

Что делать с колонками низкой селективности:

• Частичный индекс, если запрашивают редкое значение: CREATE INDEX ON orders(created_at) WHERE status = 'new'. Индекс маленький и содержит только нужные строки. Есть в PostgreSQL и SQLite.
• Составной индекс, где низкоселективная колонка стоит первой для фильтра по равенству, а за ней идёт колонка для сортировки или диапазона.

Когда индекс есть, но не используется

Частые причины, по которым в плане внезапно Seq Scan:

• Функция или выражение над колонкой: WHERE lower(email) = ?, WHERE date(created_at) = ?. Лечится индексом по выражению: CREATE INDEX ON users(lower(email)) (PostgreSQL, SQLite; в MySQL — с версии 8.0.13) или переписыванием условия в диапазон.
• Неявное приведение типов: колонка VARCHAR, а в запросе число. MySQL приведёт колонку к числу для каждой строки, и индекс не сработает.
• LIKE '%abc' — сортировка по началу строки не помогает искать по середине. Для полнотекстового поиска нужны другие индексы: GIN с триграммами в PostgreSQL или отдельный поисковый движок.
• OR по разным колонкам — часто переписывают в UNION ALL или полагаются на объединение индексов.
• Устаревшая статистика — планировщик думает, что в таблице 100 строк, а их 10 миллионов. Лечится ANALYZE.

Базовые случаи вроде функции над колонкой коротко перечислены в разборе SQL-вопросов на собеседовании — там индексы лишь один из блоков, здесь мы разбираем почему.

Цена записи

Индекс — не бесплатное ускорение. Каждый INSERT пишет в таблицу и во все индексы. UPDATE колонки из индекса — удаление старой записи в индексе и вставка новой. DELETE чистит все индексы.

Замер на SQLite: 300 000 вставок случайных чисел в таблицу с пятью колонками.

Пять индексов — в семь раз медленнее. Цифры с одной машины и для таблицы в памяти, но тренд общий. Кроме времени:

• Место. Индексы на нагруженной таблице нередко весят больше самих данных.
• Память. Горячие страницы индексов должны помещаться в buffer pool; лишние индексы вытесняют полезные.
• Блокировки и миграции. Построение индекса на большой таблице может блокировать запись. В PostgreSQL для этого есть CREATE INDEX CONCURRENTLY, в MySQL — online DDL.
• HOT-обновления в PostgreSQL. Если обновляемая колонка не входит ни в один индекс, PostgreSQL может обновить строку без правки индексов. Лишний индекс на часто меняемой колонке лишает этой оптимизации.

Отсюда практика: регулярно искать неиспользуемые индексы (pg_stat_user_indexes с idx_scan = 0 в PostgreSQL, sys.schema_unused_indexes в MySQL) и дубликаты, где один индекс — левый префикс другого.

EXPLAIN: как читать план

EXPLAIN показывает, как база собирается выполнить запрос. EXPLAIN ANALYZE в PostgreSQL ещё и выполняет его и показывает реальные цифры — осторожно с UPDATE и DELETE, оборачивай в транзакцию с ROLLBACK.

Что искать в PostgreSQL:

Главное, на что смотреть в EXPLAIN ANALYZE, — расхождение rows (оценка) и actual rows (факт). Если планировщик ждал 10 строк, а получил 100 000, он выбрал план под неправильные данные — часто виновата статистика или коррелирующие колонки.

В MySQL читай колонки type (ALL — полное сканирование, ref/range/const — работа с индексом), key (какой индекс выбран), rows и Extra (Using index — покрывающий, Using filesort — отдельная сортировка, Using temporary — временная таблица).

Индексы в системном дизайне

На system design интервью индексы всплывают, когда ты описываешь модель данных. Хороший ответ выглядит так: «Основной запрос ленты — последние 20 постов пользователя. Индекс (user_id, created_at DESC), запрос читает 20 записей из одного места индекса без сортировки». Это сразу показывает, что ты думаешь о путях доступа, а не только о таблицах.

Ещё несколько связок, которые полезно держать в голове:

• Пагинация. OFFSET 100000 всё равно проходит 100 000 записей. Курсорная пагинация WHERE (created_at, id) < (?, ?) ORDER BY created_at DESC, id DESC LIMIT 20 с индексом по (created_at, id) работает за одинаковое время на любой странице.
• Уникальность. Уникальный индекс — единственный надёжный способ гарантировать, что email не повторится: проверка в коде приложения проигрывает гонке двух параллельных запросов.
• Шардирование. Вторичный индекс в шардированной базе бывает локальным (каждый шард индексирует свои данные, запрос по нему идёт на все шарды) или глобальным (индекс сам шардирован по своему ключу, но его обновление — распределённая запись). Подробнее о шардах — в статье про шардирование и репликацию.
• Нагрузка на запись. Если система пишет на порядки больше, чем читает, это аргумент за хранилище на LSM, а на реляционной стороне — за минимальный набор индексов и отдельную реплику или витрину для аналитики.
• Кэш не заменяет индекс. Промах кэша всё равно идёт в базу, и без индекса один «холодный» запрос может положить её. О кэшах — в стратегиях кэширования.

Как встроить всё это в общий ход интервью, разобрано в статье о подходах к проектированию систем.

Типичные вопросы на собеседовании

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

Чем B-tree отличается от hash-индекса? Hash — только равенство, в среднем $O(1)$. B-tree — равенство, диапазоны, сортировка, префиксы за $O(\log n)$. Поэтому B-tree по умолчанию почти везде.

Почему B-tree, а не бинарное дерево поиска? Узел B-дерева занимает страницу диска и содержит сотни ключей, поэтому высота 3–5 вместо 30 у бинарного дерева. Каждый уровень — потенциальное чтение с диска. Подробности — в статье про B-дерево.

Есть индекс (a, b, c). Какие запросы он ускорит? a, a + b, a + b + c, а также a = ? ORDER BY b. Не ускорит b, c, b + c. Для a = ? AND c = ? будет использован только префикс a, а c проверится фильтром.

Что такое покрывающий индекс? Индекс, содержащий все колонки запроса, — база отвечает без чтения таблицы.

Почему запрос не использует индекс? Низкая селективность, функция над колонкой, приведение типов, LIKE '%...', устаревшая статистика. Проверяется через EXPLAIN.

Когда выбрать LSM-хранилище? Когда запись доминирует и важна её пропускная способность: метрики, логи, события. Цена — сложнее чтение и фоновая компакция, которая ест диск и CPU.

Почему случайный UUID как первичный ключ — плохо? В кластерном индексе вставки идут в случайные страницы: деления страниц, фрагментация, хуже работает кэш. Решение — последовательные идентификаторы или UUIDv7.

Частые ошибки

• Создать индексы по каждой колонке из WHERE по отдельности вместо одного составного.
• Поставить в составном индексе колонку с диапазоном перед колонкой с равенством.
• Держать индекс (a) рядом с (a, b) — первый лишний.
• Индексировать колонку с двумя-тремя значениями и ждать ускорения.
• Оптимизировать без EXPLAIN, по ощущениям.
• Строить индекс на большой таблице в проде обычным CREATE INDEX и блокировать запись.
• Забыть, что EXPLAIN ANALYZE действительно выполняет DELETE.

Что запомнить

1. Индекс превращает полный проход в поиск за $O(\log n)$, но каждая запись платит за все индексы.
2. B-tree — по умолчанию; hash — только равенство; LSM — для тяжёлой записи.
3. Составной индекс работает по левому префиксу: равенство → сортировка → диапазон.
4. Покрывающий индекс избавляет от похода в таблицу — смотри Index Only Scan и Using index.
5. При низкой селективности индекс бесполезен; частичный индекс — частое решение.
6. Любую гипотезу об индексе проверяй через EXPLAIN, а на интервью называй индекс под каждый главный запрос.