--- 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' ``` *Чому це погано:* Якщо значення статусу розподілені рівномірно, індекс марний. Оптимізатор запитів співставить вартість обходу вторинного індексу з вартістю випадкових читань із кластеризованого індексу/купи і вирішить, що послідовне сканування всієї таблиці буде швидшим. Індекс залишиться незадіяним, але продовжить сповільнювати запис. --- ## 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**, повністю пропустивши етап читання купи або кластеризованого індексу.