Як реалізуються індекси всередині СУБД?

Індекси всередині СУБД реалізуються як окремі структури даних, оптимізовані під швидкий пошук, сортування й навігацію. Залежно від типу індексу й движка зберігання використовуються різні алгоритми - найчастіше B-дерева, рідше хеш-таблиці, GiST, GIN або R-дерева.

Розберемо детальніше:

#1. B-tree / B+tree (основний тип)

Найпоширеніший варіант (PostgreSQL, MySQL InnoDB, Oracle).

• Вузли дерева містять ключі й посилання на підвузли.
• Ключі відсортовані, тому пошук, вставка й видалення займають O(log n) операцій.
• Листові вузли пов'язані між собою, що прискорює діапазонні запити (BETWEEN, <, >, ORDER BY).

Приклад: індекс за age зберігає дерево, де вузли містять діапазони віку. Пошук 25-річного користувача потребує пройти від кореня до листка через 3-4 рівні дерева, замість сканування всієї таблиці.

#2. Hash-індекси

Використовуються, коли потрібні точні збіги (=), але не діапазони.

• Ключ пропускається через хеш-функцію, яка визначає «комірку».
• У комірці зберігається посилання на рядок таблиці.
• Пошук дуже швидкий (O(1)), але не можна використати для сортування чи > / <.

Приклад: PostgreSQL підтримує USING hash, але застосовують рідше через обмеження.

#3. GiST (Generalized Search Tree)

Гнучка структура, яка може зберігати не лише числа й текст, а й геодані, масиви, діапазони тощо. Використовується, наприклад, у PostgreSQL для FULL TEXT SEARCH, cube, hstore, tsvector.

#4. GIN (Generalized Inverted Index)

Оптимізований під пошук за множинами: масивами, JSON, текстами.

• Зберігає «обернені списки» - для кожного значення чи слова вказує, у яких рядках воно трапляється.
• Застосовується в повнотекстовому пошуку (to_tsvector, @@).

#5. R-tree (для геоданих)

Використовується в движках на кшталт SQLite чи PostGIS для зберігання координат. Індексує просторові об'єкти - точки, полігони, прямокутники, і прискорює запити типу «знайди всі об'єкти в радіусі».

Загальна будова індексного файлу:

• Метадані (тип індексу, рівень дерева, статистика).
• Вузли (гілки) і листки (ключі + посилання на рядки).
• У кластері СУБД - окрема фізична сторінка (зазвичай 8 КБ).

Підсумок: Індекс - це вбудована структура даних усередині СУБД, зазвичай реалізована як B+tree. Вона зберігає відсортовані ключі й посилання на рядки, щоб забезпечити швидкий пошук (O(log n)) та ефективну роботу фільтрів, сортувань і діапазонів.