Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Як реалізуються індекси всередині СУБД?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)Індекси всередині СУБД реалізуються як **окремі структури даних**, оптимізовані під швидкий пошук, сортування й навігацію: залежно від типу індексу й движка зберігання використовуються різні алгоритми - найчастіше **B-дерева**, рідше хеш-таблиці, GiST, GIN чи R-дерева. **Ключове:** B-tree/B+tree - основний тип (PostgreSQL, MySQL InnoDB, Oracle) з `O(log n)` пошуком; hash-індекси дають `O(1)` для точних збігів, але не підходять для діапазонів; GiST і GIN застосовуються для повнотекстового пошуку, JSON і масивів; R-tree - для геоданих.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)ЗображенняІндекси всередині СУБД реалізуються як **окремі структури даних**, оптимізовані під швидкий пошук, сортування й навігацію. Залежно від типу індексу й движка зберігання використовуються різні алгоритми - найчастіше **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)`) та ефективну роботу фільтрів, сортувань і діапазонів.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.