Принципи роботи індексів: структура даних та алгоритми пошуку

Сьогодні ми зануримось глибше в архітектуру індексів і розглянемо, як вони реально працюють під капотом. Бо знання пристрою індексу допомагає не тільки розуміти, чому запити працюють швидше, а й як обирати оптимальні індекси для різних задач.

Коли ми говоримо про структуру індексу, йдеться про те, як дані організовані всередині індексу для забезпечення швидкого пошуку. Уяви собі шафу з документами. Якщо документи просто звалені в одну купу, знайти потрібний буде складно. Але якщо шафа організована за алфавітом, пошук стає значно простішим. Індекси працюють саме так: вони впорядковують дані так, щоб пошук потрібної інформації відбувався максимально швидко.

Структура B-TREE індексу

B-TREE (balanced tree — збалансоване дерево) — це найчастіше використовуваний тип індексу в PostgreSQL. По суті, це деревоподібна структура, де дані організовані у вузли, а пошук відбувається через навігацію від кореня дерева до листків.

Як це виглядає:

         Корінь
          /       |       \
      Вузол 1    Вузол 2    Вузол 3
     /   \       |       /   \
Лист1 Лист2   Лист3  Лист4 Лист5

Кожен вузол містить ключові значення, які дозволяють спрямовувати пошук. Наприклад, якщо кореневий вузол містить значення [10, 20, 30], то:

• Всі дані менше 10 знаходяться в Листі 1.
• Всі дані між 10 і 20 — у Листі 2, і так далі.

Переваги B-TREE індексу:

• Швидкий пошук даних: складність пошуку складає O(log n), що значно швидше, ніж лінійний пошук.
• Підходить для пошуку за діапазонами (наприклад, знайти всі значення між 10 і 50).

Приклад: припустимо, у нас є таблиця students з колонкою age. Коли ми створюємо B-TREE індекс на цій колонці:

CREATE INDEX age_idx ON students (age);

PostgreSQL створює збалансоване дерево для значень віку, що дозволяє швидко знаходити студентів певного віку або діапазону віків.

Алгоритм пошуку в B-TREE

Коли ти виконуєш запит, PostgreSQL використовує індекс для пошуку даних наступним чином:

1. Визначає ключ пошуку (наприклад, вік 25).
2. Починає з кореневого вузла.
3. Порівнює ключ з діапазонами значень вузла і переходить у відповідний дочірній вузол.
4. Повторює крок 3, поки не дійде до листка.
5. Повертає дані з листка, що відповідають ключу.

Приклад запиту:

SELECT * FROM students WHERE age = 25;

Індекс скорочує кількість даних, які треба сканувати, забезпечуючи швидкий пошук.

Алгоритми пошуку та продуктивність

Індекси пришвидшують пошук за рахунок зменшення кількості рядків, які треба просканувати. Без індексу PostgreSQL сканує всю таблицю (це називається послідовне сканування, або Seq Scan). З індексом же виконується індексне сканування (Index Scan), що набагато швидше.

Порівняння послідовного та індексного сканування

• Послідовне сканування (Seq Scan):

  • PostgreSQL читає кожен рядок таблиці, перевіряє умови запиту і повертає підходящі рядки.
  • Використовується, якщо індексу немає або якщо запит охоплює майже всі рядки таблиці.

• Індексне сканування (Index Scan):

  • PostgreSQL використовує індекс для пошуку відповідних рядків, а потім звертається до таблиці тільки для них.
  • Значно швидше для великих таблиць, якщо запит зачіпає невелику вибірку даних.

Приклад: без індексу пошук віків

SELECT * FROM students WHERE age = 25;

результат може вимагати читання 1 мільйона рядків. З індексом B-TREE система, наприклад, читає лише 100 рядків.

Вплив структури індексу на продуктивність

Індекси працюють швидше, бо вони скорочують обсяг сканованих даних. Наприклад, якщо в таблиці є мільйони рядків, індекс організовує їх так, що запиту треба прочитати лише кілька вузлів замість всієї таблиці.

Дуже важливо розуміти структуру індексу. Знання, як саме працюють індекси, допомагає зрозуміти, чому деякі запити повільні і як їх прискорити.

Крім того важливо розуміти, які індекси треба використовувати. Для пошуку за діапазонами підходить B-TREE. Для масивів або JSONB — GIN. Неправильний вибір індексу може сповільнити роботу бази.

Реальні приклади

Давай подивимось, як індекси допомагають нам у роботі.

Індекс для сортування

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

З індексом B-TREE PostgreSQL може повернути відсортовані дані напряму з індексу, без додаткового сортування.

Індекс для діапазонів

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

Індекс B-TREE дозволяє швидко знаходити рядки, що потрапляють у заданий діапазон.

Часті питання та підводні камені

Чому не завжди варто використовувати індекси? Індекси займають місце на диску і сповільнюють операції вставки, оновлення та видалення, бо треба оновлювати структуру індексу. Тому важливо створювати індекси тільки для часто використовуваних колонок.

Коли індекси не допомагають? Для запитів, що охоплюють більшу частину таблиці (наприклад, WHERE true), PostgreSQL віддасть перевагу Seq Scan, бо читання індексних вузлів не дає виграшу.