Индекс — это сделка: вы платите памятью и скоростью записи, чтобы читать быстрее. Разница видна не на глаз — на честном стенде PostgreSQL 18 (таблица events, 2 000 000 строк, 202 МБ heap) один и тот же запрос по равенству user_id = 12345 без индекса выполняется 148.580 мс (Seq Scan, план перебирает все 2 миллиона строк и отбрасывает 1 999 975 лишних). После CREATE INDEX тот же запрос укладывается в 0.114 мс — разница почти в 1300 раз. Индекс при этом занимает 15 МБ — 7% от размера самой таблицы. Это не абстрактная арифметика «O(log n) быстрее O(n)», это конкретная строка в EXPLAIN ANALYZE.
Но за эту скорость чтения кто-то платит. Каждый INSERT теперь обязан обновить не только таблицу, но и структуру индекса — а если индексов несколько, обновляются все. На том же стенде вставка 500 000 строк без единого индекса заняла 1.4 секунды и весила 56 МБ; с шестью индексами на той же таблице — почти 9 секунд и 135 МБ, притом что вставляемые данные были побитово идентичны в обоих прогонах. Индекс не бесплатен ни в деньгах диска, ни во времени записи — и раздел про эту цену подробно разберёт статья #4 этой серии.
Но «индекс» — это не одна структура, а целое семейство: B-tree, hash, bitmap, инвертированный, BRIN, LSM устроены принципиально по-разному и ускоряют разные классы запросов. Индекс, идеальный для равенства, бесполезен для диапазона; индекс, экономящий место на гигантской таблице, требует определённого порядка данных на диске, без которого превращается в мёртвый груз. Понимание внутреннего устройства — единственный способ предсказать, поможет ли конкретный индекс конкретному запросу, ещё до того, как вы его создали.
Это первая, вводная статья серии «Индексы в базах данных». Здесь — что индекс вообще делает и как устроены основные структуры. Дальше — как выбирать индекс под запрос и проверять, что он реально используется (#2), различия в реализациях по конкретным БД (#3), паттерны и антипаттерны эксплуатации (#4), и как на индексы влияют язык приложения и ORM (#5).
В статье
- Full scan против индекса: цена и выигрыш
- B-tree и B+tree: рабочая лошадка
- Hash: точное равенство и ничего больше
- Bitmap: низкая кардинальность и комбинирование условий
- Инвертированный индекс (GIN): термин → список документов
- GiST и SP-GiST: обобщённые деревья
- BRIN: крошечный индекс для гигантских таблиц
- R-tree и пространственные индексы: коротко
- LSM: когда запись важнее чтения
- Что дальше
- Источники
Full scan против индекса: цена и выигрыш
Без индекса единственный способ найти строки, удовлетворяющие условию, — прочитать всю таблицу и проверить условие на каждой строке. Это Seq Scan в терминологии PostgreSQL: сложность линейна по числу строк, O(n). На маленькой таблице это дёшево и даже быстрее индекса — не нужно обращаться к отдельной структуре и потом ходить обратно в таблицу. Но при 2 миллионах строк тот же перебор стоит 148.580 мс, а Index Scan того же запроса — 0.114 мс:
--- Seq Scan, WHERE user_id = 12345, без индекса ---
Seq Scan on events (cost=0.00..50847.00 rows=21 width=70)
(actual time=0.956..148.523 rows=25.00 loops=1)
Filter: (user_id = 12345)
Rows Removed by Filter: 1999975
Buffers: shared hit=25847
Execution Time: 148.580 ms
--- Index Scan, тот же запрос, после CREATE INDEX idx_events_user ---
Index Scan using idx_events_user on events (cost=0.43..23.88 rows=20 width=70)
(actual time=0.051..0.091 rows=25.00 loops=1)
Index Cond: (user_id = 12345)
Buffers: shared hit=28 read=3
Execution Time: 0.114 ms
Разница в буферах — shared hit=25847 против shared hit=28 read=3 — объясняет весь разрыв: без индекса нужно прочитать почти все блоки таблицы, с индексом — три десятка блоков самого индекса плюс горстку блоков таблицы для найденных строк. Если убрать и это последнее обращение к таблице, добавив в индекс лишние колонки через INCLUDE (покрывающий индекс), можно вообще исключить поход в heap — Index Only Scan на том же запросе даёт 0.090 мс, ещё немного быстрее за счёт того, что Heap Fetches не нужны, если видимость строк подтверждена картой видимости.
Но индекс — это отдельная структура на диске, которая должна оставаться согласованной с таблицей. idx_events_user занимает 15 МБ при 202 МБ heap: индекс хранит не всю строку, а только индексируемые колонки плюс указатель на строку, поэтому обычно меньше таблицы — но не бесплатно, и при добавлении нескольких индексов на одну таблицу совокупный размер и цена записи растут почти линейно по числу индексов (раздел про write-amplification — ниже и подробно в статье #4).
Отсюда правило: индекс имеет смысл, когда выигрыш на чтении перевешивает цену на запись и место, и когда запрос достаточно избирателен — извлекает малую долю строк. Как именно оценить избирательность и когда планировщик всё равно откажется от индекса в пользу full scan — тема статьи #2 этой серии (выбор и использование индексов).
B-tree и B+tree: рабочая лошадка
B-tree (и его вариант B+tree, который использует подавляющее большинство реляционных СУБД, включая PostgreSQL, MySQL и большинство файловых систем) — это сбалансированное дерево, где каждый узел хранит отсортированные ключи-разделители. Поиск спускается от корня к листу, на каждом уровне сравнивая искомый ключ с разделителями в узле и выбирая нужную ветвь — глубина дерева растёт логарифмически от числа строк, поэтому сложность поиска O(log n): на миллиарде строк дерево из B+tree с разветвлением в сотни ключей на узел имеет глубину 4–5, а не миллиард шагов перебора.
Ключевое отличие B+tree от классического B-tree — где хранятся данные. В B+tree все значения (или указатели на строки таблицы) лежат только в листьях; внутренние узлы содержат исключительно ключи-разделители для навигации. А сами листья связаны в двусвязный список — переход от одного листа к соседнему не требует подъёма к родителю. Это решает вторую важную задачу индекса помимо точечного поиска: диапазонные запросы и сортировку. Найдя левую границу диапазона спуском по дереву, можно затем просто идти по цепочке листьев вправо, не возвращаясь к внутренним узлам — ровно то, что нужно для BETWEEN, ORDER BY и range-сканов.
Ещё одно следствие сортированности ключей — составные индексы работают по принципу left-prefix: индекс (user_id, status) можно использовать для поиска по одному user_id, но не по одному status — потому что внутри дерева строки физически упорядочены сначала по первой колонке, и без неё нет способа сузить диапазон поиска. На реальном стенде это выглядит буквально так: запрос user_id = 555 по индексу (user_id, status) — Index Scan, 0.170 мс; запрос по одному status = 'paid' — честный Seq Scan с чтением всех строк, 226.914 мс, потому что эта колонка — не префикс индекса. Разбор составных индексов, порядка колонок и того, как ломается индекс при неявном приведении типов (тот же стенд: user_id = 555 находит индекс за 0.170 мс, а user_id::text = '555' с тем же результатом по данным — Seq Scan за 255.980 мс), — в статье #2.
B+tree — дефолтный индекс почти во всех реляционных СУБД не случайно: он одинаково хорошо обслуживает равенство, диапазон, сортировку и left-prefix составных условий, ценой логарифмической, а не постоянной высоты дерева. Следующие структуры — не замена B-tree, а специализация под задачи, где B-tree работает хуже или не работает вовсе.
Hash: точное равенство и ничего больше
Hash-индекс хранит не отсортированные ключи, а хеш-таблицу: значение колонки прогоняется через хеш-функцию, и результат указывает на bucket с указателями на строки. Поиск по точному равенству — теоретически O(1), без логарифмической глубины дерева. Цена этой скорости — потеря всякого порядка: хеш-функция намеренно рассеивает близкие значения по разным bucket’ам, поэтому диапазон (>, <, BETWEEN) и сортировка по hash-индексу невозможны в принципе — для них нужно вернуться к дереву.
На практике в PostgreSQL выигрыш hash-индекса перед B-tree на чистом равенстве обычно не стоит потери универсальности: B-tree на равенстве уже достаточно быстр (те самые 0.114 мс выше — это B-tree), а hash лишается диапазонов и сортировки совсем. Показательна и цена по месту: на стенде hash-индекс по низкоселективной колонке status (5 различных значений на 2 миллиона строк) занял 94 МБ — больше, чем B-tree по первичному ключу той же таблицы (43 МБ), из-за оверхеда самой hash-структуры и низкой селективности, которая всё равно требует последующего чтения из heap через Bitmap Heap Scan. Hash-индекс имеет смысл в специализированных движках, где диапазоны и сортировка не нужны в принципе, — например, в KV-хранилищах.
Bitmap: низкая кардинальность и комбинирование условий
Bitmap-индекс хранит для каждого возможного значения колонки битовую карту: один бит на строку таблицы, единица — если у строки это значение. Такая структура выгодна, когда число различных значений мало (низкая кардинальность) — карта на значение компактна, а комбинировать условия по нескольким колонкам можно битовыми операциями AND/OR над картами, что дёшево и параллелизуется.
В PostgreSQL отдельного персистентного bitmap-индекса как типа нет — вместо этого планировщик умеет на лету строить Bitmap Index Scan из обычного B-tree или другого индекса, если это выгоднее чистого Index Scan: собрать битовую карту нужных страниц таблицы, затем прочитать эти страницы Bitmap Heap Scan, отсортировав обращения по физическому порядку и избежав случайного I/O по одной строке за раз. Именно так план выглядит для hash-индекса по status = 'refunded' на стенде — Bitmap Heap Scan ← Bitmap Index Scan, 90.4 мс на ~250 000 подходящих строк из 2 миллионов: планировщик распознал, что для такой доли строк дешевле собрать карту страниц заранее, чем скакать по индексу построчно. Тот же путь берёт и GIN-индекс по JSONB (ниже) — bitmap-стратегия там, где число совпадений велико, но не равно всей таблице.
Инвертированный индекс (GIN): термин → список документов
Обычный B-tree индексирует одно значение на строку. Но что делать, если в строке — массив, JSONB-документ с произвольным набором ключей или текст, который нужно искать по отдельным словам? Здесь работает инвертированный индекс (в PostgreSQL — GIN, Generalized Inverted Index): структура индексирует не строку целиком, а каждый элемент — каждое слово, каждый ключ JSONB, каждый элемент массива — и хранит для него список (или битовую карту) строк, где этот элемент встречается. Это в точности механизм полнотекстового поиска и обратный индекс поисковых систем, только внутри реляционной БД.
На стенде GIN по JSONB-колонке payload для запроса на вхождение payload @> '{"tag": "a"}' даёт Bitmap Heap Scan ← Bitmap Index Scan on idx_payload_gin, 171.7 мс на 334 319 подходящих строк. Индекс занимает 11 МБ — компактнее, чем можно было бы ожидать от структуры, которая хранит отдельную запись на каждый ключ каждого JSONB-документа: GIN дедуплицирует повторяющиеся элементы и хранит их один раз со списком строк, а не размножает элемент на каждое вхождение. Похожий эффект даёт multikey-индекс MongoDB по массиву: индексируется каждый элемент массива отдельно (isMultiKey: true), и запрос tags: 'a' в отчёте стенда возвращает totalKeysExamined: 50247 — по одной проверке ключа на каждое вхождение элемента 'a' в любом документе, а не на документ. Различия реализации инвертированного индекса и multikey между PostgreSQL и MongoDB — в статье #3 (индексы в разных БД).
GiST и SP-GiST: обобщённые деревья
GiST (Generalized Search Tree) и SP-GiST (Space-Partitioned GiST) — не конкретная структура, а фреймворк для построения деревьев поиска под произвольный предикат, который не укладывается в линейный порядок B-tree. Вместо фиксированного сравнения «меньше/больше» GiST требует от типа данных функции пересечения и объединения ограничивающих объёмов (bounding box) — и на этой основе можно строить индексы для геометрии, диапазонов (tsrange, int4range), даже полнотекстового поиска. SP-GiST отличается тем, что не балансирует дерево обязательно — подходит для данных с неравномерным, кластеризованным распределением (например, quad-tree по географическим координатам), где строгая балансировка B-tree была бы избыточна.
Типичный практический случай GiST — индекс по географической точке или полигону, где значение не сравнимо по «больше/меньше», а нужно проверять пересечение или включение в область. Это отдельная большая тема, разобранная детально в серии о гео-поиске — geohash, R-tree, S2, H3 и то, как каждый подход балансирует точность, размер и поведение на границах ячеек, смотрите в статье «Алгоритмы и пространственные индексы»Скоро.
BRIN: крошечный индекс для гигантских таблиц
BRIN (Block Range Index) — самая экономная по месту структура из всех: вместо индексации каждой строки он хранит сводку (обычно min/max) по диапазону физических блоков таблицы — например, по каждым 128 страницам. Поиск по BRIN сначала отбрасывает целые диапазоны блоков, для которых сводка гарантированно не содержит искомое значение, а затем читает оставшиеся блоки уже как Bitmap Heap Scan. Цена такой экономии — точность: BRIN не указывает на конкретные строки, только на диапазоны блоков, которые стоит проверить.
Размер BRIN-индекса на стенде — это не преувеличение маркетинга, а буквально измеренное число: 24 килобайта на индекс, независимо от того, строился он по колонке с идеальной корреляцией или со случайной. Для сравнения, B-tree по первичному ключу той же таблицы (43 МБ) больше BRIN в ~1800 раз, а весь heap — в 8600 раз. BRIN хранит не указатели на строки, а буквально несколько чисел на каждый диапазон блоков — отсюда и размер.
Но крошечный размер — не повод ставить BRIN везде. Работоспособность BRIN целиком зависит от одного условия: индексируемая колонка должна физически коррелировать с порядком строк на диске. На стенде это проверено в обе стороны. По колонке created_at, которая генерировалась случайно (correlation ≈ -0.0005, то есть практически ноль), планировщик BRIN честно не выбрал вообще — запрос created_at > now() - interval '7 days' ушёл в Seq Scan, 309.148 мс: без физической кластеризации BRIN не может отсечь ни одного блока, потому что подходящие строки размазаны по всей таблице. А по колонке id (bigserial, корреляция = 1, идеальная — значения физически монотонны) BRIN технически работает — принудительное отключение Index Scan подтверждает Bitmap Index Scan on idx_id_brin за 3.8 мс, — но планировщик по умолчанию всё равно выбирает не его, а уже существующий B-tree первичного ключа (Index Scan using events_pkey, 3.007 мс), потому что тот дешевле для точечного диапазона при наличии готового дерева.
Честный вывод: BRIN эффективен ровно в одной нише — данные физически коррелируют с индексируемой колонкой, и при этом нет конкурирующего B-tree по той же колонке, который планировщик предпочтёт как более дешёвый. Типичный подходящий сценарий — append-only лог с монотонной колонкой времени, по которой ещё не создан отдельный B-tree: там 24 КБ BRIN отсекают подавляющее большинство блоков почти бесплатно. Если же на той же колонке уже висит B-tree (как у id в этом стенде), BRIN просто не будет выбран — не потому что он сломан, а потому что он не самый дешёвый вариант из имеющихся.
R-tree и пространственные индексы: коротко
R-tree — специализация идеи B-tree для пространственных данных: вместо ключей-разделителей внутренние узлы хранят минимальные ограничивающие прямоугольники (MBR), которые вкладываются друг в друга — узел верхнего уровня охватывает MBR всех своих потомков. Поиск «что пересекается с этой областью» спускается по дереву, отбрасывая целые поддеревья, чьи MBR не пересекают запрос. Именно так устроен индекс by_geo в Tarantool (RTREE — один из четырёх типов индексов memtx-движка наравне с TREE, HASH и BITSET) и один из механизмов, доступных через GiST в PostgreSQL.
Пространственные индексы — большая отдельная тема с собственными компромиссами (R-tree vs geohash vs иерархические ячейки S2/H3), которую эта статья не будет дублировать: подробный разбор — в серии о гео-поиске, начиная со статьи «Алгоритмы и пространственные индексы: geohash, R-tree, S2, H3»Скоро.
LSM: когда запись важнее чтения
Все структуры выше — вариации read-optimized деревьев: они держат данные отсортированными на диске постоянно, а значит каждая запись потенциально требует случайной модификации страницы посреди дерева. LSM (Log-Structured Merge Tree) решает обратную задачу — оптимизирует запись, а не чтение. Новые данные сначала попадают в memtable — отсортированную структуру в памяти; когда она заполняется, целиком сбрасывается на диск как неизменяемый отсортированный файл (SSTable). Запись всегда последовательна и дёшева: не нужно искать место посреди существующей структуры на диске, только дописать новый файл. Чтение расплачивается за это — нужно проверить memtable и потенциально несколько уровней SSTable, поэтому в фоне работает компакция, которая сливает и уплотняет файлы, поддерживая число уровней разумным.
LSM — движок, стоящий за большинством современных систем, ориентированных на высокий поток записи: RocksDB, Cassandra/ScyllaDB, vinyl-движок Tarantool (в противовес встроенному in-memory движку memtx того же Tarantool — на стенде оба присутствуют в одном кластере: memtx-спейс events с TREE/HASH/BITSET/RTREE индексами и отдельный vinyl-спейс events_lsm, engine=vinyl, подтверждённый явно). Компромисс read/write-амплификации между B-tree и LSM — отдельная и важная тема, которую эта статья не разворачивает подробно: она разобрана на живых стендах Redis/Tarantool/ScyllaDB и других in-memory и LSM-систем в серии «Вычисления в оперативной памяти»готовится, с 23 сентября и в статье о KV/документных хранилищах «KV и документные: транзакций почти нет», где LSM-хранилища вроде ScyllaDB разбираются с точки зрения консистентности записи под конкуренцией.
Что дальше
Эта статья дала словарь структур; дальше серия идёт вглубь по трём осям. Как выбирать индекс под конкретный запрос, что такое селективность и покрывающий индекс, и — главное — как убедиться, что планировщик действительно использует созданный индекс, а не игнорирует его: статья #2, «Как выбирать и использовать индексы». Как одна и та же идея индекса реализована по-разному в PostgreSQL, MongoDB и Tarantool — статья #3, «Индексы в разных БД». Где индексирование превращается в антипаттерн — over-indexing, write-amplification на реальных числах, неиспользуемые и дублирующие индексы, bloat — статья #4, «Паттерны и антипаттерны индексирования». И как ORM и язык приложения незаметно ломают использование индекса — N+1, неявные приведения типов, prepared statements — статья #5, «Индексы и языки/ORM»готовится, с 30 июля.
Источники
- PostgreSQL Documentation — Chapter 11. Indexes
- PostgreSQL Documentation — 65.4. GIN Indexes, 65.3. GiST Indexes, BRIN Indexes
- Tarantool Documentation — Indexes
- Стенд:
digital-cookbook/databases/db-indexes(PostgreSQL 18.4, MongoDB 8.2.11, Tarantool 3.7.0)
Комментарии