--- title: "Глубокое погружение в индексы баз данных: как это устроено" description: "Подробное руководство для разработчиков по B+Tree в InnoDB, кучам (Heap) в Postgres, указателям узлов индексов, правилам составных индексов, расширенным типам индексов и избыточной записи (write amplification)." published: 2026-05-31 faq: - question: "Почему InnoDB использует кластеризованный индекс, в то время как Postgres использует кучу (Heap)?" answer: "InnoDB хранит данные строк непосредственно в листовых узлах B+Tree первичного ключа. Это делает поиск по первичному ключу чрезвычайно быстрым и сохраняет связанные данные последовательно. Postgres хранит все данные в файле кучи (Heap) и делает все индексы (включая первичный ключ) вторичными, указывающими на позиции в куче через TID. Это упрощает перемещение строк при обновлениях и избавляет от двойного поиска во вторичных индексах, но требует обращений к куче при запросах по первичному ключу." - question: "Что такое индекс GIN и когда его следует использовать в Postgres?" answer: "Обобщенный инвертированный индекс (GIN) разработан для индексации составных значений, таких как JSONB или массивы. Он сопоставляет отдельные элементы (ключи или значения) с соответствующими TID, обеспечивая высокоэффективное выполнение запросов с операторами вроде `@>` (содержит) или `?` (имеет ключ)." - question: "Как происходит избыточная запись (write amplification) при обслуживании индексов?" answer: "Избыточная запись происходит из-за того, что каждая операция INSERT, UPDATE или DELETE требует от СУБД обновления не только данных таблицы, но и всех связанных индексов. Кроме того, если вставка происходит в заполненную страницу B-Tree, страница должна быть разделена (Page Split), что приводит к записи нескольких страниц на диск и фрагментации диска." - question: "Как избежать двойного поиска во вторичных индексах в InnoDB?" answer: "Чтобы избежать двойного поиска (сначала сканирование вторичного индекса, затем переход к кластеризованному индексу по первичному ключу), вы можете спроектировать покрывающий индекс (Covering Index), содержащий все столбцы, запрашиваемые в SELECT. Это позволит СУБД получить все данные напрямую из вторичного индекса." --- # Глубокое погружение в индексы баз данных: как это устроено Каждый создаваемый вами запрос к базе данных — это борьба за скорость дискового ввода-вывода (I/O). Когда ваш набор данных помещается в оперативной памяти (RAM), запросы выполняются мгновенно. Но по мере того как объем данных вырастает до миллионов строк и выходит за пределы RAM на диск, СУБД приходится либо перебирать каждую страницу на диске (последовательное сканирование), либо использовать карту для быстрого перехода к нужным данным. Эта карта и есть индекс. Понимание того, как работают индексы на уровне диска и страниц, отличает начинающих разработчиков, которые наугад добавляют индексы к таблицам, от архитекторов баз данных, проектирующих самооптимизирующиеся и высокопроизводительные системы хранения данных. В этом глубоком погружении мы снимем абстрактный слой с MySQL (InnoDB) и PostgreSQL, чтобы увидеть, как они представляют индексы на диске, как работают правила составных индексов и какова реальная стоимость избыточной записи (write amplification). --- ## 1. Что под капотом: B+Tree в InnoDB против Heap и B-Tree в Postgres СУБД не хранят таблицы в виде простых массивов строк. Они структурируют их на диске с помощью страниц (обычно 16 КБ в InnoDB, 8 КБ в PostgreSQL). Однако их архитектура хранения принципиально различается. ### InnoDB: Кластеризованный индекс (B+Tree) В движке InnoDB от MySQL **сама таблица является индексом**. Если точнее, таблица структурирована как дерево B+Tree, построенное вокруг первичного ключа (Primary Key). Это называется **кластеризованным индексом**. * **Внутренние узлы (Internal Nodes):** Содержат только ключи и указатели на дочерние страницы. Они направляют поиск. * **Листовые узлы (Leaf Nodes):** Содержат непосредственно строки данных. Листовые страницы связаны последовательно в двусвязный список, что делает диапазонное сканирование (`WHERE id BETWEEN 10 AND 50`) невероятно быстрым. * **Вторичные индексы (Secondary Indexes):** Любой индекс, отличный от первичного ключа в InnoDB, является вторичным. Листовые узлы вторичного индекса *не* указывают на физические адреса на диске. Вместо этого они хранят **значение первичного ключа** строки. > [!NOTE] > Поскольку вторичные индексы InnoDB хранят первичный ключ, поиск строки по вторичному индексу (например, `WHERE email = 'user@example.com'`) требует двухэтапного поиска: сначала обход вторичного индекса для поиска первичного ключа, а затем обход B+Tree кластеризованного индекса для получения самой строки. ``` [Вторичный индекс (Email)] Листовой узел: 'user@example.com' -> PK: 42 | v [Кластеризованный индекс (ID)] Листовой узел: PK: 42 -> Данные строки: {id: 42, email: 'user@example.com', name: 'John Doe'} ``` ### PostgreSQL: Куча (Heap) и B-Tree PostgreSQL не использует кластеризованные индексы по умолчанию. Вместо этого он сохраняет данные строк в неупорядоченной структуре под названием **Куча (Heap)**. * **Страницы кучи (Heap Pages):** Строки таблицы добавляются в страницы в порядке их вставки (или туда, где есть свободное место). * **Индексы B-Tree:** Каждый индекс в Postgres (включая первичный ключ) является вторичным индексом. * **Листовые узлы (Leaf Nodes):** Листовые узлы индекса B-Tree в Postgres содержат **идентификатор кортежа (TID)** — физический адрес на диске, состоящий из номера блока (страницы) и индекса смещения внутри этой страницы (например, `(Page 14, Offset 3)`). > [!WARNING] > Поскольку индексы Postgres хранят физические TID, любая операция, перемещающая строку на диске (например, UPDATE, изменяющий размер строки, или миграция страниц из-за MVCC), сломала бы эти TID. Postgres справляется с этим с помощью процессов очистки (vacuum) и оптимизации HOT (Heap Only Tuples), но это означает, что все индексы указывают напрямую на Heap. ``` [Индекс Postgres (Email)] [Куча Postgres (Heap - неупорядоченная)] Лист: 'user@example.com' -> TID: (Page 14, Offset 3) ----> Page 14, Slot 3: {id: 42, ...} ``` --- ## 2. Правила порядка столбцов в составном индексе При создании индекса по нескольким столбцам — **составного индекса (composite index)** — порядок столбцов при объявлении критически важен. Неправильный порядок может сделать индекс совершенно бесполезным для определенных запросов. Золотые правила проектирования составных индексов: 1. **Правило самого левого префикса (Leftmost Prefix Rule):** База данных может использовать составной индекс только в том случае, если запрос фильтрует по самому левому столбцу индекса. Индекс на `(A, B, C)` оптимизирует запросы по `(A)`, `(A, B)` и `(A, B, C)`, но *не* поможет при запросах только по `(B)` или `(C)`. 2. **Сначала равенство, затем диапазоны (Equality First, Range Last):** Столбцы, фильтруемые по точному равенству (`=`, `IN`), должны идти первыми в индексе. Столбцы, фильтруемые по диапазонам (`<`, `>`, `BETWEEN`, `LIKE`), должны располагаться в конце. Как только оценивается диапазонный столбец, БД больше не может использовать последующие столбцы индекса для фильтрации. 3. **Высокая кардинальность в начале (High Cardinality First):** Столбцы с высокой кардинальностью (много уникальных значений, например, `user_id`) должны предшествовать столбцам с низкой кардинальностью (мало уникальных значений, например, `status`), при условии, что оба фильтруются по равенству. Давайте посмотрим на конкретную миграцию и запрос: ```sql -- database/migrations/2026_05_31_create_orders_table.sql CREATE TABLE orders ( id BIGINT AUTO_INCREMENT PRIMARY KEY, user_id BIGINT NOT NULL, status VARCHAR(50) NOT NULL, amount DECIMAL(10, 2) NOT NULL, created_at TIMESTAMP NOT NULL ); -- database/migrations/2026_05_31_add_composite_index.sql -- Оптимальный индекс для: user_id (равенство) + status (равенство) + created_at (диапазон/сортировка) CREATE INDEX idx_orders_user_status_created ON orders (user_id, status, created_at); ``` Для приведенного ниже запроса этот индекс позволяет СУБД мгновенно выполнить фильтрацию по `user_id`, затем по `status`, а затем прочитать уже отсортированные значения `created_at` в обратном порядке без выполнения отдельной операции filesort на диске. ```sql -- database/queries/find_user_orders.sql SELECT id, user_id, status, created_at, amount FROM orders WHERE user_id = 42 AND status = 'completed' ORDER BY created_at DESC LIMIT 10; ``` --- ## 3. Подробный разбор типов индексов Для разных сценариев запросов требуются разные структуры данных. Ниже приведено сравнение типов индексов, доступных в MySQL и PostgreSQL. ### B-Tree Рабочая лошадка баз данных. Поддерживает равенство (`=`), диапазоны (`>`, `<`, `BETWEEN`) и сортировку (`ORDER BY`). B-Tree деревья остаются сбалансированными, гарантируя время выполнения поиска, вставки и удаления на уровне $O(\log n)$. ### Hash Хеш-индексы хранят хеш индексируемого значения и указывают на соответствующую строку. * **Postgres:** Поддерживает явные хеш-индексы. Они невероятно быстры ($O(1)$) для поиска по равенству, но не поддерживают диапазонные запросы, сортировку или частичное совпадение по нескольким столбцам. * **MySQL (InnoDB):** Не поддерживает явное создание хеш-индексов. Вместо этого используется **адаптивный хеш-индекс (Adaptive Hash Index)** — внутренний механизм, при котором InnoDB отслеживает паттерны запросов к B-Tree и автоматически строит хеш-таблицы в оперативной памяти для наиболее часто запрашиваемых ключей. ### GIN (Generalized Inverted Index) - Postgres GIN (обобщенный инвертированный индекс) разработан для индексации составных значений, где нужно искать элементы *внутри* данных (например, документы JSONB или массивы). GIN сопоставляет отдельные элементы внутри документа с TID соответствующих им строк таблицы. ```sql -- database/migrations/2026_05_31_postgres_features.sql -- Создание таблицы с JSONB и индекса GIN в PostgreSQL CREATE TABLE user_profiles ( id BIGINT PRIMARY KEY, metadata JSONB NOT NULL ); CREATE INDEX idx_user_metadata_gin ON user_profiles USING GIN (metadata); -- Этот запрос задействует индекс GIN для мгновенного поиска совпадений по ключам SELECT * FROM user_profiles WHERE metadata @> '{"role": "administrator", "status": "active"}'; ``` ### Частичные / Фильтрованные индексы (Partial Indexes) Частичный индекс включает только подмножество строк таблицы, определяемое условием в секции `WHERE`. Это экономит дисковое пространство и делает индекс компактным и быстрым. * **Postgres:** Нативно поддерживает частичные индексы. * **MySQL:** Напрямую не поддерживает (по состоянию на версию 8.0). Приходится использовать функциональные индексы с выражениями, которые возвращают `NULL` (что менее элегантно), чтобы добиться схожего эффекта. ```sql -- database/migrations/2026_05_31_partial_index.sql -- Только для Postgres: индексируем только активные неоплаченные заказы для экономии места CREATE INDEX idx_orders_active_unpaid ON orders (user_id) WHERE status = 'pending' AND amount > 100.00; ``` ### Индексы по выражению / Функциональные индексы Вы можете проиндексировать результат работы функции или выражения, а не исходное значение столбца. Это полезно, когда запросы преобразуют столбцы в секции `WHERE`. ```sql -- database/migrations/2026_05_31_functional_index.sql -- Создание индекса по выражению для оптимизации поиска без учета регистра -- PostgreSQL: CREATE INDEX idx_orders_lower_status ON orders (LOWER(status)); -- MySQL 8.0+: CREATE INDEX idx_orders_lower_status ON orders ((LOWER(status))); ``` ### Покрывающие индексы (Covering Indexes) Покрывающий индекс — это вторичный индекс, содержащий все столбцы, необходимые для выполнения запроса. Это позволяет базе данных получить все данные прямо из страниц индекса, избегая обращения к самой таблице (к куче или кластеризованному индексу). * В Postgres вы можете явно добавить неключевые столбцы данных в индекс с помощью ключевого слова `INCLUDE`. * В MySQL вы просто добавляете эти столбцы в качестве дополнительных ключей составного индекса. ```sql -- database/migrations/2026_05_31_covering_index.sql -- Postgres: индекс отсортирован по user_id, но несет в себе данные amount/created_at CREATE INDEX idx_orders_covering ON orders (user_id) INCLUDE (amount, created_at); ``` --- ## 4. Избыточная запись (Write Amplification) и накладные расходы Индексы не бесплатны. Каждый добавленный индекс снижает производительность операций записи. Эти издержки выражаются в **избыточной записи (Write Amplification)**. ### Разделение страниц в B+Tree (Page Splits) Страницы базы данных выделяются с запасом свободного места (fillfactor) для будущих обновлений. При вставке строки СУБД должна записать её в соответствующий узел индекса B-Tree. Если страница узла заполнена, происходит **разделение страницы (Page Split)**: 1. Выделяется новая страница. 2. Примерно 50% ключей из переполненной страницы перемещаются на новую страницу. 3. Родительская страница обновляется, получая указатель на новую страницу. Эта операция требует выполнения нескольких операций записи на диск и приводит к фрагментации индексов, снижая скорость последовательного чтения. ### Vacuuming против отставания очистки (Purge Lag) При обновлении или удалении строк занимаемое ими место не может быть освобождено немедленно из-за механизмов MVCC (Multi-Version Concurrency Control). * **Postgres (Autovacuum):** При UPDATE в Postgres на диск записывается новая версия строки (кортеж), а индексы обновляются, чтобы указывать на неё. Это оставляет «мертвый кортеж» в исходной странице кучи. Если демон autovacuum не успевает очищать мертвые кортежи, таблица и индексы раздуваются (bloat), что приводит к падению производительности RAM и диска. * **MySQL InnoDB (Purge Lag):** В InnoDB обновления выполняются на месте в кластеризованном индексе, а старые версии записываются в сегмент отката (Undo Log). Однако во вторичных индексах старая запись помечается как «удаленная» (delete-marked), а новая вставляется рядом. Фоновый процесс, называемый **Purge Thread**, отвечает за очистку таких помеченных записей во вторичных индексах. При высокой интенсивности записи возникает отставание очистки (**Purge Lag**), что приводит к раздуванию хранилища и замедлению запросов. --- ## 5. Частые ошибки ### Ошибка 1: Неправильный порядок столбцов в составном индексе **Плохая практика:** Разработчик ожидает, что индекс оптимизирует запросы по обоим столбцам, но ставит столбец диапазона на первое место. ```sql -- database/queries/bad_composite_order.sql -- Индекс определен как: (created_at, user_id) CREATE INDEX idx_bad_order ON orders (created_at, user_id); -- Запрос: SELECT * FROM orders WHERE created_at >= '2026-01-01 00:00:00' AND user_id = 42; ``` *Почему это плохо:* Фильтрация по диапазону (`created_at`) мешает базе данных использовать часть индекса с `user_id` для точного позиционирования. Движок будет вынужден сканировать индекс по всем записям после указанной даты, проверяя каждую на соответствие `user_id`. **Хорошая практика:** ```sql -- database/queries/good_composite_order.sql -- Индекс определен как: (user_id, created_at) CREATE INDEX idx_good_order ON orders (user_id, created_at); -- Запрос: SELECT * FROM orders WHERE user_id = 42 AND created_at >= '2026-01-01 00:00:00'; ``` *Почему это хорошо:* Фильтр равенства по `user_id` позволяет СУБД мгновенно перейти к записям нужного пользователя, а затем использовать отсортированные листовые узлы `created_at` для сканирования диапазона. ### Ошибка 2: Индексирование столбцов с низкой кардинальностью **Плохая практика:** Добавление индекса на логический (boolean) столбец или статус с малым набором значений (например, `is_active` или `has_paid`). ```sql -- database/queries/bad_low_cardinality.sql CREATE INDEX idx_orders_active ON orders (status); -- status принимает только 'pending' или 'completed' ``` *Why it's bad:* Если значения статуса распределены равномерно, индекс бесполезен. Оптимизатор запросов сопоставит стоимость обхода вторичного индекса со стоимостью случайных чтений из кластеризованного индекса/кучи и решит, что последовательное сканирование всей таблицы будет быстрее. Индекс останется невостребованным, но продолжит замедлять запись. --- ## 6. Интерактивный тест Проверьте свои знания архитектуры индексов: ### Вопрос 1 Допустим, на таблице создан составной индекс `idx_test (A, B, C)`. Какой из следующих запросов **НЕ** сможет использовать этот индекс? 1. `WHERE A = 1 AND B = 2` 2. `WHERE B = 2 AND C = 3` 3. `WHERE A = 1 AND C = 3`
Нажмите, чтобы увидеть ответ **Ответ: Запрос 2 (`WHERE B = 2 AND C = 3`)** **Объяснение:** Согласно правилу самого левого префикса, для использования индекса запрос должен обязательно фильтровать по первому столбцу индекса (`A`). Поскольку Запрос 2 не фильтрует по `A`, база данных не может пройти по корневым узлам B-Tree и будет вынуждена сканировать всю таблицу. Запрос 3 *может* задействовать индекс, но только его часть `A`; СУБД найдет записи, где `A = 1`, а затем вручную отфильтрует их по `C = 3`.
--- ### Вопрос 2 Почему обновление неиндексируемого столбца в PostgreSQL иногда вызывает избыточную запись во всех индексах (index write amplification), тогда как в MySQL InnoDB этого не происходит?
Нажмите, чтобы увидеть ответ **Ответ:** Это связано с различиями между структурами Кучи (Heap) и кластеризованного индекса. * В PostgreSQL при выполнении UPDATE, если оптимизация HOT (Heap Only Tuples) невозможна (например, на исходной странице нет свободного места), новая версия строки записывается на другую страницу. Это меняет физический адрес строки (TID). Как следствие, *все* индексы этой таблицы должны быть обновлены, чтобы указывать на новый TID, вызывая избыточную запись в индексах. * В MySQL InnoDB строка остается в том же листовом узле кластеризованного индекса (если только сам первичный ключ не обновляется). Вторичные индексы ссылаются на значение первичного ключа, а не на физический дисковый адрес, поэтому их листовые узлы обновлять не требуется.
--- ### Вопрос 3 У вас есть таблица с 10 миллионами строк. Вы запускаете следующий запрос: `SELECT user_id, status FROM orders WHERE user_id = 100500;` Индекс на `user_id` определен как: `CREATE INDEX idx_user ON orders (user_id);` Как оптимизировать этот запрос, чтобы полностью исключить обращение к страницам данных таблицы?
Нажмите, чтобы увидеть ответ **Ответ:** Создать **покрывающий индекс (covering index)**, включающий столбец `status`. * В PostgreSQL: `CREATE INDEX idx_user_status ON orders (user_id) INCLUDE (status);` * В MySQL (или PostgreSQL): `CREATE INDEX idx_user_status ON orders (user_id, status);` **Объяснение:** Благодаря добавлению `status` в индекс, все столбцы, запрашиваемые в `SELECT` и `WHERE`, содержатся непосредственно в страницах самого индекса. СУБД сможет выполнить **Index Only Scan**, полностью пропустив этап чтения кучи или кластеризованного индекса.